diff options
author | Konstantin Käfer <mail@kkaefer.com> | 2014-12-04 18:29:42 +0100 |
---|---|---|
committer | Konstantin Käfer <mail@kkaefer.com> | 2014-12-04 20:02:50 +0100 |
commit | abafb52f37beb5659efc2105ccd1568e1f754898 (patch) | |
tree | 6a60636d3497560ca61e5aae5f6d7061c4f18553 /src/mbgl/text | |
parent | bff6aeb4da41dee1f5f1cfa0be81b6c257257253 (diff) | |
download | qtlocation-mapboxgl-abafb52f37beb5659efc2105ccd1568e1f754898.tar.gz |
make most headers private
Diffstat (limited to 'src/mbgl/text')
-rw-r--r-- | src/mbgl/text/collision.cpp | 297 | ||||
-rw-r--r-- | src/mbgl/text/collision.hpp | 58 | ||||
-rw-r--r-- | src/mbgl/text/glyph.cpp | 14 | ||||
-rw-r--r-- | src/mbgl/text/glyph.hpp | 60 | ||||
-rw-r--r-- | src/mbgl/text/glyph_store.cpp | 294 | ||||
-rw-r--r-- | src/mbgl/text/glyph_store.hpp | 99 | ||||
-rw-r--r-- | src/mbgl/text/placement.cpp | 312 | ||||
-rw-r--r-- | src/mbgl/text/placement.hpp | 31 | ||||
-rw-r--r-- | src/mbgl/text/rotation_range.cpp | 263 | ||||
-rw-r--r-- | src/mbgl/text/rotation_range.hpp | 54 | ||||
-rw-r--r-- | src/mbgl/text/types.hpp | 113 |
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 |