6 files changed, 388 insertions, 0 deletions
diff --git a/include/mbgl/text/collision.hpp b/include/mbgl/text/collision.hpp
new file mode 100644
index 0000000000..31103a7439
--- /dev/null
+++ b/include/mbgl/text/collision.hpp
@@ -0,0 +1,32 @@
+#ifndef MBGL_TEXT_COLLISION
+#define MBGL_TEXT_COLLISION
+
+#include <mbgl/text/types.hpp>
+
+namespace mbgl {
+
+class Collision {
+
+public:
+    Collision();
+    ~Collision();
+
+    PlacementProperty place(const GlyphBoxes &boxes,
+                            const CollisionAnchor &anchor,
+                            float minPlacementScale, float maxPlacementScale,
+                            float padding, bool horizontal, bool alwaysVisible);
+    float getPlacementScale(const GlyphBoxes &glyphs, float minPlacementScale,
+                            float maxPlacementScale, float pad);
+    PlacementRange getPlacementRange(const GlyphBoxes &glyphs,
+                                     float placementScale, bool horizontal);
+    void insert(const GlyphBoxes &glyphs, const CollisionAnchor &anchor,
+                float placementScale, const PlacementRange &placementRange,
+                bool horizontal, float padding);
+
+private:
+    void *cTree;
+    void *hTree;
+};
+}
+
+#endif
diff --git a/include/mbgl/text/glyph.hpp b/include/mbgl/text/glyph.hpp
new file mode 100644
index 0000000000..899c8fffee
--- /dev/null
+++ b/include/mbgl/text/glyph.hpp
@@ -0,0 +1,61 @@
+#ifndef MBGL_TEXT_GLYPH
+#define MBGL_TEXT_GLYPH
+
+#include <mbgl/util/rect.hpp>
+
+#include <cstdint>
+#include <vector>
+#include <map>
+
+namespace mbgl {
+
+typedef std::pair<uint16_t, uint16_t> GlyphRange;
+
+// Note: this only works for the BMP
+GlyphRange getGlyphRange(char32_t glyph);
+
+struct GlyphMetrics {
+    operator bool() const {
+        return width == 0 && height == 0 && advance == 0;
+    }
+
+    // Glyph metrics.
+    uint32_t width = 0;
+    uint32_t height = 0;
+    int32_t left = 0;
+    int32_t top = 0;
+    uint32_t advance = 0;
+
+};
+
+struct Glyph {
+    inline explicit Glyph() : rect(0, 0, 0, 0), metrics() {}
+    inline explicit Glyph(const Rect<uint16_t> &rect,
+                          const GlyphMetrics &metrics)
+        : rect(rect), metrics(metrics) {}
+
+    operator bool() const {
+        return !metrics && !rect;
+    }
+
+    const Rect<uint16_t> rect;
+    const GlyphMetrics metrics;
+};
+
+typedef std::map<uint32_t, Glyph> GlyphPositions;
+
+class GlyphPlacement {
+public:
+    inline explicit GlyphPlacement(uint32_t face, uint32_t glyph, uint32_t x, uint32_t y)
+        : face(face), glyph(glyph), x(x), y(y) {}
+
+    uint32_t face = 0;
+    uint32_t glyph = 0;
+    int32_t x = 0;
+    int32_t y = 0;
+};
+
+typedef std::vector<GlyphPlacement> Shaping;
+}
+
+#endif
diff --git a/include/mbgl/text/glyph_store.hpp b/include/mbgl/text/glyph_store.hpp
new file mode 100644
index 0000000000..9c874b31b0
--- /dev/null
+++ b/include/mbgl/text/glyph_store.hpp
@@ -0,0 +1,95 @@
+#ifndef MBGL_TEXT_GLYPH_STORE
+#define MBGL_TEXT_GLYPH_STORE
+
+#include <mbgl/text/glyph.hpp>
+#include <mbgl/util/pbf.hpp>
+
+#include <cstdint>
+#include <vector>
+#include <future>
+#include <map>
+#include <set>
+#include <unordered_map>
+
+namespace mbgl {
+
+
+class SDFGlyph {
+public:
+    uint32_t id = 0;
+
+    // A signed distance field of the glyph with a border of 3 pixels.
+    std::string bitmap;
+
+    // Glyph metrics
+    GlyphMetrics metrics;
+};
+
+class FontStack {
+public:
+    void insert(uint32_t id, const SDFGlyph &glyph);
+    const std::map<uint32_t, GlyphMetrics> &getMetrics() const;
+    const std::map<uint32_t, SDFGlyph> &getSDFs() const;
+    const Shaping getShaping(const std::u32string &string,
+                             const float &maxWidth,
+                             const float &lineHeight,
+                             const float &alignment,
+                             const float &verticalAlignment,
+                             const float &letterSpacing) const;
+    void lineWrap(Shaping &shaping,
+                     const float &lineHeight,
+                     const float &maxWidth,
+                     const float &alignment,
+                     const float &verticalAlignment) const;
+
+private:
+    std::map<uint32_t, std::string> bitmaps;
+    std::map<uint32_t, GlyphMetrics> metrics;
+    std::map<uint32_t, SDFGlyph> sdfs;
+    mutable std::mutex mtx;
+};
+
+class GlyphPBF {
+public:
+    GlyphPBF(const std::string &glyphURL, const std::string &fontStack, GlyphRange glyphRange);
+
+    void parse(FontStack &stack);
+
+    std::shared_future<GlyphPBF &> getFuture();
+
+private:
+    std::string data;
+    std::promise<GlyphPBF &> promise;
+    std::shared_future<GlyphPBF &> future;
+    std::mutex mtx;
+};
+
+// Manages Glyphrange PBF loading.
+class GlyphStore {
+public:
+    GlyphStore(const std::string &glyphURL);
+
+    // Block until all specified GlyphRanges of the specified font stack are loaded.
+    void waitForGlyphRanges(const std::string &fontStack, const std::set<GlyphRange> &glyphRanges);
+
+    FontStack &getFontStack(const std::string &fontStack);
+
+private:
+    // Loads an individual glyph range from the font stack and adds it to rangeSets
+    std::shared_future<GlyphPBF &> loadGlyphRange(const std::string &fontStack, std::map<GlyphRange, std::unique_ptr<GlyphPBF>> &rangeSets, GlyphRange range);
+
+    FontStack &createFontStack(const std::string &fontStack);
+
+public:
+    const std::string glyphURL;
+
+private:
+    std::unordered_map<std::string, std::map<GlyphRange, std::unique_ptr<GlyphPBF>>> ranges;
+    std::unordered_map<std::string, std::unique_ptr<FontStack>> stacks;
+    std::mutex mtx;
+};
+
+
+}
+
+#endif
diff --git a/include/mbgl/text/placement.hpp b/include/mbgl/text/placement.hpp
new file mode 100644
index 0000000000..69a1a10b72
--- /dev/null
+++ b/include/mbgl/text/placement.hpp
@@ -0,0 +1,37 @@
+#ifndef MBGL_TEXT_PLACEMENT
+#define MBGL_TEXT_PLACEMENT
+
+#include <mbgl/text/collision.hpp>
+#include <mbgl/geometry/geometry.hpp>
+#include <mbgl/util/vec.hpp>
+#include <mbgl/text/glyph.hpp>
+#include <vector>
+
+namespace mbgl {
+
+class TextBucket;
+class StyleBucketText;
+
+class Placement {
+public:
+    Placement(int8_t zoom);
+
+    void addFeature(TextBucket &bucket, const std::vector<Coordinate> &line,
+                    const StyleBucketText &info,
+                    const GlyphPositions &face,
+                    const Shaping &shaping);
+
+private:
+    const int8_t zoom;
+    Collision collision;
+    const float zOffset;
+    const float maxPlacementScale;
+
+public:
+    static const int tileExtent;
+    static const int glyphSize;
+    static const float minScale;
+};
+}
+
+#endif
diff --git a/include/mbgl/text/rotation_range.hpp b/include/mbgl/text/rotation_range.hpp
new file mode 100644
index 0000000000..4968fda164
--- /dev/null
+++ b/include/mbgl/text/rotation_range.hpp
@@ -0,0 +1,54 @@
+#ifndef MBGL_TEXT_ROTATION_RANGE
+#define MBGL_TEXT_ROTATION_RANGE
+
+#include <mbgl/util/math.hpp>
+#include <mbgl/text/types.hpp>
+
+#include <vector>
+#include <cassert>
+
+namespace mbgl {
+
+/*
+ * Combine an array of collision ranges to form a continuous
+ * range that includes 0. Collisions within the ignoreRange are ignored
+ */
+CollisionRange mergeCollisions(const CollisionList &collisions,
+                               PlacementRange ignoreRange);
+
+/*
+ *  Calculate collision ranges for two rotating boxes.e
+ */
+CollisionList rotatingRotatingCollisions(const CollisionRect &a,
+                                         const CollisionRect &b,
+                                         const CollisionAnchor &anchorToAnchor);
+
+/*
+ * Return the intersection points of a circle and a line segment;
+ */
+void circleEdgeCollisions(std::back_insert_iterator<CollisionAngles> angles,
+                          const CollisionPoint &corner, float radius,
+                          const CollisionPoint &p1, const CollisionPoint &p2);
+
+/*
+ *  Calculate the ranges for which the corner,
+ *  rotatated around the anchor, is within the box;
+ */
+void cornerBoxCollisions(std::back_insert_iterator<CollisionList> collisions,
+                         const CollisionPoint &corner,
+                         const CollisionCorners &boxCorners, bool flip = false);
+
+/*
+ *  Calculate collision ranges for a rotating box and a fixed box;
+ */
+CollisionList rotatingFixedCollisions(const CollisionRect &rotating,
+                                      const CollisionRect &fixed);
+
+/*
+ * Calculate the range a box conflicts with a second box
+ */
+CollisionRange rotationRange(const GlyphBox &inserting,
+                             const PlacementBox &blocker, float scale);
+}
+
+#endif
diff --git a/include/mbgl/text/types.hpp b/include/mbgl/text/types.hpp
new file mode 100644
index 0000000000..9a9284b588
--- /dev/null
+++ b/include/mbgl/text/types.hpp
@@ -0,0 +1,109 @@
+#ifndef MBGL_TEXT_TYPES
+#define MBGL_TEXT_TYPES
+
+#include <mbgl/util/vec.hpp>
+#include <mbgl/util/rect.hpp>
+#include <array>
+#include <vector>
+
+namespace mbgl {
+
+typedef vec2<float> CollisionPoint;
+typedef vec2<float> CollisionAnchor;
+
+typedef std::array<float, 2> PlacementRange;
+typedef float CollisionAngle;
+typedef std::vector<CollisionAngle> CollisionAngles;
+typedef std::array<CollisionAngle, 2> CollisionRange;
+typedef std::vector<CollisionRange> CollisionList;
+typedef std::array<CollisionPoint, 4> CollisionCorners;
+
+struct CollisionRect {
+    CollisionPoint tl;
+    CollisionPoint br;
+    inline explicit CollisionRect() {}
+    inline explicit CollisionRect(CollisionPoint::Type ax,
+                                  CollisionPoint::Type ay,
+                                  CollisionPoint::Type bx,
+                                  CollisionPoint::Type by)
+        : tl(ax, ay), br(bx, by) {}
+    inline explicit CollisionRect(const CollisionPoint &tl,
+                                  const CollisionPoint &br)
+        : tl(tl), br(br) {}
+};
+
+// These are the glyph boxes that we want to have placed.
+struct GlyphBox {
+    explicit GlyphBox() {}
+    explicit GlyphBox(const CollisionRect &bbox, const CollisionRect &box,
+                      float minScale)
+        : bbox(bbox), box(box), minScale(minScale) {}
+    explicit GlyphBox(const CollisionRect &box, float minScale, float maxScale,
+                      const CollisionAnchor &anchor, bool rotate)
+        : anchor(anchor),
+          box(box),
+          rotate(rotate),
+          minScale(minScale),
+          maxScale(maxScale) {}
+
+    CollisionAnchor anchor;
+    CollisionRect bbox;
+    CollisionRect box;
+    bool rotate = false;
+    float minScale = 0.0f;
+    float maxScale = std::numeric_limits<float>::infinity();
+};
+
+typedef std::vector<GlyphBox> GlyphBoxes;
+
+
+// TODO: Transform the vec2<float>s to vec2<int16_t> to save bytes
+struct PlacedGlyph {
+    explicit PlacedGlyph(const vec2<float> &tl, const vec2<float> &tr,
+                      const vec2<float> &bl, const vec2<float> &br,
+                      const Rect<uint16_t> &tex, float angle, const GlyphBox &glyphBox)
+        : tl(tl),
+          tr(tr),
+          bl(bl),
+          br(br),
+          tex(tex),
+          angle(angle),
+          glyphBox(glyphBox) {}
+
+    vec2<float> tl, tr, bl, br;
+    Rect<uint16_t> tex;
+    float angle;
+    GlyphBox glyphBox;
+};
+
+typedef std::vector<PlacedGlyph> PlacedGlyphs;
+
+// These are the placed boxes contained in the rtree.
+struct PlacementBox {
+    CollisionAnchor anchor;
+    CollisionRect bbox;
+    CollisionRect box;
+    bool rotate = false;
+    PlacementRange placementRange = {{0.0f, 0.0f}};
+    float placementScale = 0.0f;
+    float maxScale = std::numeric_limits<float>::infinity();
+    float padding = 0.0f;
+};
+
+struct PlacementProperty {
+    explicit PlacementProperty() {}
+    explicit PlacementProperty(float zoom, const PlacementRange &rotationRange)
+        : zoom(zoom), rotationRange(rotationRange) {}
+
+    inline operator bool() const {
+        return !isnan(zoom) && zoom != std::numeric_limits<float>::infinity() &&
+               rotationRange[0] != rotationRange[1];
+    }
+
+    float zoom = std::numeric_limits<float>::infinity();
+    PlacementRange rotationRange = {{0.0f, 0.0f}};
+};
+
+}
+
+#endif