split generating symbol quads from collision code

Collision prevention is temporarily disabled.

7 files changed, 290 insertions, 356 deletions

diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp
index c50ac15dff..166d5cf148 100644
--- a/src/mbgl/renderer/symbol_bucket.cpp
+++ b/src/mbgl/renderer/symbol_bucket.cpp
@@ -9,7 +9,8 @@
 #include <mbgl/geometry/resample.hpp>
 #include <mbgl/renderer/painter.hpp>
 #include <mbgl/text/glyph_store.hpp>
-#include <mbgl/text/placement.hpp>
+#include <mbgl/text/shaping.hpp>
+#include <mbgl/text/quads.hpp>
 #include <mbgl/platform/log.hpp>
 #include <mbgl/text/collision.hpp>
 #include <mbgl/map/sprite.hpp>
@@ -223,8 +224,6 @@ void SymbolBucket::addFeatures(const GeometryTileLayer& layer,
 
 bool byScale(const Anchor &a, const Anchor &b) { return a.scale < b.scale; }
 
-const PlacementRange fullRange{{2 * M_PI, 0}};
-
 void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping &shaping,
                               const GlyphPositions &face, const Rect<uint16_t> &image) {
     assert(line.size());
@@ -239,7 +238,7 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
         layout.icon.rotation_alignment == RotationAlignmentType::Viewport;
     const float fontScale = layout.text.max_size / glyphSize;
     const float textBoxScale = collision.tilePixelRatio * fontScale;
-    const float iconBoxScale = collision.tilePixelRatio * layout.icon.max_size;
+    //const float iconBoxScale = collision.tilePixelRatio * layout.icon.max_size;
     const bool iconWithoutText = layout.text.optional || !shaping.positionedGlyphs.size();
     const bool textWithoutIcon = layout.icon.optional || !image;
     const bool avoidEdges = layout.avoid_edges && layout.placement != PlacementType::Line;
@@ -279,8 +278,8 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
     for (Anchor &anchor : anchors) {
 
         // Calculate the scales at which the text and icons can be first shown without overlap
-        Placement glyphPlacement;
-        Placement iconPlacement;
+        PlacedGlyphs placedGlyphs;
+        PlacedGlyphs placedIcons;
         float glyphScale = 0;
         float iconScale = 0;
         const bool inside = !(anchor.x < 0 || anchor.x > 4096 || anchor.y < 0 || anchor.y > 4096);
@@ -288,22 +287,27 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
         if (avoidEdges && !inside) continue;
 
         if (shaping.positionedGlyphs.size()) {
-            glyphPlacement = Placement::getGlyphs(anchor, origin, shaping, face, textBoxScale,
-                                                  horizontalText, line, layout);
-            glyphScale =
+
+            placedGlyphs = getGlyphQuads(anchor, shaping, textBoxScale, line, layout, !horizontalText, face);
+            glyphScale = 0.5f;
+            /*
                 layout.text.allow_overlap
                     ? glyphPlacement.minScale
                     : collision.getPlacementScale(glyphPlacement.boxes, glyphPlacement.minScale, avoidEdges);
+                    */
             if (!glyphScale && !iconWithoutText)
                 continue;
         }
 
         if (image) {
-            iconPlacement = Placement::getIcon(anchor, image, iconBoxScale, line, layout);
-            iconScale =
+            auto shapedImage = shapeIcon(image, layout);
+            placedIcons = getIconQuads(anchor, shapedImage, line, layout, !horizontalIcon);
+            iconScale = 0.5f;
+                /*
                 layout.icon.allow_overlap
                     ? iconPlacement.minScale
                     : collision.getPlacementScale(iconPlacement.boxes, iconPlacement.minScale, avoidEdges);
+                    */
             if (!iconScale && !textWithoutIcon)
                 continue;
         }
@@ -317,7 +321,8 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
         }
 
         // Get the rotation ranges it is safe to show the glyphs
-        PlacementRange glyphRange =
+        /*
+        PlacementRange glyphRange = fullRange;
             (!glyphScale || layout.text.allow_overlap)
                 ? fullRange
                 : collision.getPlacementRange(glyphPlacement.boxes, glyphScale, horizontalText);
@@ -337,21 +342,26 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping
         } else if (!iconWithoutText) {
             iconRange = maxRange;
         }
+                */
 
         // Insert final placement into collision tree and add glyphs/icons to buffers
         if (glyphScale && std::isfinite(glyphScale)) {
             if (!layout.text.ignore_placement) {
+                /*
                 collision.insert(glyphPlacement.boxes, anchor, glyphScale, glyphRange,
                                  horizontalText);
+                                 */
             }
-            if (inside) addSymbols<TextBuffer, TextElementGroup>(text, glyphPlacement.shapes, glyphScale);
+            if (inside) addSymbols<TextBuffer, TextElementGroup>(text, placedGlyphs, glyphScale);
         }
 
         if (iconScale && std::isfinite(iconScale)) {
+            /*
             if (!layout.icon.ignore_placement) {
                 collision.insert(iconPlacement.boxes, anchor, iconScale, iconRange, horizontalIcon);
             }
-            if (inside) addSymbols<IconBuffer, IconElementGroup>(icon, iconPlacement.shapes, iconScale);
+            */
+            if (inside) addSymbols<IconBuffer, IconElementGroup>(icon, placedIcons, iconScale);
         }
     }
 }
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
deleted file mode 100644
index ff25204f2a..0000000000
--- a/src/mbgl/text/placement.cpp
+++ /dev/null
@@ -1,311 +0,0 @@
-#include <mbgl/text/placement.hpp>
-#include <mbgl/geometry/anchor.hpp>
-#include <mbgl/text/glyph.hpp>
-#include <mbgl/text/placement.hpp>
-#include <mbgl/text/glyph_store.hpp>
-#include <mbgl/style/style_bucket.hpp>
-#include <mbgl/style/style_layout.hpp>
-
-#include <mbgl/util/math.hpp>
-
-namespace mbgl {
-
-const float Placement::globalMinScale = 0.5; // underscale by 1 zoom level
-
-struct GlyphInstance {
-    explicit GlyphInstance(const vec2<float> &anchor_) : anchor(anchor_) {}
-    explicit GlyphInstance(const vec2<float> &anchor_, float offset_, float minScale_, float maxScale_,
-                           float angle_)
-        : anchor(anchor_), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {}
-
-    const vec2<float> anchor;
-    const float offset = 0.0f;
-    const float minScale = Placement::globalMinScale;
-    const float maxScale = std::numeric_limits<float>::infinity();
-    const float angle = 0.0f;
-};
-
-typedef std::vector<GlyphInstance> GlyphInstances;
-
-void getSegmentGlyphs(std::back_insert_iterator<GlyphInstances> glyphs, Anchor &anchor,
-                      float offset, const std::vector<Coordinate> &line, int segment,
-                      int8_t direction, float maxAngle) {
-    const bool upsideDown = direction < 0;
-
-    if (offset < 0)
-        direction *= -1;
-
-    if (direction > 0)
-        segment++;
-
-    vec2<float> newAnchor = anchor;
-
-    if ((int)line.size() <= segment) {
-        return;
-    }
-    vec2<float> end = line[segment];
-    float prevscale = std::numeric_limits<float>::infinity();
-    float prevAngle = 0.0f;
-
-    offset = std::fabs(offset);
-
-    const float placementScale = anchor.scale;
-
-    while (true) {
-        const float dist = util::dist<float>(newAnchor, end);
-        const float scale = offset / dist;
-        float angle =
-            -std::atan2(end.x - newAnchor.x, end.y - newAnchor.y) + direction * M_PI / 2.0f;
-        if (upsideDown)
-            angle += M_PI;
-
-        // Don't place around sharp corners
-        float angleDiff = std::fmod((angle - prevAngle), (2.0f * M_PI));
-        if (prevAngle && std::fabs(angleDiff) > maxAngle) {
-            anchor.scale = prevscale;
-            break;
-        }
-
-        glyphs = GlyphInstance{
-            /* anchor */ newAnchor,
-            /* offset */ static_cast<float>(upsideDown ? M_PI : 0.0),
-            /* minScale */ scale,
-            /* maxScale */ prevscale,
-            /* angle */ static_cast<float>(std::fmod((angle + 2.0 * M_PI), (2.0 * M_PI)))};
-
-        if (scale <= placementScale)
-            break;
-
-        newAnchor = end;
-
-        // skip duplicate nodes
-        while (newAnchor == end) {
-            segment += direction;
-            if ((int)line.size() <= segment || segment < 0) {
-                anchor.scale = scale;
-                return;
-            }
-            end = line[segment];
-        }
-
-        vec2<float> normal = util::normal<float>(newAnchor, end) * dist;
-        newAnchor = newAnchor - normal;
-
-        prevscale = scale;
-        prevAngle = angle;
-    }
-}
-
-GlyphBox getMergedBoxes(const GlyphBoxes &glyphs, const Anchor &anchor) {
-    // Collision checks between rotating and fixed labels are relatively expensive,
-    // so we use one box per label, not per glyph for horizontal labels.
-
-    const float inf = std::numeric_limits<float>::infinity();
-
-    GlyphBox mergedglyphs{/* box */ CollisionRect{inf, inf, -inf, -inf},
-                          /* anchor */ anchor,
-                          /* minScale */ 0,
-                          /* maxScale */ inf,
-                          /* padding */ -inf};
-
-    CollisionRect &box = mergedglyphs.box;
-
-    for (const GlyphBox &glyph : glyphs) {
-        const CollisionRect &gbox = glyph.box;
-        box.tl.x = util::min(box.tl.x, gbox.tl.x);
-        box.tl.y = util::min(box.tl.y, gbox.tl.y);
-        box.br.x = util::max(box.br.x, gbox.br.x);
-        box.br.y = util::max(box.br.y, gbox.br.y);
-        mergedglyphs.minScale = util::max(mergedglyphs.minScale, glyph.minScale);
-        mergedglyphs.padding = util::max(mergedglyphs.padding, glyph.padding);
-    }
-    // for all horizontal labels, calculate bbox covering all rotated positions
-    float x12 = box.tl.x * box.tl.x, y12 = box.tl.y * box.tl.y, x22 = box.br.x * box.br.x,
-          y22 = box.br.y * box.br.y,
-          diag = std::sqrt(util::max(x12 + y12, x12 + y22, x22 + y12, x22 + y22));
-
-    mergedglyphs.hBox = CollisionRect{-diag, -diag, diag, diag};
-
-    return mergedglyphs;
-}
-
-Placement Placement::getIcon(Anchor &anchor, const Rect<uint16_t> &image, float boxScale,
-                             const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout) {
-
-    const float dx = layout.icon.offset[0];
-    const float dy = layout.icon.offset[1];
-    float x1 = dx - image.originalW / 2.0f;
-    float x2 = x1 + image.w;
-    float y1 = dy - image.originalH / 2.0f;
-    float y2 = y1 + image.h;
-
-    vec2<float> tl{x1, y1};
-    vec2<float> tr{x2, y1};
-    vec2<float> br{x2, y2};
-    vec2<float> bl{x1, y2};
-
-    float angle = layout.icon.rotate * M_PI / 180.0f;
-    if (anchor.segment >= 0 && layout.icon.rotation_alignment != RotationAlignmentType::Viewport) {
-        const Coordinate &next = line[anchor.segment];
-        angle += -std::atan2(next.x - anchor.x, next.y - anchor.y) + M_PI / 2;
-    }
-
-    if (angle) {
-        // Compute the transformation matrix.
-        float angle_sin = std::sin(angle);
-        float angle_cos = std::cos(angle);
-        std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
-
-        tl = tl.matMul(matrix);
-        tr = tr.matMul(matrix);
-        bl = bl.matMul(matrix);
-        br = br.matMul(matrix);
-
-        x1 = util::min(tl.x, tr.x, bl.x, br.x);
-        x2 = util::max(tl.x, tr.x, bl.x, br.x);
-        y1 = util::min(tl.y, tr.y, bl.y, br.y);
-        y2 = util::max(tl.y, tr.y, bl.y, br.y);
-    }
-
-    const CollisionRect box{/* x1 */ x1 * boxScale,
-                            /* y1 */ y1 * boxScale,
-                            /* x2 */ x2 * boxScale,
-                            /* y2 */ y2 * boxScale};
-
-    Placement placement;
-
-    placement.boxes.emplace_back(
-        /* box */ box,
-        /* anchor */ anchor,
-        /* minScale */ Placement::globalMinScale,
-        /* maxScale */ std::numeric_limits<float>::infinity(),
-        /* padding */ layout.icon.padding);
-
-    placement.shapes.emplace_back(
-        /* tl */ tl,
-        /* tr */ tr,
-        /* bl */ bl,
-        /* br */ br,
-        /* image */ image,
-        /* angle */ 0,
-        /* anchors */ anchor,
-        /* minScale */ Placement::globalMinScale,
-        /* maxScale */ std::numeric_limits<float>::infinity());
-
-    placement.minScale = anchor.scale;
-
-    return placement;
-}
-
-Placement Placement::getGlyphs(Anchor &anchor, const vec2<float> &origin, const Shaping &shaping,
-                               const GlyphPositions &face, float boxScale, bool horizontal,
-                               const std::vector<Coordinate> &line,
-                               const StyleLayoutSymbol &layout) {
-    const float maxAngle = layout.text.max_angle * M_PI / 180;
-    const float rotate = layout.text.rotate * M_PI / 180;
-    const float padding = layout.text.padding;
-    const bool alongLine = layout.text.rotation_alignment != RotationAlignmentType::Viewport;
-    const bool keepUpright = layout.text.keep_upright;
-
-    Placement placement;
-
-    const uint32_t buffer = 3;
-
-    for (const PositionedGlyph &shape : shaping.positionedGlyphs) {
-        auto face_it = face.find(shape.glyph);
-        if (face_it == face.end())
-            continue;
-        const Glyph &glyph = face_it->second;
-        const Rect<uint16_t> &rect = glyph.rect;
-
-        if (!glyph)
-            continue;
-
-        if (!rect)
-            continue;
-
-        const float x = (origin.x + shape.x + glyph.metrics.left - buffer + rect.w / 2) * boxScale;
-
-        GlyphInstances glyphInstances;
-        if (anchor.segment >= 0 && alongLine) {
-            getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, x, line, anchor.segment, 1,
-                             maxAngle);
-            if (keepUpright)
-                getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, x, line,
-                                 anchor.segment, -1, maxAngle);
-
-        } else {
-            glyphInstances.emplace_back(GlyphInstance{anchor});
-        }
-
-        const float x1 = origin.x + shape.x + glyph.metrics.left - buffer;
-        const float y1 = origin.y + shape.y - glyph.metrics.top - buffer;
-        const float x2 = x1 + glyph.rect.w;
-        const float y2 = y1 + glyph.rect.h;
-
-        const vec2<float> otl{x1, y1};
-        const vec2<float> otr{x2, y1};
-        const vec2<float> obl{x1, y2};
-        const vec2<float> obr{x2, y2};
-
-        const CollisionRect obox{boxScale * x1, boxScale * y1, boxScale * x2, boxScale * y2};
-
-        for (const GlyphInstance &instance : glyphInstances) {
-            vec2<float> tl = otl;
-            vec2<float> tr = otr;
-            vec2<float> bl = obl;
-            vec2<float> br = obr;
-
-            CollisionRect box = obox;
-
-            // Clamp to -90/+90 degrees
-            const float angle = instance.angle + rotate;
-
-            if (angle) {
-                // Compute the transformation matrix.
-                float angle_sin = std::sin(angle);
-                float angle_cos = std::cos(angle);
-                std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
-
-                tl = tl.matMul(matrix);
-                tr = tr.matMul(matrix);
-                bl = bl.matMul(matrix);
-                br = br.matMul(matrix);
-            }
-
-            // Prevent label from extending past the end of the line
-            const float glyphMinScale = std::max(instance.minScale, anchor.scale);
-
-            // Remember the glyph for later insertion.
-            placement.shapes.emplace_back(
-                tl, tr, bl, br, rect,
-                float(std::fmod((anchor.angle + rotate + instance.offset + 2 * M_PI), (2 * M_PI))),
-                instance.anchor, glyphMinScale, instance.maxScale);
-
-            if (!instance.offset) { // not a flipped glyph
-                if (angle) {
-                    // Calculate the rotated glyph's bounding box offsets from the anchor point.
-                    box = CollisionRect{boxScale * util::min(tl.x, tr.x, bl.x, br.x),
-                                        boxScale * util::min(tl.y, tr.y, bl.y, br.y),
-                                        boxScale * util::max(tl.x, tr.x, bl.x, br.x),
-                                        boxScale * util::max(tl.y, tr.y, bl.y, br.y)};
-                }
-                placement.boxes.emplace_back(box, instance.anchor, glyphMinScale, instance.maxScale, padding);
-            }
-        }
-    }
-
-    // TODO avoid creating the boxes in the first place?
-    if (horizontal)
-        placement.boxes = {getMergedBoxes(placement.boxes, anchor)};
-
-    const float minPlacementScale = anchor.scale;
-    placement.minScale = std::numeric_limits<float>::infinity();
-    for (const GlyphBox &box : placement.boxes) {
-        placement.minScale = util::min(placement.minScale, box.minScale);
-    }
-    placement.minScale = util::max(minPlacementScale, Placement::globalMinScale);
-
-    return placement;
-}
-}
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
deleted file mode 100644
index 40762b8d70..0000000000
--- a/src/mbgl/text/placement.hpp
+++ /dev/null
@@ -1,31 +0,0 @@
-#ifndef MBGL_TEXT_PLACEMENT
-#define MBGL_TEXT_PLACEMENT
-
-#include <mbgl/text/types.hpp>
-#include <mbgl/text/glyph.hpp>
-
-#include <mbgl/util/vec.hpp>
-
-namespace mbgl {
-
-struct Anchor;
-class StyleLayoutSymbol;
-
-class Placement {
-public:
-    static Placement getIcon(Anchor &anchor, const Rect<uint16_t> &image, float iconBoxScale,
-                             const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout);
-
-    static Placement getGlyphs(Anchor &anchor, const vec2<float> &origin, const Shaping &shaping,
-                               const GlyphPositions &face, float boxScale, bool horizontal,
-                               const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout);
-
-    static const float globalMinScale;
-
-    GlyphBoxes boxes;
-    PlacedGlyphs shapes;
-    float minScale;
-};
-}
-
-#endif
diff --git a/src/mbgl/text/quads.cpp b/src/mbgl/text/quads.cpp
new file mode 100644
index 0000000000..02ffb1fb61
--- /dev/null
+++ b/src/mbgl/text/quads.cpp
@@ -0,0 +1,194 @@
+#include <mbgl/text/quads.hpp>
+#include <mbgl/text/shaping.hpp>
+#include <mbgl/geometry/anchor.hpp>
+#include <mbgl/style/style_layout.hpp>
+#include <mbgl/util/math.hpp>
+#include <cassert>
+
+namespace mbgl {
+
+const float globalMinScale = 0.5f; // underscale by 1 zoom level
+
+PlacedGlyphs getIconQuads(Anchor &anchor, const PositionedIcon &shapedIcon,
+        const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout,
+        const bool alongLine) {
+
+    vec2<float> tl{shapedIcon.left, shapedIcon.top};
+    vec2<float> tr{shapedIcon.right, shapedIcon.top};
+    vec2<float> br{shapedIcon.right, shapedIcon.bottom};
+    vec2<float> bl{shapedIcon.left, shapedIcon.bottom};
+
+
+    float angle = layout.icon.rotate * M_PI / 180.0f;
+    if (alongLine) {
+        assert(anchor.segment < line.size());
+        const Coordinate &next = line[anchor.segment];
+        angle += -std::atan2(next.x - anchor.x, next.y - anchor.y) + M_PI / 2;
+    }
+
+
+    if (angle) {
+        // Compute the transformation matrix.
+        float angle_sin = std::sin(angle);
+        float angle_cos = std::cos(angle);
+        std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
+
+        tl = tl.matMul(matrix);
+        tr = tr.matMul(matrix);
+        bl = bl.matMul(matrix);
+        br = br.matMul(matrix);
+    }
+
+    PlacedGlyphs quads;
+    quads.emplace_back(tl, tr, bl, br, shapedIcon.image, 0, anchor, globalMinScale, std::numeric_limits<float>::infinity());
+    return quads;
+}
+
+struct GlyphInstance {
+    explicit GlyphInstance(const vec2<float> &anchor_) : anchor(anchor_) {}
+    explicit GlyphInstance(const vec2<float> &anchor_, float offset_, float minScale_, float maxScale_,
+            float angle_)
+        : anchor(anchor_), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {}
+
+    const vec2<float> anchor;
+    const float offset = 0.0f;
+    const float minScale = globalMinScale;
+    const float maxScale = std::numeric_limits<float>::infinity();
+    const float angle = 0.0f;
+};
+
+typedef std::vector<GlyphInstance> GlyphInstances;
+
+void getSegmentGlyphs(std::back_insert_iterator<GlyphInstances> glyphs, Anchor &anchor,
+        float offset, const std::vector<Coordinate> &line, int segment, int8_t direction) {
+
+    const bool upsideDown = direction < 0;
+
+    if (offset < 0)
+        direction *= -1;
+
+    if (direction > 0)
+        segment++;
+
+    assert((int)line.size() > segment);
+    vec2<float> end = line[segment];
+    vec2<float> newAnchor = anchor;
+    float prevscale = std::numeric_limits<float>::infinity();
+
+    offset = std::fabs(offset);
+
+    const float placementScale = anchor.scale;
+
+    while (true) {
+        const float dist = util::dist<float>(newAnchor, end);
+        const float scale = offset / dist;
+        float angle = -std::atan2(end.x - newAnchor.x, end.y - newAnchor.y) + direction * M_PI / 2.0f;
+        if (upsideDown)
+            angle += M_PI;
+
+        glyphs = GlyphInstance{
+            /* anchor */ newAnchor,
+            /* offset */ static_cast<float>(upsideDown ? M_PI : 0.0),
+            /* minScale */ scale,
+            /* maxScale */ prevscale,
+            /* angle */ static_cast<float>(std::fmod((angle + 2.0 * M_PI), (2.0 * M_PI)))};
+
+        if (scale <= placementScale)
+            break;
+
+        newAnchor = end;
+
+        // skip duplicate nodes
+        while (newAnchor == end) {
+            segment += direction;
+            if ((int)line.size() <= segment || segment < 0) {
+                anchor.scale = scale;
+                return;
+            }
+            end = line[segment];
+        }
+
+        vec2<float> normal = util::normal<float>(newAnchor, end) * dist;
+        newAnchor = newAnchor - normal;
+
+        prevscale = scale;
+    }
+}
+
+PlacedGlyphs getGlyphQuads(Anchor &anchor, const Shaping &shapedText, 
+        const float boxScale, const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout,
+        const bool alongLine, const GlyphPositions &face) {
+
+    const float textRotate = layout.text.rotate * M_PI / 180;
+    const bool keepUpright = layout.text.keep_upright;
+
+    PlacedGlyphs quads;
+
+    for (const PositionedGlyph &positionedGlyph: shapedText.positionedGlyphs) {
+        auto face_it = face.find(positionedGlyph.glyph);
+        if (face_it == face.end())
+            continue;
+        const Glyph &glyph = face_it->second;
+        const Rect<uint16_t> &rect = glyph.rect;
+
+        if (!glyph)
+            continue;
+
+        if (!rect)
+            continue;
+
+        const float centerX = (positionedGlyph.x + glyph.metrics.advance / 2.0f) * boxScale;
+
+        GlyphInstances glyphInstances;
+        if (alongLine) {
+            getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, 1);
+            if (keepUpright)
+                getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, -1);
+
+        } else {
+            glyphInstances.emplace_back(GlyphInstance{anchor});
+        }
+
+        const float x1 = positionedGlyph.x + glyph.metrics.left;
+        const float y1 = positionedGlyph.y - glyph.metrics.top;
+        const float x2 = x1 + rect.w;
+        const float y2 = y1 + rect.h;
+
+        const vec2<float> otl{x1, y1};
+        const vec2<float> otr{x2, y1};
+        const vec2<float> obl{x1, y2};
+        const vec2<float> obr{x2, y2};
+
+        for (const GlyphInstance &instance : glyphInstances) {
+
+            vec2<float> tl = otl;
+            vec2<float> tr = otr;
+            vec2<float> bl = obl;
+            vec2<float> br = obr;
+            const float angle = instance.angle + textRotate;
+
+            if (angle) {
+                // Compute the transformation matrix.
+                float angle_sin = std::sin(angle);
+                float angle_cos = std::cos(angle);
+                std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
+
+                tl = tl.matMul(matrix);
+                tr = tr.matMul(matrix);
+                bl = bl.matMul(matrix);
+                br = br.matMul(matrix);
+            }
+
+            // Prevent label from extending past the end of the line
+            const float glyphMinScale = std::max(instance.minScale, anchor.scale);
+
+            const float glyphAngle = std::fmod((anchor.angle + textRotate + instance.offset + 2 * M_PI), (2 * M_PI));
+            quads.emplace_back(tl, tr, bl, br, rect, glyphAngle, instance.anchor, glyphMinScale, instance.maxScale);
+
+        }
+
+    }
+
+    return quads;
+}
+}
diff --git a/src/mbgl/text/quads.hpp b/src/mbgl/text/quads.hpp
new file mode 100644
index 0000000000..19acd72f46
--- /dev/null
+++ b/src/mbgl/text/quads.hpp
@@ -0,0 +1,24 @@
+#ifndef MBGL_TEXT_QUADS
+#define MBGL_TEXT_QUADS
+
+#include <mbgl/text/types.hpp>
+#include <mbgl/text/glyph.hpp>
+
+#include <mbgl/util/vec.hpp>
+
+namespace mbgl {
+
+    struct Anchor;
+    class StyleLayoutSymbol;
+    class PositionedIcon;
+
+    PlacedGlyphs getIconQuads(Anchor &anchor, const PositionedIcon &shapedIcon,
+            const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout,
+            const bool alongLine);
+    
+    PlacedGlyphs getGlyphQuads(Anchor &anchor, const Shaping &shapedText,
+            const float boxScale, const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout,
+            const bool alongLine, const GlyphPositions &face);
+}
+
+#endif
diff --git a/src/mbgl/text/shaping.cpp b/src/mbgl/text/shaping.cpp
new file mode 100644
index 0000000000..971b695e49
--- /dev/null
+++ b/src/mbgl/text/shaping.cpp
@@ -0,0 +1,18 @@
+#include <mbgl/text/shaping.hpp>
+#include <mbgl/style/style_layout.hpp>
+
+namespace mbgl {
+
+PositionedIcon shapeIcon(const Rect<uint16_t> &image, const StyleLayoutSymbol &layout) {
+    float dx = layout.icon.offset[0];
+    float dy = layout.icon.offset[1];
+    // TODO, this is image.image.width in -js
+    float x1 = dx - image.originalW / 2.0f;
+    float x2 = x1 + image.w;
+    float y1 = dy - image.originalH / 2.0f;
+    float y2 = y1 + image.h;
+
+    return PositionedIcon(image, y1, y2, x1, x2);
+}
+
+}
diff --git a/src/mbgl/text/shaping.hpp b/src/mbgl/text/shaping.hpp
new file mode 100644
index 0000000000..0af75b44cb
--- /dev/null
+++ b/src/mbgl/text/shaping.hpp
@@ -0,0 +1,30 @@
+#ifndef MBGL_TEXT_SHAPING
+#define MBGL_TEXT_SHAPING
+
+#include <mbgl/text/types.hpp>
+#include <mbgl/text/glyph.hpp>
+
+#include <mbgl/util/vec.hpp>
+
+namespace mbgl {
+
+    class PositionedIcon {
+        public:
+            inline explicit PositionedIcon() {}
+            inline explicit PositionedIcon(const Rect<uint16_t> _image,
+                    float _top, float _bottom, float _left, float _right) :
+                image(_image), top(_top), bottom(_bottom), left(_left), right(_right) {}
+            const Rect<uint16_t> image;
+            float top = 0;
+            float bottom = 0;
+            float left = 0;
+            float right = 0;
+    };
+
+    class StyleLayoutSymbol;
+
+    PositionedIcon shapeIcon(const Rect<uint16_t> &image, const StyleLayoutSymbol &layout);
+
+}
+
+#endif