summaryrefslogtreecommitdiff
path: root/src/mbgl/text
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl/text')
-rw-r--r--src/mbgl/text/collision.cpp297
-rw-r--r--src/mbgl/text/collision.hpp58
-rw-r--r--src/mbgl/text/glyph.cpp14
-rw-r--r--src/mbgl/text/glyph.hpp60
-rw-r--r--src/mbgl/text/glyph_store.cpp294
-rw-r--r--src/mbgl/text/glyph_store.hpp99
-rw-r--r--src/mbgl/text/placement.cpp312
-rw-r--r--src/mbgl/text/placement.hpp31
-rw-r--r--src/mbgl/text/rotation_range.cpp263
-rw-r--r--src/mbgl/text/rotation_range.hpp54
-rw-r--r--src/mbgl/text/types.hpp113
11 files changed, 1595 insertions, 0 deletions
diff --git a/src/mbgl/text/collision.cpp b/src/mbgl/text/collision.cpp
new file mode 100644
index 0000000000..2e0ec6dce2
--- /dev/null
+++ b/src/mbgl/text/collision.cpp
@@ -0,0 +1,297 @@
+#include <mbgl/text/collision.hpp>
+#include <mbgl/text/rotation_range.hpp>
+#include <mbgl/util/math.hpp>
+
+
+using namespace mbgl;
+
+Box getBox(const CollisionAnchor &anchor, const CollisionRect &bbox, float minScale,
+ float maxScale) {
+ return Box{
+ Point{
+ anchor.x + util::min(bbox.tl.x / minScale, bbox.tl.x / maxScale),
+ anchor.y + util::min(bbox.tl.y / minScale, bbox.tl.y / maxScale),
+ },
+ Point{
+ anchor.x + util::max(bbox.br.x / minScale, bbox.br.x / maxScale),
+ anchor.y + util::max(bbox.br.y / minScale, bbox.br.y / maxScale),
+ },
+ };
+};
+
+Collision::Collision(float zoom_, float tileExtent, float tileSize, float placementDepth)
+ // tile pixels per screen pixels at the tile's zoom level
+ : tilePixelRatio(tileExtent / tileSize),
+
+ zoom(zoom_),
+
+ // Calculate the maximum scale we can go down in our fake-3d rtree so that
+ // placement still makes sense. This is calculated so that the minimum
+ // placement zoom can be at most 25.5 (we use an unsigned integer x10 to
+ // store the minimum zoom).
+ //
+ // We don't want to place labels all the way to 25.5. This lets too many
+ // glyphs be placed, slowing down collision checking. Only place labels if
+ // they will show up within the intended zoom range of the tile.
+ maxPlacementScale(std::exp(std::log(2) * util::min(3.0f, placementDepth, 25.5f - zoom_))) {
+ const float m = 4096;
+ const float edge = m * tilePixelRatio * 2;
+
+
+ PlacementBox left;
+ left.anchor = CollisionAnchor{ 0.0f, 0.0f };
+ left.box = CollisionRect{CollisionPoint{-edge, -edge}, CollisionPoint{0, edge}};
+ left.placementRange = {{ 2.0f * M_PI, 0.0f }};
+ left.placementScale = 0.5f;
+ left.maxScale = std::numeric_limits<float>::infinity();
+ left.padding = 0.0f;
+ leftEdge = PlacementValue{
+ getBox(left.anchor, left.box, left.placementScale, left.maxScale),
+ left};
+
+ PlacementBox top;
+ top.anchor = CollisionAnchor{ 0.0f, 0.0f };
+ top.box = CollisionRect{CollisionPoint{-edge, -edge}, CollisionPoint{edge, 0}};
+ top.placementRange = {{ 2.0f * M_PI, 0.0f }};
+ top.placementScale = 0.5f;
+ top.maxScale = std::numeric_limits<float>::infinity();
+ top.padding = 0.0f;
+ topEdge = PlacementValue{
+ getBox(top.anchor, top.box, top.placementScale, top.maxScale),
+ top};
+
+ PlacementBox bottom;
+ bottom.anchor = CollisionAnchor{ m, m };
+ bottom.box = CollisionRect{CollisionPoint{-edge, 0}, CollisionPoint{edge, edge}};
+ bottom.placementRange = {{ 2.0f * M_PI, 0.0f }};
+ bottom.placementScale = 0.5f;
+ bottom.maxScale = std::numeric_limits<float>::infinity();
+ bottom.padding = 0.0f;
+ bottomEdge = PlacementValue{
+ getBox(bottom.anchor, bottom.box, bottom.placementScale, bottom.maxScale),
+ bottom};
+
+ PlacementBox right;
+ right.anchor = CollisionAnchor{ m, m };
+ right.box = CollisionRect{CollisionPoint{0, -edge}, CollisionPoint{edge, edge}};
+ right.placementRange = {{ 2.0f * M_PI, 0.0f }};
+ right.placementScale = 0.5f;
+ right.maxScale = std::numeric_limits<float>::infinity();
+ right.padding = 0.0f;
+ rightEdge = PlacementValue{
+ getBox(right.anchor, right.box, right.placementScale, right.maxScale),
+ right};
+
+}
+
+GlyphBox getMergedGlyphs(const GlyphBoxes &boxes, const CollisionAnchor &anchor) {
+ GlyphBox mergedGlyphs;
+ const float inf = std::numeric_limits<float>::infinity();
+ mergedGlyphs.box = CollisionRect{{inf, inf}, {-inf, -inf}};
+ mergedGlyphs.anchor = anchor;
+
+ CollisionRect &box = mergedGlyphs.box;
+ for (const GlyphBox &glyph : boxes) {
+ 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);
+ }
+
+ return mergedGlyphs;
+}
+
+float Collision::getPlacementScale(const GlyphBoxes &glyphs, float minPlacementScale, bool avoidEdges) {
+
+ for (const GlyphBox &glyph : glyphs) {
+ const CollisionRect &box = glyph.box;
+ const CollisionRect &bbox = glyph.hBox ? glyph.hBox.get() : glyph.box;
+ const CollisionAnchor &anchor = glyph.anchor;
+ const float pad = glyph.padding;
+
+
+ if (anchor.x < 0 || anchor.x > 4096 || anchor.y < 0 || anchor.y > 4096) {
+ return 0;
+ }
+
+ float minScale = std::fmax(minPlacementScale, glyph.minScale);
+ float maxScale = glyph.maxScale != 0 ? glyph.maxScale : std::numeric_limits<float>::infinity();
+
+ if (minScale >= maxScale) {
+ continue;
+ }
+
+ // Compute the scaled bounding box of the unrotated glyph
+ const Box searchBox = getBox(anchor, bbox, minScale, maxScale);
+
+ std::vector<PlacementValue> blocking;
+ hTree.query(bgi::intersects(searchBox), std::back_inserter(blocking));
+ cTree.query(bgi::intersects(searchBox), std::back_inserter(blocking));
+
+ if (avoidEdges) {
+ if (searchBox.min_corner().get<0>() < 0) blocking.emplace_back(leftEdge);
+ if (searchBox.min_corner().get<1>() < 0) blocking.emplace_back(topEdge);
+ if (searchBox.max_corner().get<0>() >= 4096) blocking.emplace_back(rightEdge);
+ if (searchBox.max_corner().get<1>() >= 4096) blocking.emplace_back(bottomEdge);
+ }
+
+ if (blocking.size()) {
+ const CollisionAnchor &na = anchor; // new anchor
+ const CollisionRect &nb = box; // new box
+
+ for (const PlacementValue &value : blocking) {
+ const PlacementBox &placement = std::get<1>(value);
+ const CollisionAnchor &oa = placement.anchor; // old anchor
+ const CollisionRect &ob = placement.box; // old box
+
+ // If anchors are identical, we're going to skip the label.
+ // NOTE: this isn't right because there can be glyphs with
+ // the same anchor but differing box offsets.
+ if (na == oa) {
+ return 0;
+ }
+
+ // todo: unhardcode the 8 = tileExtent/tileSize
+ float padding = std::fmax(pad, placement.padding) * 8.0f;
+
+ // Original algorithm:
+ float s1 = (ob.tl.x - nb.br.x - padding) /
+ (na.x - oa.x); // scale at which new box is to the left of old box
+ float s2 = (ob.br.x - nb.tl.x + padding) /
+ (na.x - oa.x); // scale at which new box is to the right of old box
+ float s3 = (ob.tl.y - nb.br.y - padding) /
+ (na.y - oa.y); // scale at which new box is to the top of old box
+ float s4 = (ob.br.y - nb.tl.y + padding) /
+ (na.y - oa.y); // scale at which new box is to the bottom of old box
+
+ if (std::isnan(s1) || std::isnan(s2)) {
+ s1 = s2 = 1;
+ }
+ if (std::isnan(s3) || std::isnan(s4)) {
+ s3 = s4 = 1;
+ }
+
+ const float collisionFreeScale = std::fmin(std::fmax(s1, s2), std::fmax(s3, s4));
+
+ // Only update label's min scale if the glyph was
+ // restricted by a collision
+ if (collisionFreeScale > minPlacementScale &&
+ collisionFreeScale > minScale &&
+ collisionFreeScale < maxScale &&
+ collisionFreeScale < placement.maxScale) {
+ minPlacementScale = collisionFreeScale;
+ }
+
+ if (minPlacementScale > maxPlacementScale) {
+ return 0;
+ }
+ }
+ }
+ }
+
+ return minPlacementScale;
+}
+
+PlacementRange Collision::getPlacementRange(const GlyphBoxes &glyphs, float placementScale,
+ bool horizontal) {
+ PlacementRange placementRange = {{2.0f * M_PI, 0}};
+
+ for (const GlyphBox &glyph : glyphs) {
+ const CollisionRect &bbox = glyph.hBox ? glyph.hBox.get() : glyph.box;
+ const CollisionAnchor &anchor = glyph.anchor;
+
+ float minPlacedX = anchor.x + bbox.tl.x / placementScale;
+ float minPlacedY = anchor.y + bbox.tl.y / placementScale;
+ float maxPlacedX = anchor.x + bbox.br.x / placementScale;
+ float maxPlacedY = anchor.y + bbox.br.y / placementScale;
+
+ Box query_box{Point{minPlacedX, minPlacedY}, Point{maxPlacedX, maxPlacedY}};
+
+ std::vector<PlacementValue> blocking;
+ hTree.query(bgi::intersects(query_box), std::back_inserter(blocking));
+
+ if (horizontal) {
+ cTree.query(bgi::intersects(query_box), std::back_inserter(blocking));
+ }
+
+ for (const PlacementValue &value : blocking) {
+ const Box &s = std::get<0>(value);
+ const PlacementBox &b = std::get<1>(value);
+ const CollisionRect &bbox2 = b.hBox ? b.hBox.get() : b.box;
+
+ float x1, x2, y1, y2, intersectX, intersectY;
+
+ // Adjust and compare bboxes to see if the glyphs might intersect
+ if (placementScale > b.placementScale) {
+ x1 = b.anchor.x + bbox2.tl.x / placementScale;
+ y1 = b.anchor.y + bbox2.tl.y / placementScale;
+ x2 = b.anchor.x + bbox2.br.x / placementScale;
+ y2 = b.anchor.y + bbox2.br.y / placementScale;
+ intersectX = x1 < maxPlacedX && x2 > minPlacedX;
+ intersectY = y1 < maxPlacedY && y2 > minPlacedY;
+ } else {
+ x1 = anchor.x + bbox.tl.x / b.placementScale;
+ y1 = anchor.y + bbox.tl.y / b.placementScale;
+ x2 = anchor.x + bbox.br.x / b.placementScale;
+ y2 = anchor.y + bbox.br.y / b.placementScale;
+
+ intersectX = x1 < s.max_corner().get<0>() && x2 > s.min_corner().get<0>();
+ intersectY = y1 < s.max_corner().get<1>() && y2 > s.min_corner().get<1>();
+ }
+
+ // If they can't intersect, skip more expensive rotation calculation
+ if (!(intersectX && intersectY))
+ continue;
+
+ float scale = std::fmax(placementScale, b.placementScale);
+ // TODO? glyph.box or glyph.bbox?
+ CollisionRange range = rotationRange(glyph, b, scale);
+
+ placementRange[0] = std::fmin(placementRange[0], range[0]);
+ placementRange[1] = std::fmax(placementRange[1], range[1]);
+ }
+ }
+
+ return placementRange;
+};
+
+void Collision::insert(const GlyphBoxes &glyphs, const CollisionAnchor &anchor,
+ float placementScale, const PlacementRange &placementRange,
+ bool horizontal) {
+ assert(placementScale != std::numeric_limits<float>::infinity());
+
+ std::vector<PlacementValue> allBounds;
+ allBounds.reserve(glyphs.size());
+
+ for (const GlyphBox &glyph : glyphs) {
+ const CollisionRect &box = glyph.box;
+ const CollisionRect &bbox = glyph.hBox ? glyph.hBox.get() : glyph.box;
+
+ const float minScale = util::max(placementScale, glyph.minScale);
+ const float maxScale = glyph.maxScale != 0 ? glyph.maxScale : std::numeric_limits<float>::infinity();
+
+ const Box bounds = getBox(anchor, bbox, minScale, maxScale);
+
+ PlacementBox placement;
+ placement.anchor = anchor;
+ placement.box = box;
+ if (glyph.hBox) {
+ placement.hBox = bbox;
+ }
+ placement.placementRange = placementRange;
+ placement.placementScale = minScale;
+ placement.maxScale = maxScale;
+ placement.padding = glyph.padding;
+
+ allBounds.emplace_back(bounds, placement);
+ }
+
+ // Bulk-insert all glyph boxes
+ if (horizontal) {
+ hTree.insert(allBounds.begin(), allBounds.end());
+ } else {
+ cTree.insert(allBounds.begin(), allBounds.end());
+ }
+}
diff --git a/src/mbgl/text/collision.hpp b/src/mbgl/text/collision.hpp
new file mode 100644
index 0000000000..3bf37a6a12
--- /dev/null
+++ b/src/mbgl/text/collision.hpp
@@ -0,0 +1,58 @@
+#ifndef MBGL_TEXT_COLLISION
+#define MBGL_TEXT_COLLISION
+
+#include <mbgl/text/types.hpp>
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#pragma GCC diagnostic ignored "-Wunused-variable"
+#pragma GCC diagnostic ignored "-Wshadow"
+#ifdef __clang__
+#pragma GCC diagnostic ignored "-Wdeprecated-register"
+#else
+#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
+#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#endif
+#include <boost/geometry.hpp>
+#include <boost/geometry/geometries/point.hpp>
+#include <boost/geometry/geometries/box.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#pragma GCC diagnostic pop
+
+namespace mbgl {
+
+namespace bg = boost::geometry;
+namespace bgm = bg::model;
+namespace bgi = bg::index;
+typedef bgm::point<float, 2, bg::cs::cartesian> Point;
+typedef bgm::box<Point> Box;
+typedef std::pair<Box, PlacementBox> PlacementValue;
+typedef bgi::rtree<PlacementValue, bgi::linear<16,4>> Tree;
+
+class Collision {
+
+public:
+ Collision(float zoom, float tileExtent, float tileSize, float placementDepth = 1);
+
+ float getPlacementScale(const GlyphBoxes &glyphs, float minPlacementScale, bool avoidEdges);
+ PlacementRange getPlacementRange(const GlyphBoxes &glyphs, float placementScale,
+ bool horizontal);
+ void insert(const GlyphBoxes &glyphs, const CollisionAnchor &anchor, float placementScale,
+ const PlacementRange &placementRange, bool horizontal);
+
+private:
+ Tree hTree;
+ Tree cTree;
+ PlacementValue leftEdge;
+ PlacementValue topEdge;
+ PlacementValue rightEdge;
+ PlacementValue bottomEdge;
+
+public:
+ const float tilePixelRatio;
+ const float zoom;
+ const float maxPlacementScale;
+};
+}
+
+#endif
diff --git a/src/mbgl/text/glyph.cpp b/src/mbgl/text/glyph.cpp
new file mode 100644
index 0000000000..f02c710db2
--- /dev/null
+++ b/src/mbgl/text/glyph.cpp
@@ -0,0 +1,14 @@
+#include <mbgl/text/glyph.hpp>
+
+namespace mbgl {
+
+// Note: this only works for the BMP
+GlyphRange getGlyphRange(char32_t glyph) {
+ unsigned start = (glyph/256) * 256;
+ unsigned end = (start + 255);
+ if (start > 65280) start = 65280;
+ if (end > 65533) end = 65533;
+ return { start, end };
+}
+
+}
diff --git a/src/mbgl/text/glyph.hpp b/src/mbgl/text/glyph.hpp
new file mode 100644
index 0000000000..4fbb75fc1e
--- /dev/null
+++ b/src/mbgl/text/glyph.hpp
@@ -0,0 +1,60 @@
+#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 PositionedGlyph {
+public:
+ inline explicit PositionedGlyph(uint32_t glyph_, float x_, float y_)
+ : glyph(glyph_), x(x_), y(y_) {}
+
+ uint32_t glyph = 0;
+ float x = 0;
+ float y = 0;
+};
+
+typedef std::vector<PositionedGlyph> Shaping;
+}
+
+#endif
diff --git a/src/mbgl/text/glyph_store.cpp b/src/mbgl/text/glyph_store.cpp
new file mode 100644
index 0000000000..2f5db180fd
--- /dev/null
+++ b/src/mbgl/text/glyph_store.cpp
@@ -0,0 +1,294 @@
+#include <mbgl/text/glyph_store.hpp>
+
+#include <mbgl/util/std.hpp>
+#include <mbgl/util/string.hpp>
+#include <mbgl/util/utf.hpp>
+#include <mbgl/util/pbf.hpp>
+#include <mbgl/util/url.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/util/token.hpp>
+#include <mbgl/util/math.hpp>
+#include <mbgl/storage/file_source.hpp>
+#include <mbgl/platform/platform.hpp>
+#include <mbgl/util/uv_detail.hpp>
+#include <algorithm>
+
+namespace mbgl {
+
+
+void FontStack::insert(uint32_t id, const SDFGlyph &glyph) {
+ std::lock_guard<std::mutex> lock(mtx);
+ metrics.emplace(id, glyph.metrics);
+ bitmaps.emplace(id, glyph.bitmap);
+ sdfs.emplace(id, glyph);
+}
+
+const std::map<uint32_t, GlyphMetrics> &FontStack::getMetrics() const {
+ std::lock_guard<std::mutex> lock(mtx);
+ return metrics;
+}
+
+const std::map<uint32_t, SDFGlyph> &FontStack::getSDFs() const {
+ std::lock_guard<std::mutex> lock(mtx);
+ return sdfs;
+}
+
+const Shaping FontStack::getShaping(const std::u32string &string, const float maxWidth,
+ const float lineHeight, const float horizontalAlign,
+ const float verticalAlign, const float justify,
+ const float spacing, const vec2<float> &translate) const {
+ std::lock_guard<std::mutex> lock(mtx);
+
+ Shaping shaping;
+
+ int32_t x = std::round(translate.x * 24); // one em
+ const int32_t y = std::round(translate.y * 24); // one em
+
+ // Loop through all characters of this label and shape.
+ for (uint32_t chr : string) {
+ shaping.emplace_back(chr, x, y);
+ auto metric = metrics.find(chr);
+ if (metric != metrics.end()) {
+ x += metric->second.advance + spacing;
+ }
+ }
+
+ if (!shaping.size())
+ return shaping;
+
+ lineWrap(shaping, lineHeight, maxWidth, horizontalAlign, verticalAlign, justify);
+
+ return shaping;
+}
+
+void align(Shaping &shaping, const float justify, const float horizontalAlign,
+ const float verticalAlign, const uint32_t maxLineLength, const float lineHeight,
+ const uint32_t line) {
+ const float shiftX = (justify - horizontalAlign) * maxLineLength;
+ const float shiftY = (-verticalAlign * (line + 1) + 0.5) * lineHeight;
+
+ for (PositionedGlyph &glyph : shaping) {
+ glyph.x += shiftX;
+ glyph.y += shiftY;
+ }
+}
+
+void justifyLine(Shaping &shaping, const std::map<uint32_t, GlyphMetrics> &metrics, uint32_t start,
+ uint32_t end, float justify) {
+ PositionedGlyph &glyph = shaping[end];
+ auto metric = metrics.find(glyph.glyph);
+ if (metric != metrics.end()) {
+ const uint32_t lastAdvance = metric->second.advance;
+ const float lineIndent = float(glyph.x + lastAdvance) * justify;
+
+ for (uint32_t j = start; j <= end; j++) {
+ shaping[j].x -= lineIndent;
+ }
+ }
+}
+
+void FontStack::lineWrap(Shaping &shaping, const float lineHeight, const float maxWidth,
+ const float horizontalAlign, const float verticalAlign,
+ const float justify) const {
+ uint32_t lastSafeBreak = 0;
+
+ uint32_t lengthBeforeCurrentLine = 0;
+ uint32_t lineStartIndex = 0;
+ uint32_t line = 0;
+
+ uint32_t maxLineLength = 0;
+
+ if (maxWidth) {
+ for (uint32_t i = 0; i < shaping.size(); i++) {
+ PositionedGlyph &shape = shaping[i];
+
+ shape.x -= lengthBeforeCurrentLine;
+ shape.y += lineHeight * line;
+
+ if (shape.x > maxWidth && lastSafeBreak > 0) {
+
+ uint32_t lineLength = shaping[lastSafeBreak + 1].x;
+ maxLineLength = util::max(lineLength, maxLineLength);
+
+ for (uint32_t k = lastSafeBreak + 1; k <= i; k++) {
+ shaping[k].y += lineHeight;
+ shaping[k].x -= lineLength;
+ }
+
+ if (justify) {
+ justifyLine(shaping, metrics, lineStartIndex, lastSafeBreak - 1, justify);
+ }
+
+ lineStartIndex = lastSafeBreak + 1;
+ lastSafeBreak = 0;
+ lengthBeforeCurrentLine += lineLength;
+ line++;
+ }
+
+ if (shape.glyph == 32) {
+ lastSafeBreak = i;
+ }
+ }
+ }
+
+ if (!maxLineLength) maxLineLength = shaping.back().x;
+
+ justifyLine(shaping, metrics, lineStartIndex, uint32_t(shaping.size()) - 1, justify);
+ align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight, line);
+}
+
+GlyphPBF::GlyphPBF(const std::string &glyphURL, const std::string &fontStack, GlyphRange glyphRange, FileSource& fileSource)
+ : future(promise.get_future().share())
+{
+ // Load the glyph set URL
+ std::string url = util::replaceTokens(glyphURL, [&](const std::string &name) -> std::string {
+ if (name == "fontstack") return util::percentEncode(fontStack);
+ if (name == "range") return util::toString(glyphRange.first) + "-" + util::toString(glyphRange.second);
+ return "";
+ });
+
+ // The prepare call jumps back to the main thread.
+ fileSource.prepare([&, url] {
+ auto request = fileSource.request(ResourceType::Glyphs, url);
+ request->onload([&, url](const Response &res) {
+ if (res.code != 200) {
+ // Something went wrong with loading the glyph pbf. Pass on the error to the future listeners.
+ const std::string msg = std::string { "[ERROR] failed to load glyphs (" } + util::toString(res.code) + "): " + res.message;
+ promise.set_exception(std::make_exception_ptr(std::runtime_error(msg)));
+ } else {
+ // Transfer the data to the GlyphSet and signal its availability.
+ // Once it is available, the caller will need to call parse() to actually
+ // parse the data we received. We are not doing this here since this callback is being
+ // called from another (unknown) thread.
+ data = res.data;
+ promise.set_value(*this);
+ }
+ });
+ request->oncancel([&]() {
+ promise.set_exception(std::make_exception_ptr(std::runtime_error("Loading glyphs was canceled")));
+ });
+ });
+}
+
+std::shared_future<GlyphPBF &> GlyphPBF::getFuture() {
+ return future;
+}
+
+void GlyphPBF::parse(FontStack &stack) {
+ std::lock_guard<std::mutex> lock(mtx);
+
+ if (!data.size()) {
+ // If there is no data, this means we either haven't received any data, or
+ // we have already parsed the data.
+ return;
+ }
+
+ // Parse the glyph PBF
+ pbf glyphs_pbf(reinterpret_cast<const uint8_t *>(data.data()), data.size());
+
+ while (glyphs_pbf.next()) {
+ if (glyphs_pbf.tag == 1) { // stacks
+ pbf fontstack_pbf = glyphs_pbf.message();
+ while (fontstack_pbf.next()) {
+ if (fontstack_pbf.tag == 3) { // glyphs
+ pbf glyph_pbf = fontstack_pbf.message();
+
+ SDFGlyph glyph;
+
+ while (glyph_pbf.next()) {
+ if (glyph_pbf.tag == 1) { // id
+ glyph.id = glyph_pbf.varint();
+ } else if (glyph_pbf.tag == 2) { // bitmap
+ glyph.bitmap = glyph_pbf.string();
+ } else if (glyph_pbf.tag == 3) { // width
+ glyph.metrics.width = glyph_pbf.varint();
+ } else if (glyph_pbf.tag == 4) { // height
+ glyph.metrics.height = glyph_pbf.varint();
+ } else if (glyph_pbf.tag == 5) { // left
+ glyph.metrics.left = glyph_pbf.svarint();
+ } else if (glyph_pbf.tag == 6) { // top
+ glyph.metrics.top = glyph_pbf.svarint();
+ } else if (glyph_pbf.tag == 7) { // advance
+ glyph.metrics.advance = glyph_pbf.varint();
+ } else {
+ glyph_pbf.skip();
+ }
+ }
+
+ stack.insert(glyph.id, glyph);
+ } else {
+ fontstack_pbf.skip();
+ }
+ }
+ } else {
+ glyphs_pbf.skip();
+ }
+ }
+
+ data.clear();
+}
+
+GlyphStore::GlyphStore(FileSource& fileSource_) : fileSource(fileSource_) {}
+
+void GlyphStore::setURL(const std::string &url) {
+ glyphURL = url;
+}
+
+
+void GlyphStore::waitForGlyphRanges(const std::string &fontStack, const std::set<GlyphRange> &glyphRanges) {
+ // We are implementing a blocking wait with futures: Every GlyphSet has a future that we are
+ // waiting for until it is loaded.
+ if (glyphRanges.empty()) {
+ return;
+ }
+
+ FontStack *stack = nullptr;
+
+ std::vector<std::shared_future<GlyphPBF &>> futures;
+ futures.reserve(glyphRanges.size());
+ {
+ std::lock_guard<std::mutex> lock(mtx);
+ auto &rangeSets = ranges[fontStack];
+
+ stack = &createFontStack(fontStack);
+
+ // Attempt to load the glyph range. If the GlyphSet already exists, we are getting back
+ // the same shared_future.
+ for (GlyphRange range : glyphRanges) {
+ futures.emplace_back(loadGlyphRange(fontStack, rangeSets, range));
+ }
+ }
+
+ // Now that we potentially created all GlyphSets, we are waiting for the results, one by one.
+ // When we get a result (or the GlyphSet is aready loaded), we are attempting to parse the
+ // GlyphSet.
+ for (std::shared_future<GlyphPBF &> &future : futures) {
+ future.get().parse(*stack);
+ }
+}
+
+std::shared_future<GlyphPBF &> GlyphStore::loadGlyphRange(const std::string &fontStack, std::map<GlyphRange, std::unique_ptr<GlyphPBF>> &rangeSets, const GlyphRange range) {
+ auto range_it = rangeSets.find(range);
+ if (range_it == rangeSets.end()) {
+ // We don't have this glyph set yet for this font stack.
+ range_it = rangeSets.emplace(range, util::make_unique<GlyphPBF>(glyphURL, fontStack, range, fileSource)).first;
+ }
+
+ return range_it->second->getFuture();
+}
+
+FontStack &GlyphStore::createFontStack(const std::string &fontStack) {
+ auto stack_it = stacks.find(fontStack);
+ if (stack_it == stacks.end()) {
+ stack_it = stacks.emplace(fontStack, util::make_unique<FontStack>()).first;
+ }
+ return *stack_it->second.get();
+}
+
+FontStack &GlyphStore::getFontStack(const std::string &fontStack) {
+ std::lock_guard<std::mutex> lock(mtx);
+ return createFontStack(fontStack);
+}
+
+
+}
diff --git a/src/mbgl/text/glyph_store.hpp b/src/mbgl/text/glyph_store.hpp
new file mode 100644
index 0000000000..95ab92f307
--- /dev/null
+++ b/src/mbgl/text/glyph_store.hpp
@@ -0,0 +1,99 @@
+#ifndef MBGL_TEXT_GLYPH_STORE
+#define MBGL_TEXT_GLYPH_STORE
+
+#include <mbgl/text/glyph.hpp>
+#include <mbgl/util/pbf.hpp>
+#include <mbgl/util/vec.hpp>
+#include <mbgl/util/ptr.hpp>
+
+#include <cstdint>
+#include <vector>
+#include <future>
+#include <map>
+#include <set>
+#include <unordered_map>
+
+namespace mbgl {
+
+class FileSource;
+
+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, float maxWidth, float lineHeight,
+ float horizontalAlign, float verticalAlign, float justify,
+ float spacing, const vec2<float> &translate) const;
+ void lineWrap(Shaping &shaping, float lineHeight, float maxWidth, float horizontalAlign,
+ float verticalAlign, float justify) 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, FileSource& fileSource);
+
+private:
+ GlyphPBF(const GlyphPBF &) = delete;
+ GlyphPBF(GlyphPBF &&) = delete;
+ GlyphPBF &operator=(const GlyphPBF &) = delete;
+ GlyphPBF &operator=(GlyphPBF &&) = delete;
+
+public:
+ 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(FileSource& fileSource);
+
+ // 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);
+
+ void setURL(const std::string &url);
+
+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);
+
+ std::string glyphURL;
+ FileSource& fileSource;
+ 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/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
new file mode 100644
index 0000000000..84d4e20b2f
--- /dev/null
+++ b/src/mbgl/text/placement.cpp
@@ -0,0 +1,312 @@
+#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/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 StyleBucketSymbol &props) {
+ const float x = image.w / 2.0f; // No need to divide by image.pixelRatio here?
+ const float y = image.h / 2.0f; // image.pixelRatio;
+
+ const float dx = props.icon.offset.x;
+ const float dy = props.icon.offset.y;
+ float x1 = (dx - x);
+ float x2 = (dx + x);
+ float y1 = (dy - y);
+ float y2 = (dy + y);
+
+ vec2<float> tl{x1, y1};
+ vec2<float> tr{x2, y1};
+ vec2<float> br{x2, y2};
+ vec2<float> bl{x1, y2};
+
+ float angle = props.icon.rotate * M_PI / 180.0f;
+ if (anchor.segment >= 0 && props.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 */ props.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 StyleBucketSymbol &props) {
+ const float maxAngle = props.text.max_angle * M_PI / 180;
+ const float rotate = props.text.rotate * M_PI / 180;
+ const float padding = props.text.padding;
+ const bool alongLine = props.text.rotation_alignment != RotationAlignmentType::Viewport;
+ const bool keepUpright = props.text.keep_upright;
+
+ Placement placement;
+
+ const uint32_t buffer = 3;
+
+ for (const PositionedGlyph &shape : shaping) {
+ 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
new file mode 100644
index 0000000000..28eb8d5317
--- /dev/null
+++ b/src/mbgl/text/placement.hpp
@@ -0,0 +1,31 @@
+#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 StyleBucketSymbol;
+
+class Placement {
+public:
+ static Placement getIcon(Anchor &anchor, const Rect<uint16_t> &image, float iconBoxScale,
+ const std::vector<Coordinate> &line, const StyleBucketSymbol &props);
+
+ 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 StyleBucketSymbol &props);
+
+ static const float globalMinScale;
+
+ GlyphBoxes boxes;
+ PlacedGlyphs shapes;
+ float minScale;
+};
+}
+
+#endif
diff --git a/src/mbgl/text/rotation_range.cpp b/src/mbgl/text/rotation_range.cpp
new file mode 100644
index 0000000000..664ea9c709
--- /dev/null
+++ b/src/mbgl/text/rotation_range.cpp
@@ -0,0 +1,263 @@
+#include <mbgl/text/rotation_range.hpp>
+
+#include <mbgl/util/interpolate.hpp>
+
+#include <cassert>
+#include <algorithm>
+
+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) {
+ // find continuous interval including 0 that doesn't have any collisions
+ float min = 2.0f * M_PI;
+ float max = 0.0f;
+
+ for (CollisionRange collision : collisions) {
+ bool entryOutside =
+ ignoreRange[0] <= collision[0] && collision[0] <= ignoreRange[1];
+ bool exitOutside =
+ ignoreRange[0] <= collision[1] && collision[1] <= ignoreRange[1];
+
+ if (entryOutside && exitOutside) {
+ // no collision, since blocker is out of range
+ } else if (entryOutside) {
+ min = util::min(min, ignoreRange[1]);
+ max = util::max(max, collision[1]);
+ } else if (exitOutside) {
+ min = util::min(min, collision[0]);
+ max = util::max(max, ignoreRange[0]);
+ } else {
+ min = util::min(min, collision[0]);
+ max = util::max(max, collision[1]);
+ }
+ }
+
+ return {{min, max}};
+}
+
+/*
+ * Calculate collision ranges for two rotating boxes.
+ */
+CollisionList
+rotatingRotatingCollisions(const CollisionRect &a, const CollisionRect &b,
+ const CollisionAnchor &anchorToAnchor) {
+ const float d = util::mag<float>(anchorToAnchor);
+ const float d_sq = d * d;
+
+ const CollisionAnchor horizontal = {1, 0};
+ const float angleBetweenAnchors =
+ util::angle_between<float>(anchorToAnchor, horizontal);
+
+ // Calculate angles at which collisions may occur
+ const std::array<float, 8> c = {{
+ // top/bottom
+ /*[0]*/ static_cast<float>(std::asin((float)(a.br.y - b.tl.y) / d)),
+ /*[1]*/ static_cast<float>(std::asin((float)(a.br.y - b.tl.y) / d) + M_PI),
+ /*[2]*/ static_cast<float>(2 * M_PI -
+ std::asin((float)(-a.tl.y + b.br.y) / d)),
+ /*[3]*/ static_cast<float>(M_PI - std::asin((float)(-a.tl.y + b.br.y) / d)),
+
+ // left/right
+ /*[4]*/ static_cast<float>(2 * M_PI -
+ std::acos((float)(a.br.x - b.tl.x) / d)),
+ /*[5]*/ static_cast<float>(std::acos((float)(a.br.x - b.tl.x) / d)),
+ /*[6]*/ static_cast<float>(M_PI - std::acos((float)(-a.tl.x + b.br.x) / d)),
+ /*[7]*/ static_cast<float>(M_PI +
+ std::acos((float)(-a.tl.x + b.br.x) / d))}};
+
+ const float rl = a.br.x - b.tl.x;
+ const float lr = -a.tl.x + b.br.x;
+ const float tb = a.br.y - b.tl.y;
+ const float bt = -a.tl.y + b.br.y;
+
+ // Calculate the distance squared of the diagonal which will be used
+ // to check if the boxes are close enough for collisions to occur at each
+ // angle
+ // todo, triple check these
+ const std::array<float, 8> e = {{
+ // top/bottom
+ /*[0]*/ static_cast<float>(rl * rl + tb * tb),
+ /*[1]*/ static_cast<float>(lr * lr + tb * tb),
+ /*[2]*/ static_cast<float>(rl * rl + bt * bt),
+ /*[3]*/ static_cast<float>(lr * lr + bt * bt),
+
+ // left/right
+ /*[4]*/ static_cast<float>(rl * rl + tb * tb),
+ /*[5]*/ static_cast<float>(rl * rl + bt * bt),
+ /*[6]*/ static_cast<float>(lr * lr + bt * bt),
+ /*[7]*/ static_cast<float>(lr * lr + tb * tb)}};
+
+ std::vector<float> f;
+ for (size_t i = 0; i < c.size(); i++) {
+ // Check if they are close enough to collide
+ if (!std::isnan(c[i]) && d_sq <= e[i]) {
+ // So far, angles have been calulated as relative to the vector
+ // between anchors.
+ // Convert the angles to angles from north.
+ f.push_back(
+ std::fmod((c[i] + angleBetweenAnchors + 2 * M_PI), (2 * M_PI)));
+ }
+ }
+
+ assert(f.size() % 2 == 0);
+
+ // Group the collision angles by two
+ // each group represents a range where the two boxes collide
+ CollisionList collisions;
+ std::sort(f.begin(), f.end());
+ for (size_t k = 0; k < f.size(); k += 2) {
+ collisions.push_back({{f[k], f[k + 1]}});
+ }
+
+ return collisions;
+}
+
+double getAngle(const CollisionPoint &p1, const CollisionPoint &p2,
+ CollisionAngle d, const CollisionPoint &corner) {
+ return std::fmod(util::angle_between(util::interpolate(p1.x, p2.x, d),
+ util::interpolate(p1.y, p2.y, d), corner.x,
+ corner.y) +
+ 2 * M_PI,
+ 2 * M_PI);
+}
+
+/*
+ * 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) {
+ const CollisionPoint::Type edgeX = p2.x - p1.x;
+ const CollisionPoint::Type edgeY = p2.y - p1.y;
+
+ const CollisionAngle a = edgeX * edgeX + edgeY * edgeY;
+ const CollisionAngle b = (edgeX * p1.x + edgeY * p1.y) * 2;
+ const CollisionAngle c = p1.x * p1.x + p1.y * p1.y - radius * radius;
+
+ const CollisionAngle discriminant = b * b - 4 * a * c;
+
+ // a collision exists only if line intersects circle at two points
+ if (discriminant > 0) {
+ CollisionAngle x1 = (-b - std::sqrt(discriminant)) / (2 * a);
+ CollisionAngle x2 = (-b + std::sqrt(discriminant)) / (2 * a);
+
+ // only add points if within line segment
+ // hack to handle floating point representations of 0 and 1
+ if (0 < x1 && x1 < 1) {
+ angles = getAngle(p1, p2, x1, corner);
+ }
+
+ if (0 < x2 && x2 < 1) {
+ angles = getAngle(p1, p2, x2, corner);
+ }
+ }
+}
+
+/*
+ * 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) {
+ float radius = util::mag<float>(corner);
+
+ CollisionAngles angles;
+
+ // Calculate the points at which the corners intersect with the edges
+ for (size_t i = 0, j = 3; i < 4; j = i++) {
+ circleEdgeCollisions(std::back_inserter(angles), corner, radius,
+ boxCorners[j], boxCorners[i]);
+ }
+
+ if (angles.size() % 2 != 0) {
+ // TODO fix
+ // This could get hit when a point intersects very close to a corner
+ // and floating point issues cause only one of the entry or exit to be
+ // counted
+ throw std::runtime_error("expecting an even number of intersections");
+ }
+
+ std::sort(angles.begin(), angles.end());
+
+ // Group by pairs, where each represents a range where a collision occurs
+ for (size_t k = 0; k < angles.size(); k += 2) {
+ CollisionRange range = {{angles[k], angles[k + 1]}};
+ if (flip) {
+ range = util::flip(range);
+ }
+ collisions = range;
+ }
+}
+
+CollisionCorners getCorners(const CollisionRect &a) {
+ return {{{a.tl.x, a.tl.y},
+ {a.tl.x, a.br.y},
+ {a.br.x, a.br.y},
+ {a.br.x, a.tl.y}}};
+}
+
+/*
+ * Calculate collision ranges for a rotating box and a fixed box;
+ */
+CollisionList rotatingFixedCollisions(const CollisionRect &rotating,
+ const CollisionRect &fixed) {
+ const auto cornersR = getCorners(rotating);
+ const auto cornersF = getCorners(fixed);
+
+ // A collision occurs when, and only at least one corner from one of the
+ // boxes is within the other box. Calculate these ranges for each corner.
+
+ CollisionList collisions;
+
+ for (size_t i = 0; i < 4; i++) {
+ cornerBoxCollisions(std::back_inserter(collisions), cornersR[i],
+ cornersF);
+ cornerBoxCollisions(std::back_inserter(collisions), cornersF[i],
+ cornersR, true);
+ }
+
+ return collisions;
+}
+
+/*
+ * Calculate the range a box conflicts with a second box
+ */
+CollisionRange rotationRange(const GlyphBox &inserting,
+ const PlacementBox &blocker, float scale) {
+ CollisionList collisions;
+
+ const GlyphBox &a = inserting;
+ const PlacementBox &b = blocker;
+
+ // Instead of scaling the boxes, we move the anchors
+ CollisionAnchor relativeAnchor{
+ static_cast<float>((b.anchor.x - a.anchor.x) * scale),
+ static_cast<float>((b.anchor.y - a.anchor.y) * scale)};
+
+ // Generate a list of collision interval
+ if (a.hBox && b.hBox) {
+ collisions = rotatingRotatingCollisions(a.box, b.box, relativeAnchor);
+ } else if (a.hBox) {
+ const CollisionRect box {
+ b.box.tl.x + relativeAnchor.x, b.box.tl.y + relativeAnchor.y,
+ b.box.br.x + relativeAnchor.x, b.box.br.y + relativeAnchor.y};
+ collisions = rotatingFixedCollisions(a.box, box);
+ } else if (b.hBox) {
+ const CollisionRect box {
+ a.box.tl.x - relativeAnchor.x, a.box.tl.y - relativeAnchor.y,
+ a.box.br.x - relativeAnchor.x, a.box.br.y - relativeAnchor.y};
+ collisions = rotatingFixedCollisions(b.box, box);
+ } else {
+ // collisions remains empty
+ }
+
+ // Find and return the continous are around 0 where there are no collisions
+ return mergeCollisions(collisions, blocker.placementRange);
+}
+}
diff --git a/src/mbgl/text/rotation_range.hpp b/src/mbgl/text/rotation_range.hpp
new file mode 100644
index 0000000000..4968fda164
--- /dev/null
+++ b/src/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/src/mbgl/text/types.hpp b/src/mbgl/text/types.hpp
new file mode 100644
index 0000000000..23f49aa748
--- /dev/null
+++ b/src/mbgl/text/types.hpp
@@ -0,0 +1,113 @@
+#ifndef MBGL_TEXT_TYPES
+#define MBGL_TEXT_TYPES
+
+#include <mbgl/util/vec.hpp>
+#include <mbgl/util/rect.hpp>
+#include <mbgl/util/optional.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 &box_,
+ const CollisionAnchor &anchor_,
+ float minScale_,
+ float maxScale_,
+ float padding_)
+ : box(box_), anchor(anchor_), minScale(minScale_), maxScale(maxScale_), padding(padding_) {}
+ explicit GlyphBox(const CollisionRect &box_,
+ float minScale_,
+ float padding_)
+ : box(box_), minScale(minScale_), padding(padding_) {}
+
+ CollisionRect box;
+ CollisionAnchor anchor;
+ float minScale = 0.0f;
+ float maxScale = std::numeric_limits<float>::infinity();
+ float padding = 0.0f;
+ mapbox::util::optional<CollisionRect> hBox;
+};
+
+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 vec2<float> &anchor_,
+ float minScale_, float maxScale_)
+ : tl(tl_),
+ tr(tr_),
+ bl(bl_),
+ br(br_),
+ tex(tex_),
+ angle(angle_),
+ anchor(anchor_),
+ minScale(minScale_),
+ maxScale(maxScale_) {}
+
+ vec2<float> tl, tr, bl, br;
+ Rect<uint16_t> tex;
+ float angle;
+ vec2<float> anchor;
+ float minScale, maxScale;
+};
+
+typedef std::vector<PlacedGlyph> PlacedGlyphs;
+
+// These are the placed boxes contained in the rtree.
+struct PlacementBox {
+ CollisionAnchor anchor;
+ CollisionRect box;
+ mapbox::util::optional<CollisionRect> hBox;
+ 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 !std::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
View Lorry Controller Status