diff options
Diffstat (limited to 'src')
68 files changed, 1658 insertions, 1588 deletions
diff --git a/src/mbgl/geometry/anchor.hpp b/src/mbgl/geometry/anchor.hpp index d30394f0b9..352f260752 100644 --- a/src/mbgl/geometry/anchor.hpp +++ b/src/mbgl/geometry/anchor.hpp @@ -16,10 +16,11 @@ struct Anchor { : x(x_), y(y_), angle(angle_), scale(scale_) {} explicit Anchor(float x_, float y_, float angle_, float scale_, int segment_) : x(x_), y(y_), angle(angle_), scale(scale_), segment(segment_) {} + }; typedef std::vector<Anchor> Anchors; } -#endif
\ No newline at end of file +#endif diff --git a/src/mbgl/geometry/collision_box_buffer.cpp b/src/mbgl/geometry/collision_box_buffer.cpp new file mode 100644 index 0000000000..050a999db8 --- /dev/null +++ b/src/mbgl/geometry/collision_box_buffer.cpp @@ -0,0 +1,27 @@ +#include <mbgl/geometry/collision_box_buffer.hpp> +#include <mbgl/platform/gl.hpp> +#include <mbgl/util/math.hpp> + +#include <cmath> + +namespace mbgl { + +size_t CollisionBoxVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, float maxzoom, float placementZoom) { + const size_t idx = index(); + void *data = addElement(); + + int16_t *shorts = static_cast<int16_t *>(data); + shorts[0] /* pos */ = x; + shorts[1] /* pos */ = y; + shorts[2] /* offset */ = std::round(ox); // use 1/64 pixels for placement + shorts[3] /* offset */ = std::round(oy); + + uint8_t *ubytes = static_cast<uint8_t *>(data); + // a_data1 + ubytes[8] = maxzoom * 10; + ubytes[9] = placementZoom * 10; + + return idx; +} + +} diff --git a/src/mbgl/geometry/collision_box_buffer.hpp b/src/mbgl/geometry/collision_box_buffer.hpp new file mode 100644 index 0000000000..098eab13c6 --- /dev/null +++ b/src/mbgl/geometry/collision_box_buffer.hpp @@ -0,0 +1,23 @@ +#ifndef MBGL_GEOMETRY_COLLISIONBOX_BUFFER +#define MBGL_GEOMETRY_COLLISIONBOX_BUFFER + +#include <mbgl/geometry/buffer.hpp> +#include <array> + +namespace mbgl { + +class CollisionBoxVertexBuffer : public Buffer < + 12, + GL_ARRAY_BUFFER, + 32768 +> { +public: + typedef int16_t vertex_type; + + size_t add(int16_t x, int16_t y, float ex, float ey, float maxzoom, float placementZoom); +}; + + +} + +#endif diff --git a/src/mbgl/geometry/icon_buffer.cpp b/src/mbgl/geometry/icon_buffer.cpp index 5e7b76fde2..2ca15b6c5c 100644 --- a/src/mbgl/geometry/icon_buffer.cpp +++ b/src/mbgl/geometry/icon_buffer.cpp @@ -6,9 +6,7 @@ namespace mbgl { -const double IconVertexBuffer::angleFactor = 128.0 / M_PI; - -size_t IconVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, int16_t tx, int16_t ty, float angle, float minzoom, std::array<float, 2> range, float maxzoom, float labelminzoom) { +size_t IconVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, int16_t tx, int16_t ty, float minzoom, float maxzoom, float labelminzoom) { const size_t idx = index(); void *data = addElement(); @@ -23,13 +21,10 @@ size_t IconVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, int16_t t ubytes[8] /* tex */ = tx / 4; ubytes[9] /* tex */ = ty / 4; ubytes[10] /* labelminzoom */ = labelminzoom * 10; - ubytes[11] /* angle */ = (int16_t)std::round(angle * angleFactor) % 256; // a_data2 ubytes[12] /* minzoom */ = minzoom * 10; // 1/10 zoom levels: z16 == 160. ubytes[13] /* maxzoom */ = std::fmin(maxzoom, 25) * 10; // 1/10 zoom levels: z16 == 160. - ubytes[14] /* rangeend */ = util::max((int16_t)std::round(range[0] * angleFactor), (int16_t)0) % 256; - ubytes[15] /* rangestart */ = util::min((int16_t)std::round(range[1] * angleFactor), (int16_t)255) % 256; return idx; } diff --git a/src/mbgl/geometry/icon_buffer.hpp b/src/mbgl/geometry/icon_buffer.hpp index 90ce19b1ed..95469929cf 100644 --- a/src/mbgl/geometry/icon_buffer.hpp +++ b/src/mbgl/geometry/icon_buffer.hpp @@ -11,9 +11,7 @@ namespace mbgl { 16 > { public: - static const double angleFactor; - - size_t add(int16_t x, int16_t y, float ox, float oy, int16_t tx, int16_t ty, float angle, float minzoom, std::array<float, 2> range, float maxzoom, float labelminzoom); + size_t add(int16_t x, int16_t y, float ox, float oy, int16_t tx, int16_t ty, float minzoom, float maxzoom, float labelminzoom); }; diff --git a/src/mbgl/geometry/resample.cpp b/src/mbgl/geometry/resample.cpp deleted file mode 100644 index ed086fefd4..0000000000 --- a/src/mbgl/geometry/resample.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include <mbgl/geometry/resample.hpp> - -#include <mbgl/util/interpolate.hpp> - -#include <cmath> - -namespace mbgl { - -const float minScale = 0.5f; -const std::array<std::vector<float>, 4> minScaleArrays = {{ - /*1:*/ { minScale }, - /*2:*/ { minScale, 2 }, - /*4:*/ { minScale, 4, 2, 4 }, - /*8:*/ { minScale, 8, 4, 8, 2, 8, 4, 8 } -}}; - - -Anchors resample(const std::vector<Coordinate> &vertices, float spacing, - const float /*minScale*/, float maxScale, const float tilePixelRatio, - float offset) { - - maxScale = std::round(std::fmax(std::fmin(8.0f, maxScale / 2.0f), 1.0f)); - spacing *= tilePixelRatio / maxScale; - offset *= tilePixelRatio; - const size_t index = util::clamp<size_t>(std::floor(std::log(maxScale) / std::log(2)), 0, minScaleArrays.size() - 1); - const std::vector<float> &minScales = minScaleArrays[index]; - const size_t len = minScales.size(); - - float distance = 0.0f; - float markedDistance = offset != 0.0f ? offset - spacing : offset; - int added = 0; - - Anchors points; - - auto end = vertices.end() - 1; - int i = 0; - for (auto it = vertices.begin(); it != end; it++, i++) { - const Coordinate &a = *(it), b = *(it + 1); - - float segmentDist = util::dist<float>(a, b); - float angle = util::angle_to(b, a); - - while (markedDistance + spacing < distance + segmentDist) { - markedDistance += spacing; - - float t = (markedDistance - distance) / segmentDist, - x = util::interpolate(a.x, b.x, t), - y = util::interpolate(a.y, b.y, t), - s = minScales[added % len]; - - if (x >= 0 && x < 4096 && y >= 0 && y < 4096) { - points.emplace_back(x, y, angle, s, i); - } - - added++; - } - - distance += segmentDist; - } - - return points; -} -} diff --git a/src/mbgl/geometry/resample.hpp b/src/mbgl/geometry/resample.hpp deleted file mode 100644 index ce7eba2f1b..0000000000 --- a/src/mbgl/geometry/resample.hpp +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef MBGL_GEOMETRY_INTERPOLATE -#define MBGL_GEOMETRY_INTERPOLATE - -#include <mbgl/geometry/anchor.hpp> -#include <mbgl/util/math.hpp> - -namespace mbgl { - -Anchors resample(const std::vector<Coordinate> &vertices, float spacing, - float minScale, float maxScale, float tilePixelRatio, float offset); -} - -#endif diff --git a/src/mbgl/geometry/text_buffer.cpp b/src/mbgl/geometry/text_buffer.cpp index e9bfc503be..e3f7117eb0 100644 --- a/src/mbgl/geometry/text_buffer.cpp +++ b/src/mbgl/geometry/text_buffer.cpp @@ -6,9 +6,7 @@ namespace mbgl { -const double TextVertexBuffer::angleFactor = 128.0 / M_PI; - -size_t TextVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, uint16_t tx, uint16_t ty, float angle, float minzoom, std::array<float, 2> range, float maxzoom, float labelminzoom) { +size_t TextVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, uint16_t tx, uint16_t ty, float minzoom, float maxzoom, float labelminzoom) { const size_t idx = index(); void *data = addElement(); @@ -23,13 +21,10 @@ size_t TextVertexBuffer::add(int16_t x, int16_t y, float ox, float oy, uint16_t ubytes[8] /* tex */ = tx / 4; ubytes[9] /* tex */ = ty / 4; ubytes[10] /* labelminzoom */ = labelminzoom * 10; - ubytes[11] /* angle */ = (int16_t)std::round(angle * angleFactor) % 256; // a_data2 ubytes[12] /* minzoom */ = minzoom * 10; // 1/10 zoom levels: z16 == 160. ubytes[13] /* maxzoom */ = std::fmin(maxzoom, 25) * 10; // 1/10 zoom levels: z16 == 160. - ubytes[14] /* rangeend */ = util::max((int16_t)std::round(range[0] * angleFactor), (int16_t)0) % 256; - ubytes[15] /* rangestart */ = util::min((int16_t)std::round(range[1] * angleFactor), (int16_t)255) % 256; return idx; } diff --git a/src/mbgl/geometry/text_buffer.hpp b/src/mbgl/geometry/text_buffer.hpp index 4687b32f97..895d472376 100644 --- a/src/mbgl/geometry/text_buffer.hpp +++ b/src/mbgl/geometry/text_buffer.hpp @@ -14,9 +14,7 @@ class TextVertexBuffer : public Buffer < public: typedef int16_t vertex_type; - static const double angleFactor; - - size_t add(int16_t x, int16_t y, float ox, float oy, uint16_t tx, uint16_t ty, float angle, float minzoom, std::array<float, 2> range, float maxzoom, float labelminzoom); + size_t add(int16_t x, int16_t y, float ox, float oy, uint16_t tx, uint16_t ty, float minzoom, float maxzoom, float labelminzoom); }; diff --git a/src/mbgl/map/annotation.cpp b/src/mbgl/map/annotation.cpp index d30052c94a..6df49ec647 100644 --- a/src/mbgl/map/annotation.cpp +++ b/src/mbgl/map/annotation.cpp @@ -124,7 +124,7 @@ AnnotationManager::addPointAnnotations(const std::vector<LatLng>& points, uint32_t y = p.y * z2; for (int8_t z = maxZoom; z >= 0; z--) { - affectedTiles.emplace_back(z, x, y); + affectedTiles.emplace_back(z, x, y, z); TileID tileID = affectedTiles.back(); // calculate tile coordinate @@ -213,7 +213,7 @@ std::vector<TileID> AnnotationManager::removeAnnotations(const AnnotationIDs& id p = projectPoint(latLng); x = z2s[z] * p.x; y = z2s[z] * p.y; - TileID tid(z, x, y); + TileID tid(z, x, y, z); // erase annotation from tile's list auto& tileAnnotations = tiles[tid].first; tileAnnotations.erase(annotationID); @@ -244,8 +244,8 @@ std::vector<uint32_t> AnnotationManager::getAnnotationsInBounds(const LatLngBoun const vec2<double> nePoint = projectPoint(queryBounds.ne); // tiles number y from top down - const TileID nwTile(z, swPoint.x * z2, nePoint.y * z2); - const TileID seTile(z, nePoint.x * z2, swPoint.y * z2); + const TileID nwTile(z, swPoint.x * z2, nePoint.y * z2, z); + const TileID seTile(z, nePoint.x * z2, swPoint.y * z2, z); std::vector<uint32_t> matchingAnnotations; diff --git a/src/mbgl/map/live_tile_data.cpp b/src/mbgl/map/live_tile_data.cpp index 59f7b4de3d..1d8c42e1e4 100644 --- a/src/mbgl/map/live_tile_data.cpp +++ b/src/mbgl/map/live_tile_data.cpp @@ -10,15 +10,17 @@ using namespace mbgl; LiveTileData::LiveTileData(const TileID& id_, AnnotationManager& annotationManager_, - float mapMaxZoom, Style& style_, GlyphAtlas& glyphAtlas_, GlyphStore& glyphStore_, SpriteAtlas& spriteAtlas_, util::ptr<Sprite> sprite_, - const SourceInfo& source_) - : VectorTileData::VectorTileData(id_, mapMaxZoom, style_, glyphAtlas_, glyphStore_, - spriteAtlas_, sprite_, source_), + const SourceInfo& source_, + float overscaling_, + float angle_, + bool collisionDebug_) + : VectorTileData::VectorTileData(id_, style_, glyphAtlas_, glyphStore_, + spriteAtlas_, sprite_, source_, overscaling_, angle_, collisionDebug_), annotationManager(annotationManager_) { // live features are always ready setState(State::loaded); diff --git a/src/mbgl/map/live_tile_data.hpp b/src/mbgl/map/live_tile_data.hpp index e56a7bf7e1..4dfe832f64 100644 --- a/src/mbgl/map/live_tile_data.hpp +++ b/src/mbgl/map/live_tile_data.hpp @@ -11,13 +11,15 @@ class LiveTileData : public VectorTileData { public: LiveTileData(const TileID&, AnnotationManager&, - float mapMaxZoom, Style&, GlyphAtlas&, GlyphStore&, SpriteAtlas&, util::ptr<Sprite>, - const SourceInfo&); + const SourceInfo&, + float overscaling_, + float angle_, + bool collisionDebug_); ~LiveTileData(); void parse() override; diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp index 026297fb46..0479189300 100644 --- a/src/mbgl/map/map.cpp +++ b/src/mbgl/map/map.cpp @@ -278,6 +278,20 @@ bool Map::getDebug() const { return data->getDebug(); } +void Map::setCollisionDebug(bool value) { + data->setCollisionDebug(value); + update(); +} + +void Map::toggleCollisionDebug() { + data->toggleCollisionDebug(); + update(); +} + +bool Map::getCollisionDebug() const { + return data->getCollisionDebug(); +} + bool Map::isFullyLoaded() const { return data->getFullyLoaded(); } diff --git a/src/mbgl/map/map_data.cpp b/src/mbgl/map/map_data.cpp index 23bc094990..993edb38e8 100644 --- a/src/mbgl/map/map_data.cpp +++ b/src/mbgl/map/map_data.cpp @@ -41,4 +41,4 @@ std::vector<std::string> MapData::getClasses() const { return classes; } -}
\ No newline at end of file +} diff --git a/src/mbgl/map/map_data.hpp b/src/mbgl/map/map_data.hpp index 02519a0d38..32722d07e8 100644 --- a/src/mbgl/map/map_data.hpp +++ b/src/mbgl/map/map_data.hpp @@ -55,6 +55,16 @@ public: debug = value; } + inline bool getCollisionDebug() const { + return collisionDebug; + } + inline bool toggleCollisionDebug() { + return collisionDebug ^= 1u; + } + inline void setCollisionDebug(bool value) { + collisionDebug = value; + } + inline bool getFullyLoaded() const { return loaded; } @@ -88,6 +98,7 @@ private: std::vector<std::string> classes; std::atomic<uint8_t> debug { false }; + std::atomic<uint8_t> collisionDebug { false }; std::atomic<bool> loaded { false }; std::atomic<Duration> animationTime; std::atomic<Duration> defaultTransitionDuration; diff --git a/src/mbgl/map/source.cpp b/src/mbgl/map/source.cpp index faae3285fe..ae39b84ee3 100644 --- a/src/mbgl/map/source.cpp +++ b/src/mbgl/map/source.cpp @@ -101,7 +101,7 @@ std::string SourceInfo::tileURL(const TileID& id, float pixelRatio) const { std::string result = tiles.at((id.x + id.y) % tiles.size()); result = util::mapbox::normalizeTileURL(result, url, type); result = util::replaceTokens(result, [&](const std::string &token) -> std::string { - if (token == "z") return util::toString(id.z); + if (token == "z") return util::toString(std::min(id.z, static_cast<int8_t>(max_zoom))); if (token == "x") return util::toString(id.x); if (token == "y") return util::toString(id.y); if (token == "prefix") { @@ -177,7 +177,7 @@ void Source::load() { void Source::updateMatrices(const mat4 &projMatrix, const TransformState &transform) { for (const auto& pair : tiles) { Tile &tile = *pair.second; - transform.matrixFor(tile.matrix, tile.id); + transform.matrixFor(tile.matrix, tile.id, std::min(static_cast<int8_t>(info.max_zoom), tile.id.z)); matrix::multiply(tile.matrix, projMatrix, tile.matrix); } } @@ -265,7 +265,9 @@ TileData::State Source::addTile(MapData& data, return state; } + const float overscaling = id.z > info.max_zoom ? std::pow(2.0f, id.z - info.max_zoom) : 1.0f; auto pos = tiles.emplace(id, std::make_unique<Tile>(id)); + Tile& new_tile = *pos.first->second; // We couldn't find the tile in the list. Create a new one. @@ -288,23 +290,24 @@ TileData::State Source::addTile(MapData& data, } if (!new_tile.data) { - auto callback = std::bind(&Source::tileLoadingCompleteCallback, this, normalized_id); + auto callback = std::bind(&Source::tileLoadingCompleteCallback, this, normalized_id, transformState, data.getCollisionDebug()); // If we don't find working tile data, we're just going to load it. if (info.type == SourceType::Vector) { new_tile.data = - std::make_shared<VectorTileData>(normalized_id, data.transform.getMaxZoom(), style, glyphAtlas, - glyphStore, spriteAtlas, sprite, info); - new_tile.data->request( - style.workers, transformState.getPixelRatio(), callback); + std::make_shared<VectorTileData>(normalized_id, style, glyphAtlas, + glyphStore, spriteAtlas, sprite, info, + overscaling, transformState.getAngle(), data.getCollisionDebug()); + new_tile.data->request(style.workers, transformState.getPixelRatio(), callback); } else if (info.type == SourceType::Raster) { new_tile.data = std::make_shared<RasterTileData>(normalized_id, texturePool, info); new_tile.data->request( style.workers, transformState.getPixelRatio(), callback); } else if (info.type == SourceType::Annotations) { new_tile.data = std::make_shared<LiveTileData>(normalized_id, data.annotationManager, - data.transform.getMaxZoom(), style, glyphAtlas, - glyphStore, spriteAtlas, sprite, info); + style, glyphAtlas, + glyphStore, spriteAtlas, sprite, info, + overscaling, transformState.getAngle(), data.getCollisionDebug()); new_tile.data->reparse(style.workers, callback); } else { throw std::runtime_error("source type not implemented"); @@ -327,6 +330,11 @@ int32_t Source::coveringZoomLevel(const TransformState& state) const { std::forward_list<TileID> Source::coveringTiles(const TransformState& state) const { int32_t z = coveringZoomLevel(state); + auto actualZ = z; + const bool reparseOverscaled = + info.type == SourceType::Vector || + info.type == SourceType::Annotations; + if (z < info.min_zoom) return {{}}; if (z > info.max_zoom) z = info.max_zoom; @@ -334,7 +342,7 @@ std::forward_list<TileID> Source::coveringTiles(const TransformState& state) con box points = state.cornersToBox(z); const vec2<double>& center = points.center; - std::forward_list<TileID> covering_tiles = tileCover(z, points); + std::forward_list<TileID> covering_tiles = tileCover(z, points, reparseOverscaled ? actualZ : z); covering_tiles.sort([¢er](const TileID& a, const TileID& b) { // Sorts by distance from the box center @@ -357,7 +365,7 @@ std::forward_list<TileID> Source::coveringTiles(const TransformState& state) con bool Source::findLoadedChildren(const TileID& id, int32_t maxCoveringZoom, std::forward_list<TileID>& retain) { bool complete = true; int32_t z = id.z; - auto ids = id.children(z + 1); + auto ids = id.children(info.max_zoom); for (const auto& child_id : ids) { const TileData::State state = hasTile(child_id); if (TileData::isReadyState(state)) { @@ -384,7 +392,7 @@ bool Source::findLoadedChildren(const TileID& id, int32_t maxCoveringZoom, std:: */ bool Source::findLoadedParent(const TileID& id, int32_t minCoveringZoom, std::forward_list<TileID>& retain) { for (int32_t z = id.z - 1; z >= minCoveringZoom; --z) { - const TileID parent_id = id.parent(z); + const TileID parent_id = id.parent(z, info.max_zoom); const TileData::State state = hasTile(parent_id); if (TileData::isReadyState(state)) { retain.emplace_front(parent_id); @@ -505,6 +513,10 @@ bool Source::update(MapData& data, updateTilePtrs(); + for (auto& tilePtr : tilePtrs) { + tilePtr->data->redoPlacement(transformState.getAngle(), data.getCollisionDebug()); + } + updated = data.getAnimationTime(); return allTilesUpdated; @@ -538,7 +550,7 @@ void Source::setObserver(Observer* observer) { observer_ = observer; } -void Source::tileLoadingCompleteCallback(const TileID& normalized_id) { +void Source::tileLoadingCompleteCallback(const TileID& normalized_id, const TransformState& transformState, bool collisionDebug) { auto it = tile_data.find(normalized_id); if (it == tile_data.end()) { return; @@ -555,6 +567,8 @@ void Source::tileLoadingCompleteCallback(const TileID& normalized_id) { } emitTileLoaded(true); + data->redoPlacement(transformState.getAngle(), collisionDebug); + } void Source::emitSourceLoaded() { diff --git a/src/mbgl/map/source.hpp b/src/mbgl/map/source.hpp index 174dd996b5..be869559b5 100644 --- a/src/mbgl/map/source.hpp +++ b/src/mbgl/map/source.hpp @@ -104,7 +104,7 @@ public: bool enabled; private: - void tileLoadingCompleteCallback(const TileID& normalized_id); + void tileLoadingCompleteCallback(const TileID& normalized_id, const TransformState& transformState, bool collisionDebug); void emitSourceLoaded(); void emitSourceLoadingFailed(const std::string& message); diff --git a/src/mbgl/map/tile_data.cpp b/src/mbgl/map/tile_data.cpp index fc2d48bb5b..6ff92bb6e5 100644 --- a/src/mbgl/map/tile_data.cpp +++ b/src/mbgl/map/tile_data.cpp @@ -2,6 +2,7 @@ #include <mbgl/map/environment.hpp> #include <mbgl/map/source.hpp> +#include <mbgl/map/transform_state.hpp> #include <mbgl/platform/log.hpp> #include <mbgl/storage/file_source.hpp> #include <mbgl/util/work_request.hpp> diff --git a/src/mbgl/map/tile_data.hpp b/src/mbgl/map/tile_data.hpp index d2a91b880f..2b237a61cb 100644 --- a/src/mbgl/map/tile_data.hpp +++ b/src/mbgl/map/tile_data.hpp @@ -21,6 +21,7 @@ class StyleLayer; class Request; class Worker; class WorkRequest; +class TransformState; class TileData : private util::noncopyable { public: @@ -86,6 +87,8 @@ public: virtual void parse() = 0; virtual Bucket* getBucket(StyleLayer const &layer_desc) = 0; + virtual void redoPlacement(float, bool) {} + const TileID id; const std::string name; std::atomic_flag parsing = ATOMIC_FLAG_INIT; diff --git a/src/mbgl/map/tile_id.cpp b/src/mbgl/map/tile_id.cpp index 518ee14c42..ad7ec2e0f6 100644 --- a/src/mbgl/map/tile_id.cpp +++ b/src/mbgl/map/tile_id.cpp @@ -5,35 +5,49 @@ namespace mbgl { -TileID TileID::parent(int8_t parent_z) const { +TileID TileID::parent(int8_t parent_z, int8_t sourceMaxZoom) const { assert(parent_z < z); - int32_t dim = std::pow(2, z - parent_z); - return TileID{ - parent_z, - (x >= 0 ? x : x - dim + 1) / dim, - y / dim - }; + auto newX = x; + auto newY = y; + for (auto newZ = z; newZ > parent_z; newZ--) { + if (newZ > sourceMaxZoom) { + // the id represents an overscaled tile, return the same coordinates with a lower z + // do nothing + } else { + newX = newX / 2; + newY = newY / 2; + } + } + + return TileID{parent_z, newX, newY, parent_z > sourceMaxZoom ? sourceMaxZoom : parent_z}; } -std::forward_list<TileID> TileID::children(int32_t child_z) const { - assert(child_z > z); - int32_t factor = std::pow(2, child_z - z); +std::forward_list<TileID> TileID::children(int8_t sourceMaxZoom) const { + auto childZ = z + 1; std::forward_list<TileID> child_ids; - for (int32_t ty = y * factor, y_max = (y + 1) * factor; ty < y_max; ++ty) { - for (int32_t tx = x * factor, x_max = (x + 1) * factor; tx < x_max; ++tx) { - child_ids.emplace_front(child_z, tx, ty); - } + if (z >= sourceMaxZoom) { + // return a single tile id representing a an overscaled tile + child_ids.emplace_front(childZ, x, y, sourceMaxZoom); + + } else { + auto childX = x * 2; + auto childY = y * 2; + child_ids.emplace_front(childZ, childX, childY, childZ); + child_ids.emplace_front(childZ, childX + 1, childY, childZ); + child_ids.emplace_front(childZ, childX, childY + 1, childZ); + child_ids.emplace_front(childZ, childX + 1, childY + 1, childZ); } + return child_ids; } TileID TileID::normalized() const { - int32_t dim = std::pow(2, z); + int32_t dim = std::pow(2, sourceZ); int32_t nx = x, ny = y; while (nx < 0) nx += dim; while (nx >= dim) nx -= dim; - return TileID { z, nx, ny }; + return TileID { z, nx, ny, sourceZ}; } bool TileID::isChildOf(const TileID &parent_id) const { diff --git a/src/mbgl/map/tile_id.hpp b/src/mbgl/map/tile_id.hpp index 056fcdbfa5..f2e2171f1a 100644 --- a/src/mbgl/map/tile_id.hpp +++ b/src/mbgl/map/tile_id.hpp @@ -14,9 +14,12 @@ public: const int16_t w = 0; const int8_t z = 0; const int32_t x = 0, y = 0; + const int8_t sourceZ; + const float overscaling; - inline explicit TileID(int8_t z_, int32_t x_, int32_t y_) - : w((x_ < 0 ? x_ - (1 << z_) + 1 : x_) / (1 << z_)), z(z_), x(x_), y(y_) {} + inline explicit TileID(int8_t z_, int32_t x_, int32_t y_, int8_t sourceZ_) + : w((x_ < 0 ? x_ - (1 << z_) + 1 : x_) / (1 << z_)), z(z_), x(x_), y(y_), + sourceZ(sourceZ_), overscaling(std::pow(2, z_ - sourceZ_)) {} inline uint64_t to_uint64() const { return ((std::pow(2, z) * y + x) * 32) + z; @@ -43,11 +46,12 @@ public: return y < rhs.y; } - TileID parent(int8_t z) const; + TileID parent(int8_t z, int8_t sourceMaxZoom) const; TileID normalized() const; - std::forward_list<TileID> children(int32_t z) const; + std::forward_list<TileID> children(int8_t sourceMaxZoom) const; bool isChildOf(const TileID&) const; operator std::string() const; + }; } diff --git a/src/mbgl/map/tile_parser.cpp b/src/mbgl/map/tile_parser.cpp index 9c0b5e26e1..61af227034 100644 --- a/src/mbgl/map/tile_parser.cpp +++ b/src/mbgl/map/tile_parser.cpp @@ -179,7 +179,7 @@ std::unique_ptr<Bucket> TileParser::createLineBucket(const GeometryTileLayer& la std::unique_ptr<Bucket> TileParser::createSymbolBucket(const GeometryTileLayer& layer, const StyleBucket& bucket_desc) { - auto bucket = std::make_unique<SymbolBucket>(*tile.getCollision()); + auto bucket = std::make_unique<SymbolBucket>(*tile.getCollision(), tile.id.overscaling); const float z = tile.id.z; auto& layout = bucket->layout; diff --git a/src/mbgl/map/transform_state.cpp b/src/mbgl/map/transform_state.cpp index 2a1cc4b9ea..8002a07f2b 100644 --- a/src/mbgl/map/transform_state.cpp +++ b/src/mbgl/map/transform_state.cpp @@ -8,8 +8,8 @@ using namespace mbgl; #pragma mark - Matrix -void TransformState::matrixFor(mat4& matrix, const TileID& id) const { - const double tile_scale = std::pow(2, id.z); +void TransformState::matrixFor(mat4& matrix, const TileID& id, const int8_t z) const { + const double tile_scale = std::pow(2, z); const double tile_size = scale * util::tileSize / tile_scale; matrix::identity(matrix); diff --git a/src/mbgl/map/transform_state.hpp b/src/mbgl/map/transform_state.hpp index e09be8ca63..3e76c7f817 100644 --- a/src/mbgl/map/transform_state.hpp +++ b/src/mbgl/map/transform_state.hpp @@ -20,7 +20,7 @@ class TransformState { public: // Matrix - void matrixFor(mat4& matrix, const TileID& id) const; + void matrixFor(mat4& matrix, const TileID& id, const int8_t z) const; box cornersToBox(uint32_t z) const; // Dimensions diff --git a/src/mbgl/map/vector_tile_data.cpp b/src/mbgl/map/vector_tile_data.cpp index e464c55c90..d431a200e6 100644 --- a/src/mbgl/map/vector_tile_data.cpp +++ b/src/mbgl/map/vector_tile_data.cpp @@ -5,27 +5,34 @@ #include <mbgl/map/source.hpp> #include <mbgl/geometry/glyph_atlas.hpp> #include <mbgl/platform/log.hpp> -#include <mbgl/text/collision.hpp> +#include <mbgl/text/collision_tile.hpp> #include <mbgl/util/pbf.hpp> +#include <mbgl/util/worker.hpp> +#include <mbgl/util/work_request.hpp> +#include <mbgl/style/style.hpp> using namespace mbgl; VectorTileData::VectorTileData(const TileID& id_, - float mapMaxZoom, Style& style_, GlyphAtlas& glyphAtlas_, GlyphStore& glyphStore_, SpriteAtlas& spriteAtlas_, util::ptr<Sprite> sprite_, - const SourceInfo& source_) + const SourceInfo& source_, + float overscaling_, + float angle, + bool collisionDebug) : TileData(id_, source_), - depth(id_.z >= source_.max_zoom ? mapMaxZoom - id_.z : 1), glyphAtlas(glyphAtlas_), glyphStore(glyphStore_), spriteAtlas(spriteAtlas_), sprite(sprite_), style(style_), - collision(std::make_unique<Collision>(id_.z, 4096, source_.tile_size, depth)) { + overscaling(overscaling_), + collision(std::make_unique<CollisionTile>(id_.z, 4096, source_.tile_size * id.overscaling, angle, collisionDebug)), + lastAngle(angle), + currentAngle(angle) { } VectorTileData::~VectorTileData() { @@ -60,7 +67,7 @@ void VectorTileData::parse() { } } catch (const std::exception& ex) { std::stringstream message; - message << "Failed to parse [" << int(id.z) << "/" << id.x << "/" << id.y << "]: " << ex.what(); + message << "Failed to parse [" << int(id.sourceZ) << "/" << id.x << "/" << id.y << "]: " << ex.what(); setError(message.str()); } } @@ -103,6 +110,49 @@ void VectorTileData::setState(const State& state_) { TileData::setState(state_); if (isImmutable()) { - collision.reset(); + collision->reset(0, 0); } } + +void VectorTileData::redoPlacement() { + redoPlacement(lastAngle, lastCollisionDebug); +} + +void VectorTileData::redoPlacement(float angle, bool collisionDebug) { + if (angle != currentAngle || collisionDebug != currentCollisionDebug) { + lastAngle = angle; + lastCollisionDebug = collisionDebug; + + if (getState() != State::parsed || redoingPlacement) return; + + redoingPlacement = true; + currentAngle = angle; + currentCollisionDebug = collisionDebug; + + auto callback = std::bind(&VectorTileData::endRedoPlacement, this); + workRequest = style.workers.send([this, angle, collisionDebug] { workerRedoPlacement(angle, collisionDebug); }, callback); + + } +} + +void VectorTileData::workerRedoPlacement(float angle, bool collisionDebug) { + collision->reset(angle, 0); + collision->setDebug(collisionDebug); + for (const auto& layer_desc : style.layers) { + auto bucket = getBucket(*layer_desc); + if (bucket) { + bucket->placeFeatures(); + } + } +} + +void VectorTileData::endRedoPlacement() { + for (const auto& layer_desc : style.layers) { + auto bucket = getBucket(*layer_desc); + if (bucket) { + bucket->swapRenderData(); + } + } + redoingPlacement = false; + redoPlacement(); +} diff --git a/src/mbgl/map/vector_tile_data.hpp b/src/mbgl/map/vector_tile_data.hpp index 6549c106e4..2c7c3a204a 100644 --- a/src/mbgl/map/vector_tile_data.hpp +++ b/src/mbgl/map/vector_tile_data.hpp @@ -7,6 +7,7 @@ #include <mbgl/geometry/icon_buffer.hpp> #include <mbgl/geometry/line_buffer.hpp> #include <mbgl/geometry/text_buffer.hpp> +#include <mbgl/geometry/collision_box_buffer.hpp> #include <iosfwd> #include <memory> @@ -16,7 +17,7 @@ namespace mbgl { class Bucket; -class Collision; +class CollisionTile; class Painter; class SourceInfo; class StyleLayer; @@ -32,16 +33,19 @@ class VectorTileData : public TileData { public: VectorTileData(const TileID&, - float mapMaxZoom, Style&, GlyphAtlas&, GlyphStore&, SpriteAtlas&, util::ptr<Sprite>, - const SourceInfo&); + const SourceInfo&, + float overscaling_, + float angle_, + bool collisionDebug_); ~VectorTileData(); void parse() override; + void redoPlacement(float angle, bool collisionDebug) override; virtual Bucket* getBucket(StyleLayer const &layer_desc) override; size_t countBuckets() const; @@ -49,13 +53,13 @@ public: void setState(const State& state) override; - inline Collision* getCollision() const { + inline CollisionTile* getCollision() const { return collision.get(); } - const float depth; - protected: + void redoPlacement(); + // Holds the actual geometries in this tile. FillVertexBuffer fillVertexBuffer; LineVertexBuffer lineVertexBuffer; @@ -79,7 +83,16 @@ private: std::unordered_map<std::string, std::unique_ptr<Bucket>> buckets; mutable std::mutex bucketsMutex; - std::unique_ptr<Collision> collision; + const float overscaling; + std::unique_ptr<CollisionTile> collision; + + float lastAngle = 0; + float currentAngle; + bool lastCollisionDebug = 0; + bool currentCollisionDebug = 0; + bool redoingPlacement = false; + void endRedoPlacement(); + void workerRedoPlacement(float angle, bool collisionDebug); }; } diff --git a/src/mbgl/renderer/bucket.hpp b/src/mbgl/renderer/bucket.hpp index 711fc42384..147895a099 100644 --- a/src/mbgl/renderer/bucket.hpp +++ b/src/mbgl/renderer/bucket.hpp @@ -27,6 +27,9 @@ public: return !uploaded; } + virtual void placeFeatures() {} + virtual void swapRenderData() {} + protected: bool uploaded = false; diff --git a/src/mbgl/renderer/painter.cpp b/src/mbgl/renderer/painter.cpp index bad4f9085a..43d06b69d1 100644 --- a/src/mbgl/renderer/painter.cpp +++ b/src/mbgl/renderer/painter.cpp @@ -25,6 +25,7 @@ #include <mbgl/shader/sdf_shader.hpp> #include <mbgl/shader/dot_shader.hpp> #include <mbgl/shader/gaussian_shader.hpp> +#include <mbgl/shader/box_shader.hpp> #include <mbgl/util/constants.hpp> #include <mbgl/util/mat3.hpp> @@ -101,6 +102,7 @@ void Painter::setupShaders() { if (!sdfIconShader) sdfIconShader = std::make_unique<SDFIconShader>(); if (!dotShader) dotShader = std::make_unique<DotShader>(); if (!gaussianShader) gaussianShader = std::make_unique<GaussianShader>(); + if (!collisionBoxShader) collisionBoxShader = std::make_unique<CollisionBoxShader>(); } void Painter::resize() { @@ -467,7 +469,7 @@ mat4 Painter::translatedMatrix(const mat4& matrix, const std::array<float, 2> &t return matrix; } else { // TODO: Get rid of the 8 (scaling from 4096 to tile size) - const double factor = ((double)(1 << id.z)) / state.getScale() * (4096.0 / util::tileSize); + const double factor = ((double)(1 << id.z)) / state.getScale() * (4096.0 / util::tileSize / id.overscaling); mat4 vtxMatrix; if (anchor == TranslateAnchorType::Viewport) { diff --git a/src/mbgl/renderer/painter.hpp b/src/mbgl/renderer/painter.hpp index 7b7bf693f4..465bf5ba33 100644 --- a/src/mbgl/renderer/painter.hpp +++ b/src/mbgl/renderer/painter.hpp @@ -55,6 +55,7 @@ class SDFGlyphShader; class SDFIconShader; class DotShader; class GaussianShader; +class CollisionBoxShader; struct ClipID; @@ -101,7 +102,6 @@ public: void renderDebugFrame(const mat4 &matrix); void renderDebugText(DebugBucket& bucket, const mat4 &matrix); - void renderDebugText(const std::vector<std::string> &strings); void renderFill(FillBucket& bucket, const StyleLayer &layer_desc, const TileID& id, const mat4 &matrix); void renderLine(LineBucket& bucket, const StyleLayer &layer_desc, const TileID& id, const mat4 &matrix); void renderSymbol(SymbolBucket& bucket, const StyleLayer &layer_desc, const TileID& id, const mat4 &matrix); @@ -220,6 +220,7 @@ public: std::unique_ptr<SDFIconShader> sdfIconShader; std::unique_ptr<DotShader> dotShader; std::unique_ptr<GaussianShader> gaussianShader; + std::unique_ptr<CollisionBoxShader> collisionBoxShader; StaticVertexBuffer backgroundBuffer = { { -1, -1 }, { 1, -1 }, diff --git a/src/mbgl/renderer/painter_debug.cpp b/src/mbgl/renderer/painter_debug.cpp index d4306d3e1a..4466ad2503 100644 --- a/src/mbgl/renderer/painter_debug.cpp +++ b/src/mbgl/renderer/painter_debug.cpp @@ -67,41 +67,3 @@ void Painter::renderDebugFrame(const mat4 &matrix) { lineWidth(4.0f * state.getPixelRatio()); MBGL_CHECK_ERROR(glDrawArrays(GL_LINE_STRIP, 0, (GLsizei)tileBorderBuffer.index())); } - -void Painter::renderDebugText(const std::vector<std::string> &strings) { - if (strings.empty()) { - return; - } - - gl::debugging::group group("debug text"); - - config.depthTest = false; - config.stencilTest = true; - config.stencilFunc = { GL_ALWAYS, 0xFF, 0xFF }; - - useProgram(plainShader->program); - plainShader->u_matrix = nativeMatrix; - - DebugFontBuffer debugFontBuffer; - int line = 25; - for (const auto& str : strings) { - debugFontBuffer.addText(str.c_str(), 10, line, 0.75); - line += 20; - } - - if (!debugFontBuffer.empty()) { - // draw debug info - VertexArrayObject debugFontArray; - debugFontArray.bind(*plainShader, debugFontBuffer, BUFFER_OFFSET(0)); - plainShader->u_color = {{ 1.0f, 1.0f, 1.0f, 1.0f }}; - lineWidth(4.0f * state.getPixelRatio()); - MBGL_CHECK_ERROR(glDrawArrays(GL_LINES, 0, (GLsizei)debugFontBuffer.index())); - #ifndef GL_ES_VERSION_2_0 - MBGL_CHECK_ERROR(glPointSize(2)); - MBGL_CHECK_ERROR(glDrawArrays(GL_POINTS, 0, (GLsizei)debugFontBuffer.index())); - #endif - plainShader->u_color = {{ 0.0f, 0.0f, 0.0f, 1.0f }}; - lineWidth(2.0f * state.getPixelRatio()); - MBGL_CHECK_ERROR(glDrawArrays(GL_LINES, 0, (GLsizei)debugFontBuffer.index())); - } -} diff --git a/src/mbgl/renderer/painter_fill.cpp b/src/mbgl/renderer/painter_fill.cpp index 86cef7d60e..5514ebc858 100644 --- a/src/mbgl/renderer/painter_fill.cpp +++ b/src/mbgl/renderer/painter_fill.cpp @@ -65,7 +65,7 @@ void Painter::renderFill(FillBucket& bucket, const StyleLayer &layer_desc, const const SpriteAtlasPosition posA = spriteAtlas->getPosition(properties.image.from, true); const SpriteAtlasPosition posB = spriteAtlas->getPosition(properties.image.to, true); - float factor = 8.0 / std::pow(2, state.getIntegerZoom() - id.z); + float factor = 8.0 / std::pow(2, state.getIntegerZoom() - id.z) / id.overscaling; mat3 patternMatrixA; matrix::identity(patternMatrixA); diff --git a/src/mbgl/renderer/painter_line.cpp b/src/mbgl/renderer/painter_line.cpp index d3949df5b9..e084147deb 100644 --- a/src/mbgl/renderer/painter_line.cpp +++ b/src/mbgl/renderer/painter_line.cpp @@ -70,7 +70,7 @@ void Painter::renderLine(LineBucket& bucket, const StyleLayer &layer_desc, const LinePatternPos posB = lineAtlas->getDashPosition(properties.dash_array.to, layout.cap == CapType::Round); lineAtlas->bind(); - float patternratio = std::pow(2.0, std::floor(std::log2(state.getScale())) - id.z) / 8.0; + float patternratio = std::pow(2.0, std::floor(std::log2(state.getScale())) - id.z) / 8.0 * id.overscaling; float scaleXA = patternratio / posA.width / properties.dash_line_width / properties.dash_array.fromScale; float scaleYA = -posA.height / 2.0; float scaleXB = patternratio / posB.width / properties.dash_line_width / properties.dash_array.toScale; @@ -90,7 +90,7 @@ void Painter::renderLine(LineBucket& bucket, const StyleLayer &layer_desc, const SpriteAtlasPosition imagePosA = spriteAtlas->getPosition(properties.image.from, true); SpriteAtlasPosition imagePosB = spriteAtlas->getPosition(properties.image.to, true); - float factor = 8.0 / std::pow(2, state.getIntegerZoom() - id.z); + float factor = 8.0 / std::pow(2, state.getIntegerZoom() - id.z) * id.overscaling; useProgram(linepatternShader->program); diff --git a/src/mbgl/renderer/painter_symbol.cpp b/src/mbgl/renderer/painter_symbol.cpp index 0c2f0c3cd1..4f4999b3e2 100644 --- a/src/mbgl/renderer/painter_symbol.cpp +++ b/src/mbgl/renderer/painter_symbol.cpp @@ -6,6 +6,8 @@ #include <mbgl/geometry/sprite_atlas.hpp> #include <mbgl/shader/sdf_shader.hpp> #include <mbgl/shader/icon_shader.hpp> +#include <mbgl/shader/box_shader.hpp> +#include <mbgl/map/tile_id.hpp> #include <mbgl/util/math.hpp> #include <cmath> @@ -45,14 +47,9 @@ void Painter::renderSDF(SymbolBucket &bucket, sdfShader.u_exmatrix = exMatrix; sdfShader.u_texsize = texsize; - // Convert the -pi..pi to an int8 range. - float angle = std::round(state.getAngle() / M_PI * 128); - // adjust min/max zooms for variable font sies float zoomAdjust = std::log(fontSize / bucketProperties.max_size) / std::log(2); - sdfShader.u_flip = (aligned_with_map && bucketProperties.keep_upright) ? 1 : 0; - sdfShader.u_angle = (int32_t)(angle + 256) % 256; sdfShader.u_zoom = (state.getNormalizedZoom() - zoomAdjust) * 10; // current zoom level FadeProperties f = frameHistory.getFadeProperties(std::chrono::milliseconds(300)); @@ -122,10 +119,37 @@ void Painter::renderSymbol(SymbolBucket &bucket, const StyleLayer &layer_desc, c const auto &properties = layer_desc.getProperties<SymbolProperties>(); const auto &layout = bucket.layout; - config.stencilTest = false; config.depthTest = true; config.depthMask = GL_FALSE; + if (bucket.hasCollisionBoxData() && ( + (bucket.hasIconData() && properties.icon.opacity) || + (bucket.hasTextData() && properties.text.opacity))) { + config.stencilTest = true; + + useProgram(collisionBoxShader->program); + collisionBoxShader->u_matrix = matrix; + collisionBoxShader->u_scale = std::pow(2, state.getNormalizedZoom() - id.z); + collisionBoxShader->u_zoom = state.getNormalizedZoom() * 10; + collisionBoxShader->u_maxzoom = (id.z + 1) * 10; + lineWidth(3.0f); + + config.depthRange = { strata, 1.0f }; + bucket.drawCollisionBoxes(*collisionBoxShader); + + } + + // TODO remove the `|| true` when #1673 is implemented + const bool drawAcrossEdges = !(layout.text.allow_overlap || layout.icon.allow_overlap || + layout.text.ignore_placement || layout.icon.ignore_placement) || true; + + // Disable the stencil test so that labels aren't clipped to tile boundaries. + // + // Layers with features that may be drawn overlapping aren't clipped. These + // layers are sorted in the y direction, and to draw the correct ordering near + // tile edges the icons are included in both tiles and clipped when drawing. + config.stencilTest = drawAcrossEdges ? false : true; + if (bucket.hasIconData()) { bool sdf = bucket.sdfIcons; @@ -167,19 +191,10 @@ void Painter::renderSymbol(SymbolBucket &bucket, const StyleLayer &layer_desc, c iconShader->u_exmatrix = exMatrix; iconShader->u_texsize = {{ float(spriteAtlas->getWidth()) / 4.0f, float(spriteAtlas->getHeight()) / 4.0f }}; - // Convert the -pi..pi to an int8 range. - const float angle = std::round(state.getAngle() / M_PI * 128); - // adjust min/max zooms for variable font sies float zoomAdjust = std::log(fontSize / layout.icon.max_size) / std::log(2); - iconShader->u_angle = (int32_t)(angle + 256) % 256; - - bool flip = (layout.icon.rotation_alignment == RotationAlignmentType::Map) - && layout.icon.keep_upright; - iconShader->u_flip = flip ? 1 : 0; iconShader->u_zoom = (state.getNormalizedZoom() - zoomAdjust) * 10; // current zoom level - iconShader->u_fadedist = 0 * 10; iconShader->u_minfadezoom = state.getNormalizedZoom() * 10; iconShader->u_maxfadezoom = state.getNormalizedZoom() * 10; @@ -204,4 +219,5 @@ void Painter::renderSymbol(SymbolBucket &bucket, const StyleLayer &layer_desc, c *sdfGlyphShader, &SymbolBucket::drawGlyphs); } + } diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp index 02e7e0cc6a..8521bbbf44 100644 --- a/src/mbgl/renderer/symbol_bucket.cpp +++ b/src/mbgl/renderer/symbol_bucket.cpp @@ -6,21 +6,23 @@ #include <mbgl/geometry/glyph_atlas.hpp> #include <mbgl/geometry/sprite_atlas.hpp> #include <mbgl/geometry/anchor.hpp> -#include <mbgl/geometry/resample.hpp> +#include <mbgl/text/get_anchors.hpp> #include <mbgl/renderer/painter.hpp> #include <mbgl/text/glyph_store.hpp> #include <mbgl/text/font_stack.hpp> -#include <mbgl/text/placement.hpp> #include <mbgl/platform/log.hpp> -#include <mbgl/text/collision.hpp> +#include <mbgl/text/collision_tile.hpp> #include <mbgl/shader/sdf_shader.hpp> #include <mbgl/shader/icon_shader.hpp> +#include <mbgl/shader/box_shader.hpp> #include <mbgl/map/sprite.hpp> #include <mbgl/util/utf.hpp> #include <mbgl/util/token.hpp> #include <mbgl/util/math.hpp> #include <mbgl/util/merge_lines.hpp> +#include <mbgl/util/clip_lines.hpp> +#include <mbgl/util/std.hpp> #ifndef BUFFER_OFFSET #define BUFFER_OFFSET(i) ((char *)nullptr + (i)) @@ -28,8 +30,34 @@ namespace mbgl { -SymbolBucket::SymbolBucket(Collision &collision_) - : collision(collision_) { +SymbolInstance::SymbolInstance(Anchor &anchor, const std::vector<Coordinate> &line, + const Shaping &shapedText, const PositionedIcon &shapedIcon, + const StyleLayoutSymbol &layout, const bool addToBuffers, + const float textBoxScale, const float textPadding, const float textAlongLine, + const float iconBoxScale, const float iconPadding, const float iconAlongLine, + const GlyphPositions &face) : + x(anchor.x), + y(anchor.y), + hasText(shapedText), + hasIcon(shapedIcon), + + // Create the quads used for rendering the glyphs. + glyphQuads(addToBuffers && shapedText ? + getGlyphQuads(anchor, shapedText, textBoxScale, line, layout, textAlongLine, face) : + SymbolQuads()), + + // Create the quad used for rendering the icon. + iconQuads(addToBuffers && shapedIcon ? + getIconQuads(anchor, shapedIcon, line, layout, iconAlongLine) : + SymbolQuads()), + + // Create the collision features that will be used to check whether this symbol instance can be placed + textCollisionFeature(line, anchor, shapedText, textBoxScale, textPadding, textAlongLine), + iconCollisionFeature(line, anchor, shapedIcon, iconBoxScale, iconPadding, iconAlongLine) {}; + + +SymbolBucket::SymbolBucket(CollisionTile &collision_, float overscaling_) + : collision(collision_), overscaling(overscaling_) { } SymbolBucket::~SymbolBucket() { @@ -38,12 +66,12 @@ SymbolBucket::~SymbolBucket() { void SymbolBucket::upload() { if (hasTextData()) { - text.vertices.upload(); - text.triangles.upload(); + renderData->text.vertices.upload(); + renderData->text.triangles.upload(); } if (hasIconData()) { - icon.vertices.upload(); - icon.triangles.upload(); + renderData->icon.vertices.upload(); + renderData->icon.triangles.upload(); } uploaded = true; @@ -58,9 +86,11 @@ void SymbolBucket::render(Painter& painter, bool SymbolBucket::hasData() const { return hasTextData() || hasIconData(); } -bool SymbolBucket::hasTextData() const { return !text.groups.empty(); } +bool SymbolBucket::hasTextData() const { return renderData && !renderData->text.groups.empty(); } -bool SymbolBucket::hasIconData() const { return !icon.groups.empty(); } +bool SymbolBucket::hasIconData() const { return renderData && !renderData->icon.groups.empty(); } + +bool SymbolBucket::hasCollisionBoxData() const { return renderData && !renderData->collisionBox.groups.empty(); } bool SymbolBucket::needsDependencies(const GeometryTileLayer& layer, const FilterExpression& filter, @@ -186,22 +216,22 @@ void SymbolBucket::addFeatures(uintptr_t tileUID, break; } - float justify = 0.5; - if (layout.text.justify == TextJustifyType::Right) justify = 1; - else if (layout.text.justify == TextJustifyType::Left) justify = 0; + const float justify = layout.text.justify == TextJustifyType::Right ? 1 : + layout.text.justify == TextJustifyType::Left ? 0 : + 0.5; auto fontStack = glyphStore.getFontStack(layout.text.font); for (const auto& feature : features) { if (!feature.geometry.size()) continue; - Shaping shaping; - Rect<uint16_t> image; + Shaping shapedText; + PositionedIcon shapedIcon; GlyphPositions face; // if feature has text, shape the text if (feature.label.length()) { - shaping = fontStack->getShaping( + shapedText = fontStack->getShaping( /* string */ feature.label, /* maxWidth: ems */ layout.placement != PlacementType::Line ? layout.text.max_width * 24 : 0, @@ -213,118 +243,150 @@ void SymbolBucket::addFeatures(uintptr_t tileUID, /* translate */ vec2<float>(layout.text.offset[0], layout.text.offset[1])); // Add the glyphs we need for this label to the glyph atlas. - if (shaping.size()) { + if (shapedText) { glyphAtlas.addGlyphs(tileUID, feature.label, layout.text.font, **fontStack, face); } } // if feature has icon, get sprite atlas position if (feature.sprite.length()) { - image = spriteAtlas.getImage(feature.sprite, false); + Rect<uint16_t> image = spriteAtlas.getImage(feature.sprite, false); + shapedIcon = shapeIcon(image, layout); if (sprite.getSpritePosition(feature.sprite).sdf) { sdfIcons = true; } } - // if either shaping or icon position is present, add the feature - if (shaping.size() || image.hasArea()) { - for (const auto& line : feature.geometry) { - if (line.size()) { - addFeature(line, shaping, face, image); - } - } + // if either shapedText or icon position is present, add the feature + if (shapedText || shapedIcon) { + addFeature(feature.geometry, shapedText, shapedIcon, face); } } features.clear(); -} -bool byScale(const Anchor &a, const Anchor &b) { return a.scale < b.scale; } + placeFeatures(true); +} -const PlacementRange fullRange{{2 * M_PI, 0}}; -void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping &shaping, - const GlyphPositions &face, const Rect<uint16_t> &image) { - assert(line.size()); +void SymbolBucket::addFeature(const std::vector<std::vector<Coordinate>> &lines, + const Shaping &shapedText, const PositionedIcon &shapedIcon, const GlyphPositions &face) { const float minScale = 0.5f; const float glyphSize = 24.0f; - const bool horizontalText = - layout.text.rotation_alignment == RotationAlignmentType::Viewport; - const bool horizontalIcon = - layout.icon.rotation_alignment == RotationAlignmentType::Viewport; const float fontScale = layout.text.max_size / glyphSize; const float textBoxScale = collision.tilePixelRatio * fontScale; const float iconBoxScale = collision.tilePixelRatio * layout.icon.max_size; - const bool iconWithoutText = layout.text.optional || !shaping.size(); - const bool textWithoutIcon = layout.icon.optional || !image.hasArea(); + const float symbolSpacing = collision.tilePixelRatio * layout.min_distance; const bool avoidEdges = layout.avoid_edges && layout.placement != PlacementType::Line; + const float textPadding = layout.text.padding * collision.tilePixelRatio; + const float iconPadding = layout.icon.padding * collision.tilePixelRatio; + const float textMaxAngle = layout.text.max_angle * M_PI / 180; + const bool textAlongLine = + layout.text.rotation_alignment == RotationAlignmentType::Map && + layout.placement == PlacementType::Line; + const bool iconAlongLine = + layout.icon.rotation_alignment == RotationAlignmentType::Map && + layout.placement == PlacementType::Line; + const bool mayOverlap = layout.text.allow_overlap || layout.icon.allow_overlap || + layout.text.ignore_placement || layout.icon.ignore_placement; + + auto& clippedLines = layout.placement == PlacementType::Line ? + util::clipLines(lines, 0, 0, 4096, 4096) : + lines; + + for (const auto& line : clippedLines) { + if (!line.size()) continue; + + // Calculate the anchor points around which you want to place labels + Anchors anchors = layout.placement == PlacementType::Line ? + getAnchors(line, symbolSpacing, textMaxAngle, shapedText.left, shapedText.right, glyphSize, textBoxScale, overscaling) : + Anchors({ Anchor(float(line[0].x), float(line[0].y), 0, minScale) }); + + + // For each potential label, create the placement features used to check for collisions, and the quads use for rendering. + for (Anchor &anchor : anchors) { + + const bool inside = !(anchor.x < 0 || anchor.x > 4096 || anchor.y < 0 || anchor.y > 4096); + + if (avoidEdges && !inside) continue; + + // Normally symbol layers are drawn across tile boundaries. Only symbols + // with their anchors within the tile boundaries are added to the buffers + // to prevent symbols from being drawn twice. + // + // Symbols in layers with overlap are sorted in the y direction so that + // symbols lower on the canvas are drawn on top of symbols near the top. + // To preserve this order across tile boundaries these symbols can't + // be drawn across tile boundaries. Instead they need to be included in + // the buffers for both tiles and clipped to tile boundaries at draw time. + // + // TODO remove the `&& false` when is #1673 implemented + const bool addToBuffers = inside || (mayOverlap && false); + + symbolInstances.emplace_back(anchor, line, shapedText, shapedIcon, layout, addToBuffers, + textBoxScale, textPadding, textAlongLine, + iconBoxScale, iconPadding, iconAlongLine, + face); + } + } +} - Anchors anchors; +void SymbolBucket::placeFeatures() { + placeFeatures(false); +} - if (layout.placement == PlacementType::Line) { - float resampleOffset = 0; - - if (shaping.size()) { - float minX = std::numeric_limits<float>::infinity(); - float maxX = -std::numeric_limits<float>::infinity(); - for (const auto &glyph : shaping) { - minX = std::min(minX, glyph.x); - maxX = std::max(maxX, glyph.x); - } - const float labelLength = maxX - minX; - resampleOffset = (labelLength / 2.0 + glyphSize * 2.0) * fontScale; - } +void SymbolBucket::placeFeatures(bool swapImmediately) { - // Line labels - anchors = resample(line, layout.min_distance, minScale, collision.maxPlacementScale, - collision.tilePixelRatio, resampleOffset); + renderDataInProgress = std::make_unique<SymbolRenderData>(); - // Sort anchors by segment so that we can start placement with the - // anchors that can be shown at the lowest zoom levels. - std::sort(anchors.begin(), anchors.end(), byScale); + // Calculate which labels can be shown and when they can be shown and + // create the bufers used for rendering. - } else { - // Point labels - anchors = {Anchor{float(line[0].x), float(line[0].y), 0, minScale}}; + const bool textAlongLine = + layout.text.rotation_alignment == RotationAlignmentType::Map && + layout.placement == PlacementType::Line; + const bool iconAlongLine = + layout.icon.rotation_alignment == RotationAlignmentType::Map && + layout.placement == PlacementType::Line; + + const bool mayOverlap = layout.text.allow_overlap || layout.icon.allow_overlap || + layout.text.ignore_placement || layout.icon.ignore_placement; + + // Sort symbols by their y position on the canvas so that they lower symbols + // are drawn on top of higher symbols. + // Don't sort symbols that won't overlap because it isn't necessary and + // because it causes more labels to pop in and out when rotating. + if (mayOverlap) { + float sin = std::sin(collision.angle); + float cos = std::cos(collision.angle); + + std::sort(symbolInstances.begin(), symbolInstances.end(), [sin, cos](SymbolInstance &a, SymbolInstance &b) { + const float aRotated = sin * a.x + cos * a.y; + const float bRotated = sin * b.x + cos * b.y; + return aRotated < bRotated; + }); } - // TODO: figure out correct ascender height. - const vec2<float> origin = {0, -17}; - - for (auto& anchor : anchors) { - - // Calculate the scales at which the text and icons can be first shown without overlap - Placement glyphPlacement; - Placement iconPlacement; - float glyphScale = 0; - float iconScale = 0; - const bool inside = !(anchor.x < 0 || anchor.x > 4096 || anchor.y < 0 || anchor.y > 4096); - - if (avoidEdges && !inside) continue; - - if (shaping.size()) { - glyphPlacement = Placement::getGlyphs(anchor, origin, shaping, face, textBoxScale, - horizontalText, line, layout); - glyphScale = - layout.text.allow_overlap - ? glyphPlacement.minScale - : collision.getPlacementScale(glyphPlacement.boxes, glyphPlacement.minScale, avoidEdges); - if (!glyphScale && !iconWithoutText) - continue; - } + for (SymbolInstance &symbolInstance : symbolInstances) { - if (image.hasArea()) { - iconPlacement = Placement::getIcon(anchor, image, iconBoxScale, line, layout); - iconScale = - layout.icon.allow_overlap - ? iconPlacement.minScale - : collision.getPlacementScale(iconPlacement.boxes, iconPlacement.minScale, avoidEdges); - if (!iconScale && !textWithoutIcon) - continue; - } + const bool hasText = symbolInstance.hasText; + const bool hasIcon = symbolInstance.hasIcon; + + const bool iconWithoutText = layout.text.optional || !hasText; + const bool textWithoutIcon = layout.icon.optional || !hasIcon; + + // Calculate the scales at which the text and icon can be placed without collision. + + float glyphScale = hasText && !layout.text.allow_overlap ? + collision.placeFeature(symbolInstance.textCollisionFeature) : collision.minScale; + float iconScale = hasIcon && !layout.icon.allow_overlap ? + collision.placeFeature(symbolInstance.iconCollisionFeature) : collision.minScale; + + + // Combine the scales for icons and text. if (!iconWithoutText && !textWithoutIcon) { iconScale = glyphScale = util::max(iconScale, glyphScale); @@ -334,49 +396,37 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping iconScale = util::max(iconScale, glyphScale); } - // Get the rotation ranges it is safe to show the glyphs - PlacementRange glyphRange = - (!glyphScale || layout.text.allow_overlap) - ? fullRange - : collision.getPlacementRange(glyphPlacement.boxes, glyphScale, horizontalText); - PlacementRange iconRange = - (!iconScale || layout.icon.allow_overlap) - ? fullRange - : collision.getPlacementRange(iconPlacement.boxes, iconScale, horizontalIcon); - - const PlacementRange maxRange = {{ - util::min(iconRange[0], glyphRange[0]), util::max(iconRange[1], glyphRange[1]), - }}; - - if (!iconWithoutText && !textWithoutIcon) { - iconRange = glyphRange = maxRange; - } else if (!textWithoutIcon) { - glyphRange = maxRange; - } else if (!iconWithoutText) { - iconRange = maxRange; - } // Insert final placement into collision tree and add glyphs/icons to buffers - if (glyphScale && std::isfinite(glyphScale)) { + + if (hasText) { if (!layout.text.ignore_placement) { - collision.insert(glyphPlacement.boxes, anchor, glyphScale, glyphRange, - horizontalText); + collision.insertFeature(symbolInstance.textCollisionFeature, glyphScale); + } + if (glyphScale < collision.maxScale) { + addSymbols<SymbolRenderData::TextBuffer, TextElementGroup>(renderDataInProgress->text, + symbolInstance.glyphQuads, glyphScale, layout.text.keep_upright, textAlongLine); } - if (inside) addSymbols<TextBuffer, TextElementGroup>(text, glyphPlacement.shapes, glyphScale, glyphRange); } - if (iconScale && std::isfinite(iconScale)) { + if (hasIcon) { if (!layout.icon.ignore_placement) { - collision.insert(iconPlacement.boxes, anchor, iconScale, iconRange, horizontalIcon); + collision.insertFeature(symbolInstance.iconCollisionFeature, iconScale); + } + if (iconScale < collision.maxScale) { + addSymbols<SymbolRenderData::IconBuffer, IconElementGroup>(renderDataInProgress->icon, + symbolInstance.iconQuads, iconScale, layout.icon.keep_upright, iconAlongLine); } - if (inside) addSymbols<IconBuffer, IconElementGroup>(icon, iconPlacement.shapes, iconScale, iconRange); } } + + if (collision.getDebug()) addToDebugBuffers(); + + if (swapImmediately) swapRenderData(); } template <typename Buffer, typename GroupType> -void SymbolBucket::addSymbols(Buffer &buffer, const PlacedGlyphs &symbols, float scale, - PlacementRange placementRange) { +void SymbolBucket::addSymbols(Buffer &buffer, const SymbolQuads &symbols, float scale, const bool keepUpright, const bool alongLine) { const float zoom = collision.zoom; const float placementZoom = std::log(scale) / std::log(2) + zoom; @@ -387,13 +437,17 @@ void SymbolBucket::addSymbols(Buffer &buffer, const PlacedGlyphs &symbols, float const auto &bl = symbol.bl; const auto &br = symbol.br; const auto &tex = symbol.tex; - const auto &angle = symbol.angle; float minZoom = util::max(static_cast<float>(zoom + log(symbol.minScale) / log(2)), placementZoom); float maxZoom = util::min(static_cast<float>(zoom + log(symbol.maxScale) / log(2)), 25.0f); const auto &glyphAnchor = symbol.anchor; + // drop upside down versions of glyphs + const float a = std::fmod(symbol.angle + collision.angle + M_PI, M_PI * 2); + if (keepUpright && alongLine && (a <= M_PI / 2 || a > M_PI * 3 / 2)) continue; + + if (maxZoom <= minZoom) continue; @@ -418,14 +472,14 @@ void SymbolBucket::addSymbols(Buffer &buffer, const PlacedGlyphs &symbols, float uint32_t triangleIndex = triangleGroup.vertex_length; // coordinates (2 triangles) - buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, tl.x, tl.y, tex.x, tex.y, angle, minZoom, - placementRange, maxZoom, placementZoom); - buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, tr.x, tr.y, tex.x + tex.w, tex.y, angle, - minZoom, placementRange, maxZoom, placementZoom); - buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, bl.x, bl.y, tex.x, tex.y + tex.h, angle, - minZoom, placementRange, maxZoom, placementZoom); + buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, tl.x, tl.y, tex.x, tex.y, minZoom, + maxZoom, placementZoom); + buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, tr.x, tr.y, tex.x + tex.w, tex.y, + minZoom, maxZoom, placementZoom); + buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, bl.x, bl.y, tex.x, tex.y + tex.h, + minZoom, maxZoom, placementZoom); buffer.vertices.add(glyphAnchor.x, glyphAnchor.y, br.x, br.y, tex.x + tex.w, tex.y + tex.h, - angle, minZoom, placementRange, maxZoom, placementZoom); + minZoom, maxZoom, placementZoom); // add the two triangles, referencing the four coordinates we just inserted. buffer.triangles.add(triangleIndex + 0, triangleIndex + 1, triangleIndex + 2); @@ -436,9 +490,66 @@ void SymbolBucket::addSymbols(Buffer &buffer, const PlacedGlyphs &symbols, float } } +void SymbolBucket::addToDebugBuffers() { + + const float yStretch = 1.0f; + const float angle = collision.angle; + const float zoom = collision.zoom; + 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}}; + + for (const SymbolInstance &symbolInstance : symbolInstances) { + for (int i = 0; i < 2; i++) { + auto& feature = i == 0 ? + symbolInstance.textCollisionFeature : + symbolInstance.iconCollisionFeature; + + for (const CollisionBox &box : feature.boxes) { + auto& anchor = box.anchor; + + vec2<float> tl{box.x1, box.y1 * yStretch}; + vec2<float> tr{box.x2, box.y1 * yStretch}; + vec2<float> bl{box.x1, box.y2 * yStretch}; + vec2<float> br{box.x2, box.y2 * yStretch}; + tl = tl.matMul(matrix); + tr = tr.matMul(matrix); + bl = bl.matMul(matrix); + br = br.matMul(matrix); + + const float maxZoom = util::max(0.0f, util::min(25.0f, static_cast<float>(zoom + log(box.maxScale) / log(2)))); + const float placementZoom= util::max(0.0f, util::min(25.0f, static_cast<float>(zoom + log(box.placementScale) / log(2)))); + + auto& collisionBox = renderDataInProgress->collisionBox; + if (!collisionBox.groups.size()) { + // Move to a new group because the old one can't hold the geometry. + collisionBox.groups.emplace_back(std::make_unique<CollisionBoxElementGroup>()); + } + + collisionBox.vertices.add(anchor.x, anchor.y, tl.x, tl.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, tr.x, tr.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, tr.x, tr.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, br.x, br.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, br.x, br.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, bl.x, bl.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, bl.x, bl.y, maxZoom, placementZoom); + collisionBox.vertices.add(anchor.x, anchor.y, tl.x, tl.y, maxZoom, placementZoom); + + auto &group= *collisionBox.groups.back(); + group.vertex_length += 8; + } + } + } +} + +void SymbolBucket::swapRenderData() { + renderData = std::move(renderDataInProgress); +} + void SymbolBucket::drawGlyphs(SDFShader &shader) { char *vertex_index = BUFFER_OFFSET(0); char *elements_index = BUFFER_OFFSET(0); + auto& text = renderData->text; for (auto &group : text.groups) { assert(group); group->array[0].bind(shader, text.vertices, text.triangles, vertex_index); @@ -451,6 +562,7 @@ void SymbolBucket::drawGlyphs(SDFShader &shader) { void SymbolBucket::drawIcons(SDFShader &shader) { char *vertex_index = BUFFER_OFFSET(0); char *elements_index = BUFFER_OFFSET(0); + auto& icon = renderData->icon; for (auto &group : icon.groups) { assert(group); group->array[0].bind(shader, icon.vertices, icon.triangles, vertex_index); @@ -463,6 +575,7 @@ void SymbolBucket::drawIcons(SDFShader &shader) { void SymbolBucket::drawIcons(IconShader &shader) { char *vertex_index = BUFFER_OFFSET(0); char *elements_index = BUFFER_OFFSET(0); + auto& icon = renderData->icon; for (auto &group : icon.groups) { assert(group); group->array[1].bind(shader, icon.vertices, icon.triangles, vertex_index); @@ -471,4 +584,13 @@ void SymbolBucket::drawIcons(IconShader &shader) { elements_index += group->elements_length * icon.triangles.itemSize; } } + +void SymbolBucket::drawCollisionBoxes(CollisionBoxShader &shader) { + char *vertex_index = BUFFER_OFFSET(0); + auto& collisionBox = renderData->collisionBox; + for (auto &group : collisionBox.groups) { + group->array[0].bind(shader, collisionBox.vertices, vertex_index); + MBGL_CHECK_ERROR(glDrawArrays(GL_LINES, 0, group->vertex_length)); + } +} } diff --git a/src/mbgl/renderer/symbol_bucket.hpp b/src/mbgl/renderer/symbol_bucket.hpp index d0b133bc77..5654f9b2ba 100644 --- a/src/mbgl/renderer/symbol_bucket.hpp +++ b/src/mbgl/renderer/symbol_bucket.hpp @@ -7,8 +7,11 @@ #include <mbgl/geometry/elements_buffer.hpp> #include <mbgl/geometry/text_buffer.hpp> #include <mbgl/geometry/icon_buffer.hpp> -#include <mbgl/text/types.hpp> +#include <mbgl/geometry/collision_box_buffer.hpp> #include <mbgl/text/glyph.hpp> +#include <mbgl/text/collision_feature.hpp> +#include <mbgl/text/shaping.hpp> +#include <mbgl/text/quads.hpp> #include <mbgl/style/style_bucket.hpp> #include <mbgl/style/style_layout.hpp> @@ -20,7 +23,9 @@ namespace mbgl { class SDFShader; class IconShader; -class Collision; +class CollisionBoxShader; +class DotShader; +class CollisionTile; class SpriteAtlas; class Sprite; class GlyphAtlas; @@ -33,26 +38,33 @@ public: std::string sprite; }; - -class Symbol { -public: - vec2<float> tl, tr, bl, br; - Rect<uint16_t> tex; - float angle; - float minScale = 0.0f; - float maxScale = std::numeric_limits<float>::infinity(); - CollisionAnchor anchor; +struct Anchor; + +class SymbolInstance { + public: + explicit SymbolInstance(Anchor &anchor, const std::vector<Coordinate> &line, + const Shaping &shapedText, const PositionedIcon &shapedIcon, + const StyleLayoutSymbol &layout, const bool inside, + const float textBoxScale, const float textPadding, const float textAlongLine, + const float iconBoxScale, const float iconPadding, const float iconAlongLine, + const GlyphPositions &face); + float x; + float y; + bool hasText; + bool hasIcon; + SymbolQuads glyphQuads; + SymbolQuads iconQuads; + CollisionFeature textCollisionFeature; + CollisionFeature iconCollisionFeature; }; -typedef std::vector<Symbol> Symbols; - - class SymbolBucket : public Bucket { typedef ElementGroup<1> TextElementGroup; typedef ElementGroup<2> IconElementGroup; + typedef ElementGroup<1> CollisionBoxElementGroup; public: - SymbolBucket(Collision &collision); + SymbolBucket(CollisionTile &collision, float overscaling); ~SymbolBucket() override; void upload() override; @@ -60,6 +72,7 @@ public: bool hasData() const; bool hasTextData() const; bool hasIconData() const; + bool hasCollisionBoxData() const; void addFeatures(uintptr_t tileUID, SpriteAtlas&, @@ -70,38 +83,59 @@ public: void drawGlyphs(SDFShader& shader); void drawIcons(SDFShader& shader); void drawIcons(IconShader& shader); + void drawCollisionBoxes(CollisionBoxShader& shader); bool needsDependencies(const GeometryTileLayer&, const FilterExpression&, GlyphStore&, Sprite&); + void placeFeatures() override; private: - void addFeature(const std::vector<Coordinate> &line, const Shaping &shaping, const GlyphPositions &face, const Rect<uint16_t> &image); + void addFeature(const std::vector<std::vector<Coordinate>> &lines, + const Shaping &shapedText, const PositionedIcon &shapedIcon, + const GlyphPositions &face); + + void addToDebugBuffers(); + + void placeFeatures(bool swapImmediately); + void swapRenderData() override; // Adds placed items to the buffer. template <typename Buffer, typename GroupType> - void addSymbols(Buffer &buffer, const PlacedGlyphs &symbols, float scale, PlacementRange placementRange); + void addSymbols(Buffer &buffer, const SymbolQuads &symbols, float scale, const bool keepUpright, const bool alongLine); public: StyleLayoutSymbol layout; bool sdfIcons = false; private: - Collision &collision; + CollisionTile &collision; + const float overscaling; + std::vector<SymbolInstance> symbolInstances; std::vector<SymbolFeature> features; - struct TextBuffer { - TextVertexBuffer vertices; - TriangleElementsBuffer triangles; - std::vector<std::unique_ptr<TextElementGroup>> groups; - } text; - - struct IconBuffer { - IconVertexBuffer vertices; - TriangleElementsBuffer triangles; - std::vector<std::unique_ptr<IconElementGroup>> groups; - } icon; + struct SymbolRenderData { + struct TextBuffer { + TextVertexBuffer vertices; + TriangleElementsBuffer triangles; + std::vector<std::unique_ptr<TextElementGroup>> groups; + } text; + + struct IconBuffer { + IconVertexBuffer vertices; + TriangleElementsBuffer triangles; + std::vector<std::unique_ptr<IconElementGroup>> groups; + } icon; + + struct CollisionBoxBuffer { + CollisionBoxVertexBuffer vertices; + std::vector<std::unique_ptr<CollisionBoxElementGroup>> groups; + } collisionBox; + }; + + std::unique_ptr<SymbolRenderData> renderData; + std::unique_ptr<SymbolRenderData> renderDataInProgress; }; } diff --git a/src/mbgl/shader/box.fragment.glsl b/src/mbgl/shader/box.fragment.glsl new file mode 100644 index 0000000000..030f1219f8 --- /dev/null +++ b/src/mbgl/shader/box.fragment.glsl @@ -0,0 +1,24 @@ +uniform float u_zoom; +uniform float u_maxzoom; + +varying float v_max_zoom; +varying float v_placement_zoom; + +void main() { + + float alpha = 0.5; + + gl_FragColor = vec4(0.0, 1.0, 0.0, 1.0) * alpha; + + if (v_placement_zoom > u_zoom) { + gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0) * alpha; + } + + if (u_zoom >= v_max_zoom) { + gl_FragColor = vec4(0.0, 0.0, 0.0, 1.0) * alpha * 0.25; + } + + if (v_placement_zoom >= u_maxzoom) { + gl_FragColor = vec4(0.0, 0.0, 1.0, 1.0) * alpha * 0.2; + } +} diff --git a/src/mbgl/shader/box.vertex.glsl b/src/mbgl/shader/box.vertex.glsl new file mode 100644 index 0000000000..d141b13873 --- /dev/null +++ b/src/mbgl/shader/box.vertex.glsl @@ -0,0 +1,16 @@ +attribute vec2 a_pos; +attribute vec2 a_extrude; +attribute vec2 a_data; + +uniform mat4 u_matrix; +uniform float u_scale; + +varying float v_max_zoom; +varying float v_placement_zoom; + +void main() { + gl_Position = u_matrix * vec4(a_pos + a_extrude / u_scale, 0.0, 1.0); + + v_max_zoom = a_data.x; + v_placement_zoom = a_data.y; +} diff --git a/src/mbgl/shader/box_shader.cpp b/src/mbgl/shader/box_shader.cpp new file mode 100644 index 0000000000..2676223a9d --- /dev/null +++ b/src/mbgl/shader/box_shader.cpp @@ -0,0 +1,32 @@ +#include <mbgl/shader/box_shader.hpp> +#include <mbgl/shader/shaders.hpp> +#include <mbgl/platform/gl.hpp> + +#include <cstdio> + +using namespace mbgl; + +CollisionBoxShader::CollisionBoxShader() + : Shader( + "collisionbox", + shaders[BOX_SHADER].vertex, + shaders[BOX_SHADER].fragment + ) { + a_pos = MBGL_CHECK_ERROR(glGetAttribLocation(program, "a_pos")); + a_extrude = MBGL_CHECK_ERROR(glGetAttribLocation(program, "a_extrude")); + a_data = MBGL_CHECK_ERROR(glGetAttribLocation(program, "a_data")); +} + +void CollisionBoxShader::bind(char *offset) { + const int stride = 12; + + MBGL_CHECK_ERROR(glEnableVertexAttribArray(a_pos)); + MBGL_CHECK_ERROR(glVertexAttribPointer(a_pos, 2, GL_SHORT, false, stride, offset + 0)); + + MBGL_CHECK_ERROR(glEnableVertexAttribArray(a_extrude)); + MBGL_CHECK_ERROR(glVertexAttribPointer(a_extrude, 2, GL_SHORT, false, stride, offset + 4)); + + MBGL_CHECK_ERROR(glEnableVertexAttribArray(a_data)); + MBGL_CHECK_ERROR(glVertexAttribPointer(a_data, 2, GL_UNSIGNED_BYTE, false, stride, offset + 8)); + +} diff --git a/src/mbgl/shader/box_shader.hpp b/src/mbgl/shader/box_shader.hpp new file mode 100644 index 0000000000..5c84d8906c --- /dev/null +++ b/src/mbgl/shader/box_shader.hpp @@ -0,0 +1,28 @@ +#ifndef MBGL_SHADER_SHADER_BOX +#define MBGL_SHADER_SHADER_BOX + +#include <mbgl/shader/shader.hpp> +#include <mbgl/shader/uniform.hpp> + +namespace mbgl { + +class CollisionBoxShader : public Shader { +public: + CollisionBoxShader(); + + void bind(char *offset); + + UniformMatrix<4> u_matrix = {"u_matrix", *this}; + Uniform<float> u_scale = {"u_scale", *this}; + Uniform<float> u_zoom = {"u_zoom", *this}; + Uniform<float> u_maxzoom = {"u_maxzoom", *this}; + +protected: + int32_t a_pos = -1; + int32_t a_extrude = -1; + int32_t a_data = -1; +}; + +} + +#endif diff --git a/src/mbgl/shader/icon.vertex.glsl b/src/mbgl/shader/icon.vertex.glsl index fd7afd5b7d..549570021d 100644 --- a/src/mbgl/shader/icon.vertex.glsl +++ b/src/mbgl/shader/icon.vertex.glsl @@ -8,9 +8,7 @@ attribute vec4 a_data2; // the extrusion vector. uniform mat4 u_matrix; uniform mat4 u_exmatrix; -uniform float u_angle; uniform float u_zoom; -uniform float u_flip; uniform float u_fadedist; uniform float u_minfadezoom; uniform float u_maxfadezoom; @@ -29,24 +27,11 @@ void main() { vec2 a_zoom = a_data2.st; float a_minzoom = a_zoom[0]; float a_maxzoom = a_zoom[1]; - vec2 a_range = a_data2.pq; - float a_rangeend = a_range[0]; - float a_rangestart = a_range[1]; float a_fadedist = 10.0; - float rev = 0.0; - // u_angle is angle of the map, -128..128 representing 0..2PI - // a_angle is angle of the label, 0..256 representing 0..2PI, where 0 is horizontal text - float rotated = mod(a_angle + u_angle, 256.0); - // if the label rotates with the map, and if the rotated label is upside down, hide it - if (u_flip > 0.0 && rotated >= 64.0 && rotated < 192.0) rev = 1.0; - - // If the label should be invisible, we move the vertex outside - // of the view plane so that the triangle gets clipped. This makes it easier - // for us to create degenerate triangle strips. // u_zoom is the current zoom level adjusted for the change in font size - float z = 2.0 - step(a_minzoom, u_zoom) - (1.0 - step(a_maxzoom, u_zoom)) + rev; + float z = 2.0 - step(a_minzoom, u_zoom) - (1.0 - step(a_maxzoom, u_zoom)); // fade out labels float alpha = clamp((u_fadezoom - a_labelminzoom) / u_fadedist, 0.0, 1.0); @@ -66,10 +51,6 @@ void main() { // if label has been faded out, clip it z += step(v_alpha, 0.0); - // all the angles are 0..256 representing 0..2PI - // hide if (angle >= a_rangeend && angle < rangestart) - z += step(a_rangeend, u_angle) * (1.0 - step(a_rangestart, u_angle)); - gl_Position = u_matrix * vec4(a_pos, 0, 1) + u_exmatrix * vec4(a_offset / 64.0, z, 0); v_tex = a_tex / u_texsize; diff --git a/src/mbgl/shader/icon_shader.hpp b/src/mbgl/shader/icon_shader.hpp index 155b9addca..b6156ae9a0 100644 --- a/src/mbgl/shader/icon_shader.hpp +++ b/src/mbgl/shader/icon_shader.hpp @@ -14,9 +14,7 @@ public: UniformMatrix<4> u_matrix = {"u_matrix", *this}; UniformMatrix<4> u_exmatrix = {"u_exmatrix", *this}; - Uniform<float> u_angle = {"u_angle", *this}; Uniform<float> u_zoom = {"u_zoom", *this}; - Uniform<float> u_flip = {"u_flip", *this}; Uniform<float> u_fadedist = {"u_fadedist", *this}; Uniform<float> u_minfadezoom = {"u_minfadezoom", *this}; Uniform<float> u_maxfadezoom = {"u_maxfadezoom", *this}; diff --git a/src/mbgl/shader/sdf.vertex.glsl b/src/mbgl/shader/sdf.vertex.glsl index bbfc44919e..416a9bca58 100644 --- a/src/mbgl/shader/sdf.vertex.glsl +++ b/src/mbgl/shader/sdf.vertex.glsl @@ -8,9 +8,7 @@ attribute vec4 a_data2; // the extrusion vector. uniform mat4 u_matrix; uniform mat4 u_exmatrix; -uniform float u_angle; uniform float u_zoom; -uniform float u_flip; uniform float u_fadedist; uniform float u_minfadezoom; uniform float u_maxfadezoom; @@ -28,23 +26,9 @@ void main() { vec2 a_zoom = a_data2.st; float a_minzoom = a_zoom[0]; float a_maxzoom = a_zoom[1]; - vec2 a_range = a_data2.pq; - float a_rangeend = a_range[0]; - float a_rangestart = a_range[1]; - float rev = 0.0; - - // u_angle is angle of the map, -128..128 representing 0..2PI - // a_angle is angle of the label, 0..256 representing 0..2PI, where 0 is horizontal text - float rotated = mod(a_angle + u_angle, 256.0); - // if the label rotates with the map, and if the rotated label is upside down, hide it - if (u_flip > 0.0 && rotated >= 64.0 && rotated < 192.0) rev = 1.0; - - // If the label should be invisible, we move the vertex outside - // of the view plane so that the triangle gets clipped. This makes it easier - // for us to create degenerate triangle strips. // u_zoom is the current zoom level adjusted for the change in font size - float z = 2.0 - step(a_minzoom, u_zoom) - (1.0 - step(a_maxzoom, u_zoom)) + rev; + float z = 2.0 - step(a_minzoom, u_zoom) - (1.0 - step(a_maxzoom, u_zoom)); // fade out labels float alpha = clamp((u_fadezoom - a_labelminzoom) / u_fadedist, 0.0, 1.0); @@ -64,10 +48,6 @@ void main() { // if label has been faded out, clip it z += step(v_alpha, 0.0); - // all the angles are 0..256 representing 0..2PI - // hide if (angle >= a_rangeend && angle < rangestart) - z += step(a_rangeend, u_angle) * (1.0 - step(a_rangestart, u_angle)); - gl_Position = u_matrix * vec4(a_pos, 0, 1) + u_exmatrix * vec4(a_offset / 64.0, z, 0); v_tex = a_tex / u_texsize; } diff --git a/src/mbgl/shader/sdf_shader.hpp b/src/mbgl/shader/sdf_shader.hpp index 08f3053b7d..36dfa30d3e 100644 --- a/src/mbgl/shader/sdf_shader.hpp +++ b/src/mbgl/shader/sdf_shader.hpp @@ -18,9 +18,7 @@ public: Uniform<std::array<float, 2>> u_texsize = {"u_texsize", *this}; Uniform<float> u_buffer = {"u_buffer", *this}; Uniform<float> u_gamma = {"u_gamma", *this}; - Uniform<float> u_angle = {"u_angle", *this}; Uniform<float> u_zoom = {"u_zoom", *this}; - Uniform<float> u_flip = {"u_flip", *this}; Uniform<float> u_fadedist = {"u_fadedist", *this}; Uniform<float> u_minfadezoom = {"u_minfadezoom", *this}; Uniform<float> u_maxfadezoom = {"u_maxfadezoom", *this}; diff --git a/src/mbgl/text/check_max_angle.cpp b/src/mbgl/text/check_max_angle.cpp new file mode 100644 index 0000000000..73e7dd26be --- /dev/null +++ b/src/mbgl/text/check_max_angle.cpp @@ -0,0 +1,78 @@ +#include <mbgl/text/check_max_angle.hpp> +#include <queue> + +namespace mbgl{ + +struct Corner { + Corner(float _distance, float _angleDelta) : + distance(_distance), angleDelta(_angleDelta) {} + float distance; + float angleDelta; +}; + +bool checkMaxAngle(const std::vector<Coordinate> &line, Anchor &anchor, const float labelLength, + const float windowSize, const float maxAngle) { + + // horizontal labels always pass + if (anchor.segment < 0) return true; + + Coordinate anchorPoint = Coordinate{ (int16_t)anchor.x, (int16_t)anchor.y }; + Coordinate &p = anchorPoint; + int index = anchor.segment + 1; + float anchorDistance = 0; + + // move backwards along the line to the first segment the label appears on + while (anchorDistance > -labelLength / 2) { + index--; + + // there isn't enough room for the label after the beginning of the line + if (index < 0) return false; + + anchorDistance -= util::dist<float>(line[index], p); + p = line[index]; + } + + anchorDistance += util::dist<float>(line[index], line[index + 1]); + index++; + + // store recent corners and their total angle difference + std::queue<Corner> recentCorners; + float recentAngleDelta = 0; + + // move forwards by the length of the label and check angles along the way + while (anchorDistance < labelLength / 2) { + + // there isn't enough room for the label before the end of the line + if (index + 1 >= (int)line.size()) return false; + + auto& prev = line[index - 1]; + auto& current = line[index]; + auto& next = line[index + 1]; + + float angleDelta = util::angle_to(prev, current) - util::angle_to(current, next); + // restrict angle to -pi..pi range + angleDelta = std::fmod(angleDelta + 3 * M_PI, M_PI * 2) - M_PI; + + recentCorners.emplace(anchorDistance, angleDelta); + recentAngleDelta += angleDelta; + + // remove corners that are far enough away from the list of recent anchors + while (anchorDistance - recentCorners.front().distance > windowSize) { + recentAngleDelta -= recentCorners.front().angleDelta; + recentCorners.pop(); + } + + // the sum of angles within the window area exceeds the maximum allowed value. check fails. + if (std::fabs(recentAngleDelta) > maxAngle) return false; + + index++; + anchorDistance += util::dist<float>(current, next); + } + + // no part of the line had an angle greater than the maximum allowed. check passes. + return true; + + +} + +} diff --git a/src/mbgl/text/check_max_angle.hpp b/src/mbgl/text/check_max_angle.hpp new file mode 100644 index 0000000000..5a881ebbad --- /dev/null +++ b/src/mbgl/text/check_max_angle.hpp @@ -0,0 +1,14 @@ +#ifndef MBGL_TEXT_CHECK_MAX_ANGLE +#define MBGL_TEXT_CHECK_MAX_ANGLE + +#include <mbgl/geometry/anchor.hpp> +#include <mbgl/util/math.hpp> + +namespace mbgl { + +bool checkMaxAngle(const std::vector<Coordinate> &line, Anchor &anchor, const float labelLength, + const float windowSize, const float maxAngle); + +} + +#endif diff --git a/src/mbgl/text/collision.cpp b/src/mbgl/text/collision.cpp deleted file mode 100644 index ba32b87d2f..0000000000 --- a/src/mbgl/text/collision.cpp +++ /dev/null @@ -1,307 +0,0 @@ -#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 auto& 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 auto& 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 auto& 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 sx = (na.x - oa.x); - float s1 = 1; - float s2 = 1; - if (sx != 0) { - s1 = (ob.tl.x - nb.br.x - padding) / - sx; // scale at which new box is to the left of old box - s2 = (ob.br.x - nb.tl.x + padding) / - sx; // scale at which new box is to the right of old box - } - float sy = (na.y - oa.y); - float s3 = 1; - float s4 = 1; - if (sy != 0) { - s3 = (ob.tl.y - nb.br.y - padding) / - sy; // scale at which new box is to the top of old box - s4 = (ob.br.y - nb.tl.y + padding) / - sy; // 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 auto& 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 auto& 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 auto& 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 deleted file mode 100644 index 50b8e5b218..0000000000 --- a/src/mbgl/text/collision.hpp +++ /dev/null @@ -1,61 +0,0 @@ -#ifndef MBGL_TEXT_COLLISION -#define MBGL_TEXT_COLLISION - -#include <mbgl/text/types.hpp> - -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Wunused-function" -#pragma GCC diagnostic ignored "-Wunused-parameter" -#pragma GCC diagnostic ignored "-Wunused-variable" -#pragma GCC diagnostic ignored "-Wshadow" -#ifdef __clang__ -#pragma GCC diagnostic ignored "-Wunknown-pragmas" -#endif -#pragma GCC diagnostic ignored "-Wpragmas" -#pragma GCC diagnostic ignored "-Wdeprecated-register" -#pragma GCC diagnostic ignored "-Wshorten-64-to-32" -#pragma GCC diagnostic ignored "-Wunused-local-typedefs" -#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" -#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/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp new file mode 100644 index 0000000000..2a61e0b10e --- /dev/null +++ b/src/mbgl/text/collision_feature.cpp @@ -0,0 +1,95 @@ +#include <mbgl/text/collision_feature.hpp> +#include <mbgl/util/math.hpp> + +namespace mbgl { + +CollisionFeature::CollisionFeature(const std::vector<Coordinate> &line, const Anchor &anchor, + const float top, const float bottom, const float left, const float right, + const float boxScale, const float padding, const bool alongLine) { + + if (top == 0 && bottom == 0 && left == 0 && right == 0) return; + + const float y1 = top * boxScale - padding; + const float y2 = bottom * boxScale + padding; + const float x1 = left * boxScale - padding; + const float x2 = right * boxScale + padding; + + if (alongLine) { + float height = y2 - y1; + const float length = x2 - x1; + + if (height <= 0.0f) return; + + height = std::max(10.0f * boxScale, height); + + bboxifyLabel(line, anchor, length, height); + } else { + boxes.emplace_back(anchor, x1, y1, x2, y2, std::numeric_limits<float>::infinity()); + } +} + +void CollisionFeature::bboxifyLabel(const std::vector<Coordinate> &line, + const Anchor &anchor, const float labelLength, const float boxSize) { + + const float step = boxSize / 2; + const unsigned int nBoxes = std::floor(labelLength / step); + + // offset the center of the first box by half a box so that the edge of the + // box is at the edge of the label. + const float firstBoxOffset = -boxSize / 2; + + Coordinate anchorPoint = Coordinate{ (int16_t)anchor.x, (int16_t)anchor.y }; + + Coordinate &p = anchorPoint; + int index = anchor.segment + 1; + float anchorDistance = firstBoxOffset; + + // move backwards along the line to the first segment the label appears on + do { + index--; + + // there isn't enough room for the label after the beginning of the line + // checkMaxAngle should have already caught this + if (index < 0) return; + + anchorDistance -= util::dist<float>(line[index], p); + p = line[index]; + } while (anchorDistance > -labelLength / 2); + + float segmentLength = util::dist<float>(line[index], line[index + 1]); + + for (unsigned int i = 0; i < nBoxes; i++) { + // the distance the box will be from the anchor + const float boxDistanceToAnchor = -labelLength / 2 + i * step; + + // the box is not on the current segment. Move to the next segment. + while (anchorDistance + segmentLength < boxDistanceToAnchor) { + anchorDistance += segmentLength; + index++; + + // There isn't enough room before the end of the line. + if (index + 1 >= (int)line.size()) return; + + segmentLength = util::dist<float>(line[index], line[index + 1]); + } + + // the distance the box will be from the beginning of the segment + const float segmentBoxDistance = boxDistanceToAnchor - anchorDistance; + + const auto& p0 = line[index]; + const auto& p1 = line[index + 1]; + + vec2<float> boxAnchor = { + p0.x + segmentBoxDistance / segmentLength * (p1.x - p0.x), + p0.y + segmentBoxDistance / segmentLength * (p1.y - p0.y) + }; + + const float distanceToInnerEdge = std::max(std::fabs(boxDistanceToAnchor - firstBoxOffset) - step / 2, 0.0f); + const float maxScale = labelLength / 2 / distanceToInnerEdge; + + boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale); + } +} + + +} diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp new file mode 100644 index 0000000000..06056c2a20 --- /dev/null +++ b/src/mbgl/text/collision_feature.hpp @@ -0,0 +1,62 @@ +#ifndef MBGL_TEXT_COLLISION_FEATURE +#define MBGL_TEXT_COLLISION_FEATURE + +#include <mbgl/util/vec.hpp> +#include <mbgl/geometry/anchor.hpp> +#include <mbgl/text/shaping.hpp> +#include <vector> + +namespace mbgl { + class CollisionBox { + public: + explicit CollisionBox(const vec2<float> &_anchor, float _x1, float _y1, float _x2, float _y2, float _maxScale) : + anchor(_anchor), x1(_x1), y1(_y1), x2(_x2), y2(_y2), maxScale(_maxScale) {} + + // the box is centered around the anchor point + vec2<float> anchor; + + // distances to the edges from the anchor + float x1; + float y1; + float x2; + float y2; + + // the box is only valid for scales < maxScale. + // The box does not block other boxes at scales >= maxScale; + float maxScale; + + // the scale at which the label can first be shown + float placementScale = 0.0f; + }; + + class CollisionFeature { + public: + // for text + inline explicit CollisionFeature(const std::vector<Coordinate> &line, const Anchor &anchor, + const Shaping &shapedText, + const float boxScale, const float padding, const bool alongLine) + : CollisionFeature(line, anchor, + shapedText.top, shapedText.bottom, shapedText.left, shapedText.right, + boxScale, padding, alongLine) {} + + // for icons + inline explicit CollisionFeature(const std::vector<Coordinate> &line, const Anchor &anchor, + const PositionedIcon &shapedIcon, + const float boxScale, const float padding, const bool alongLine) + : CollisionFeature(line, anchor, + shapedIcon.top, shapedIcon.bottom, shapedIcon.left, shapedIcon.right, + boxScale, padding, alongLine) {} + + explicit CollisionFeature(const std::vector<Coordinate> &line, const Anchor &anchor, + const float top, const float bottom, const float left, const float right, + const float boxScale, const float padding, const bool alongLine); + + + std::vector<CollisionBox> boxes; + + private: + void bboxifyLabel(const std::vector<Coordinate> &line, const Anchor &anchor, const float length, const float height); + }; +} + +#endif diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp new file mode 100644 index 0000000000..0d1b25af54 --- /dev/null +++ b/src/mbgl/text/collision_tile.cpp @@ -0,0 +1,105 @@ +#include <mbgl/text/collision_tile.hpp> +#include <cmath> + +namespace mbgl { + +void CollisionTile::reset(const float _angle, const float pitch) { + tree.clear(); + angle = _angle; + + // Compute the transformation matrix. + float angle_sin = std::sin(_angle); + float angle_cos = std::cos(_angle); + rotationMatrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}}; + + // Stretch boxes in y direction to account for the map tilt. + const float _yStretch = 1.0f / std::cos(pitch / 180 * M_PI); + + // The amount the map is squished depends on the y position. + // Sort of account for this by making all boxes a bit bigger. + yStretch = std::pow(_yStretch, 1.3); +} + +float CollisionTile::placeFeature(const CollisionFeature &feature) { + + float minPlacementScale = minScale; + + for (auto& box : feature.boxes) { + const auto anchor = box.anchor.matMul(rotationMatrix); + + std::vector<CollisionTreeBox> blockingBoxes; + tree.query(bgi::intersects(getTreeBox(anchor, box)), std::back_inserter(blockingBoxes)); + + for (auto& blockingTreeBox : blockingBoxes) { + const auto& blocking = std::get<1>(blockingTreeBox); + auto blockingAnchor = blocking.anchor.matMul(rotationMatrix); + + // Find the lowest scale at which the two boxes can fit side by side without overlapping. + // Original algorithm: + float s1 = (blocking.x1 - box.x2) / (anchor.x - blockingAnchor.x); // scale at which new box is to the left of old box + float s2 = (blocking.x2 - box.x1) / (anchor.x - blockingAnchor.x); // scale at which new box is to the right of old box + float s3 = (blocking.y1 - box.y2) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the top of old box + float s4 = (blocking.y2 - box.y1) * yStretch / (anchor.y - blockingAnchor.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; + + float collisionFreeScale = std::fmin(std::fmax(s1, s2), std::fmax(s3, s4)); + + if (collisionFreeScale > blocking.maxScale) { + // After a box's maxScale the label has shrunk enough that the box is no longer needed to cover it, + // so unblock the new box at the scale that the old box disappears. + collisionFreeScale = blocking.maxScale; + } + + if (collisionFreeScale > box.maxScale) { + // If the box can only be shown after it is visible, then the box can never be shown. + // But the label can be shown after this box is not visible. + collisionFreeScale = box.maxScale; + } + + if (collisionFreeScale > minPlacementScale && + collisionFreeScale >= blocking.placementScale) { + // If this collision occurs at a lower scale than previously found collisions + // and the collision occurs while the other label is visible + + // this this is the lowest scale at which the label won't collide with anything + minPlacementScale = collisionFreeScale; + } + + if (minPlacementScale >= maxScale) return minPlacementScale; + } + } + + return minPlacementScale; +} + +void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlacementScale) { + for (auto& box : feature.boxes) { + box.placementScale = minPlacementScale; + } + + if (minPlacementScale < maxScale) { + std::vector<CollisionTreeBox> treeBoxes; + for (auto& box : feature.boxes) { + treeBoxes.emplace_back(getTreeBox(box.anchor.matMul(rotationMatrix), box), box); + } + tree.insert(treeBoxes.begin(), treeBoxes.end()); + } + +} + +Box CollisionTile::getTreeBox(const vec2<float> &anchor, const CollisionBox &box) { + return Box{ + Point{ + anchor.x + box.x1, + anchor.y + box.y1 * yStretch + }, + Point{ + anchor.x + box.x2, + anchor.y + box.y2 * yStretch + } + }; +} + +} diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp new file mode 100644 index 0000000000..882f347b46 --- /dev/null +++ b/src/mbgl/text/collision_tile.hpp @@ -0,0 +1,67 @@ +#ifndef MBGL_TEXT_COLLISION_TILE +#define MBGL_TEXT_COLLISION_TILE + +#include <mbgl/text/collision_feature.hpp> + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-function" +#pragma GCC diagnostic ignored "-Wunused-parameter" +#pragma GCC diagnostic ignored "-Wunused-variable" +#pragma GCC diagnostic ignored "-Wshadow" +#ifdef __clang__ +#pragma GCC diagnostic ignored "-Wunknown-pragmas" +#endif +#pragma GCC diagnostic ignored "-Wpragmas" +#pragma GCC diagnostic ignored "-Wdeprecated-register" +#pragma GCC diagnostic ignored "-Wshorten-64-to-32" +#pragma GCC diagnostic ignored "-Wunused-local-typedefs" +#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" +#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, CollisionBox> CollisionTreeBox; + typedef bgi::rtree<CollisionTreeBox, bgi::linear<16,4>> Tree; + +class CollisionTile { + + public: + inline explicit CollisionTile(float _zoom, float tileExtent, float tileSize, float angle_, bool debug_) : + zoom(_zoom), tilePixelRatio(tileExtent / tileSize), debug(debug_) { reset(angle_, 0); } + + void reset(const float angle, const float pitch); + float placeFeature(const CollisionFeature &feature); + void insertFeature(CollisionFeature &feature, const float minPlacementScale); + + void setDebug(bool debug_) { debug = debug_; } + bool getDebug() { return debug; } + + const float zoom; + const float tilePixelRatio; + float angle = 0; + + const float minScale = 0.5f; + const float maxScale = 2.0f; + + private: + + Box getTreeBox(const vec2<float> &anchor, const CollisionBox &box); + + Tree tree; + std::array<float, 4> rotationMatrix; + float yStretch; + bool debug; + +}; +} + +#endif diff --git a/src/mbgl/text/font_stack.cpp b/src/mbgl/text/font_stack.cpp index 4bec6b1b48..fc1be0fb72 100644 --- a/src/mbgl/text/font_stack.cpp +++ b/src/mbgl/text/font_stack.cpp @@ -1,5 +1,5 @@ #include <mbgl/text/font_stack.hpp> - +#include <cassert> #include <mbgl/util/math.hpp> namespace mbgl { @@ -22,21 +22,24 @@ const Shaping FontStack::getShaping(const std::u32string &string, const float ma const float lineHeight, const float horizontalAlign, const float verticalAlign, const float justify, const float spacing, const vec2<float> &translate) const { - Shaping shaping; + Shaping shaping(translate.x * 24, translate.y * 24); + + // the y offset *should* be part of the font metadata + const int32_t yOffset = -17; int32_t x = std::round(translate.x * 24); // one em - const int32_t y = std::round(translate.y * 24); // one em + const int32_t y = std::round(translate.y * 24) + yOffset; // 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()) { + shaping.positionedGlyphs.emplace_back(chr, x, y); x += metric->second.advance + spacing; } } - if (!shaping.size()) + if (!shaping.positionedGlyphs.size()) return shaping; lineWrap(shaping, lineHeight, maxWidth, horizontalAlign, verticalAlign, justify); @@ -50,22 +53,22 @@ void align(Shaping &shaping, const float justify, const float horizontalAlign, const float shiftX = (justify - horizontalAlign) * maxLineLength; const float shiftY = (-verticalAlign * (line + 1) + 0.5) * lineHeight; - for (auto& glyph : shaping) { + for (auto& glyph : shaping.positionedGlyphs) { glyph.x += shiftX; glyph.y += shiftY; } } -void justifyLine(Shaping &shaping, const std::map<uint32_t, GlyphMetrics> &metrics, uint32_t start, +void justifyLine(std::vector<PositionedGlyph> &positionedGlyphs, const std::map<uint32_t, GlyphMetrics> &metrics, uint32_t start, uint32_t end, float justify) { - PositionedGlyph &glyph = shaping[end]; + PositionedGlyph &glyph = positionedGlyphs[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; + positionedGlyphs[j].x -= lineIndent; } } } @@ -81,25 +84,27 @@ void FontStack::lineWrap(Shaping &shaping, const float lineHeight, const float m uint32_t maxLineLength = 0; + std::vector<PositionedGlyph> &positionedGlyphs = shaping.positionedGlyphs; + if (maxWidth) { - for (uint32_t i = 0; i < shaping.size(); i++) { - PositionedGlyph &shape = shaping[i]; + for (uint32_t i = 0; i < positionedGlyphs.size(); i++) { + PositionedGlyph &shape = positionedGlyphs[i]; shape.x -= lengthBeforeCurrentLine; shape.y += lineHeight * line; if (shape.x > maxWidth && lastSafeBreak > 0) { - uint32_t lineLength = shaping[lastSafeBreak + 1].x; + uint32_t lineLength = positionedGlyphs[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; + positionedGlyphs[k].y += lineHeight; + positionedGlyphs[k].x -= lineLength; } if (justify) { - justifyLine(shaping, metrics, lineStartIndex, lastSafeBreak - 1, justify); + justifyLine(positionedGlyphs, metrics, lineStartIndex, lastSafeBreak - 1, justify); } lineStartIndex = lastSafeBreak + 1; @@ -114,10 +119,22 @@ void FontStack::lineWrap(Shaping &shaping, const float lineHeight, const float m } } - if (!maxLineLength) maxLineLength = shaping.back().x; + const PositionedGlyph& lastPositionedGlyph = positionedGlyphs.back(); + const auto lastGlyphMetric = metrics.find(lastPositionedGlyph.glyph); + assert(lastGlyphMetric != metrics.end()); + const uint32_t lastLineLength = lastPositionedGlyph.x + lastGlyphMetric->second.advance; + maxLineLength = std::max(maxLineLength, lastLineLength); - justifyLine(shaping, metrics, lineStartIndex, uint32_t(shaping.size()) - 1, justify); + const uint32_t height = (line + 1) * lineHeight; + + justifyLine(positionedGlyphs, metrics, lineStartIndex, uint32_t(positionedGlyphs.size()) - 1, justify); align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight, line); + + // Calculate the bounding box + shaping.top += -verticalAlign * height; + shaping.bottom = shaping.top + height; + shaping.left += -horizontalAlign * maxLineLength; + shaping.right = shaping.left + maxLineLength; } } // end namespace mbgl diff --git a/src/mbgl/text/get_anchors.cpp b/src/mbgl/text/get_anchors.cpp new file mode 100644 index 0000000000..88c09983a6 --- /dev/null +++ b/src/mbgl/text/get_anchors.cpp @@ -0,0 +1,79 @@ +#include <mbgl/text/get_anchors.hpp> +#include <mbgl/text/check_max_angle.hpp> + +#include <mbgl/util/interpolate.hpp> + +#include <cmath> + +namespace mbgl { + +Anchors resample(const std::vector<Coordinate> &line, const float offset, const float spacing, + const float angleWindowSize, const float maxAngle, const float labelLength, const bool placeAtMiddle) { + + float distance = 0; + float markedDistance = offset != 0.0f ? offset - spacing : 0; + + Anchors anchors; + + auto end = line.end() - 1; + int i = 0; + for (auto it = line.begin(); it != end; it++, i++) { + const Coordinate &a = *(it); + const Coordinate &b = *(it + 1); + + const float segmentDist = util::dist<float>(a, b); + const float angle = util::angle_to(b, a); + + while (markedDistance + spacing < distance + segmentDist) { + markedDistance += spacing; + + float t = (markedDistance - distance) / segmentDist, + x = util::interpolate(float(a.x), float(b.x), t), + y = util::interpolate(float(a.y), float(b.y), t); + + if (x >= 0 && x < 4096 && y >= 0 && y < 4096) { + Anchor anchor(std::round(x), std::round(y), angle, 0.5f, i); + + if (!angleWindowSize || checkMaxAngle(line, anchor, labelLength, angleWindowSize, maxAngle)) { + anchors.push_back(anchor); + } + } + } + + distance += segmentDist; + } + + if (!placeAtMiddle && !anchors.size()) { + // The first attempt at finding anchors at which labels can be placed failed. + // Try again, but this time just try placing one anchor at the middle of the line. + // This has the most effect for short lines in overscaled tiles, since the + // initial offset used in overscaled tiles is calculated to align labels with positions in + // parent tiles instead of placing the label as close to the beginning as possible. + anchors = std::move(resample(line, distance / 2, spacing, angleWindowSize, maxAngle, labelLength, true)); + } + + return anchors; +} + +Anchors getAnchors(const std::vector<Coordinate> &line, float spacing, + const bool maxAngle, const float left, const float right, + const float glyphSize, const float boxScale, const float overscaling) { + + // Resample a line to get anchor points for labels and check that each + // potential label passes text-max-angle check and has enough froom to fit + // on the line. + + const float angleWindowSize = (left - right) != 0.0f ? + 3.0f / 5.0f * glyphSize * boxScale : + 0; + + // Offset the first anchor by half the label length (or half the spacing distance for icons). + // Add a bit of extra offset to avoid collisions at T intersections. + const float labelLength = right - left ? right - left : spacing; + const float extraOffset = glyphSize * 2; + const float offset = std::fmod((labelLength / 2 + extraOffset) * boxScale * overscaling, spacing); + + return resample(line, offset, spacing, angleWindowSize, maxAngle, labelLength * boxScale, false); +} + +} diff --git a/src/mbgl/text/get_anchors.hpp b/src/mbgl/text/get_anchors.hpp new file mode 100644 index 0000000000..ca879d2243 --- /dev/null +++ b/src/mbgl/text/get_anchors.hpp @@ -0,0 +1,14 @@ +#ifndef MBGL_TEXT_GETANCHORS +#define MBGL_TEXT_GETANCHORS + +#include <mbgl/geometry/anchor.hpp> +#include <mbgl/util/math.hpp> + +namespace mbgl { + +Anchors getAnchors(const std::vector<Coordinate> &line, float spacing, + const bool maxAngle, const float left, const float right, + const float glyphSize, const float boxScale, const float overscaling); +} + +#endif diff --git a/src/mbgl/text/glyph.hpp b/src/mbgl/text/glyph.hpp index 0677bcff30..be7c9befd5 100644 --- a/src/mbgl/text/glyph.hpp +++ b/src/mbgl/text/glyph.hpp @@ -55,7 +55,19 @@ public: float y = 0; }; -typedef std::vector<PositionedGlyph> Shaping; +class Shaping { + public: + inline explicit Shaping() : top(0), bottom(0), left(0), right(0) {} + inline explicit Shaping(float x, float y) + : top(y), bottom(y), left(x), right(x) {} + std::vector<PositionedGlyph> positionedGlyphs; + int32_t top; + int32_t bottom; + int32_t left; + int32_t right; + + operator bool() const { return positionedGlyphs.size(); } +}; class SDFGlyph { public: diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp deleted file mode 100644 index 6c24d26fd0..0000000000 --- a/src/mbgl/text/placement.cpp +++ /dev/null @@ -1,316 +0,0 @@ -#include <mbgl/text/placement.hpp> -#include <mbgl/geometry/anchor.hpp> -#include <mbgl/text/glyph.hpp> -#include <mbgl/text/placement.hpp> -#include <mbgl/text/glyph_store.hpp> -#include <mbgl/style/style_bucket.hpp> -#include <mbgl/style/style_layout.hpp> - -#include <mbgl/util/math.hpp> - -namespace mbgl { - -const float Placement::globalMinScale = 0.5; // underscale by 1 zoom level - -struct GlyphInstance { - explicit GlyphInstance(const vec2<float> &anchor_) : anchor(anchor_) {} - explicit GlyphInstance(const vec2<float> &anchor_, float offset_, float minScale_, float maxScale_, - float angle_) - : anchor(anchor_), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {} - - const vec2<float> anchor; - const float offset = 0.0f; - const float minScale = Placement::globalMinScale; - const float maxScale = std::numeric_limits<float>::infinity(); - const float angle = 0.0f; -}; - -typedef std::vector<GlyphInstance> GlyphInstances; - -void getSegmentGlyphs(std::back_insert_iterator<GlyphInstances> glyphs, Anchor &anchor, - float offset, const std::vector<Coordinate> &line, int segment, - int8_t direction, float maxAngle) { - const bool upsideDown = direction < 0; - - if (offset < 0) - direction *= -1; - - if (direction > 0) - segment++; - - vec2<float> newAnchor = anchor; - - if ((int)line.size() <= segment) { - return; - } - vec2<float> end = line[segment]; - float prevscale = std::numeric_limits<float>::infinity(); - float prevAngle = 0.0f; - - offset = std::fabs(offset); - - const float placementScale = anchor.scale; - - while (true) { - const float dist = util::dist<float>(newAnchor, end); - if (dist == 0) { - break; - } - 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 auto& glyph : glyphs) { - const CollisionRect &gbox = glyph.box; - box.tl.x = util::min(box.tl.x, gbox.tl.x); - box.tl.y = util::min(box.tl.y, gbox.tl.y); - box.br.x = util::max(box.br.x, gbox.br.x); - box.br.y = util::max(box.br.y, gbox.br.y); - mergedglyphs.minScale = util::max(mergedglyphs.minScale, glyph.minScale); - mergedglyphs.padding = util::max(mergedglyphs.padding, glyph.padding); - } - // for all horizontal labels, calculate bbox covering all rotated positions - float x12 = box.tl.x * box.tl.x, y12 = box.tl.y * box.tl.y, x22 = box.br.x * box.br.x, - y22 = box.br.y * box.br.y, - diag = std::sqrt(util::max(x12 + y12, x12 + y22, x22 + y12, x22 + y22)); - - mergedglyphs.hBox = CollisionRect{-diag, -diag, diag, diag}; - - return mergedglyphs; -} - -Placement Placement::getIcon(Anchor &anchor, const Rect<uint16_t> &image, float boxScale, - const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout) { - - const float padding = 1.0f; - const float dx = layout.icon.offset[0]; - const float dy = layout.icon.offset[1]; - float x1 = dx - image.originalW / 2.0f - padding; - float x2 = x1 + image.w; - float y1 = dy - image.originalH / 2.0f - padding; - float y2 = y1 + image.h; - - vec2<float> tl{x1, y1}; - vec2<float> tr{x2, y1}; - vec2<float> br{x2, y2}; - vec2<float> bl{x1, y2}; - - float angle = layout.icon.rotate * M_PI / 180.0f; - if (anchor.segment >= 0 && layout.icon.rotation_alignment != RotationAlignmentType::Viewport) { - const Coordinate &prev = line[anchor.segment]; - angle += std::atan2(anchor.y - prev.y, anchor.x - prev.x); - } - - if (angle) { - // Compute the transformation matrix. - float angle_sin = std::sin(angle); - float angle_cos = std::cos(angle); - std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}}; - - tl = tl.matMul(matrix); - tr = tr.matMul(matrix); - bl = bl.matMul(matrix); - br = br.matMul(matrix); - - x1 = util::min(tl.x, tr.x, bl.x, br.x); - x2 = util::max(tl.x, tr.x, bl.x, br.x); - y1 = util::min(tl.y, tr.y, bl.y, br.y); - y2 = util::max(tl.y, tr.y, bl.y, br.y); - } - - const CollisionRect box{/* x1 */ x1 * boxScale, - /* y1 */ y1 * boxScale, - /* x2 */ x2 * boxScale, - /* y2 */ y2 * boxScale}; - - Placement placement; - - placement.boxes.emplace_back( - /* box */ box, - /* anchor */ anchor, - /* minScale */ Placement::globalMinScale, - /* maxScale */ std::numeric_limits<float>::infinity(), - /* padding */ layout.icon.padding); - - placement.shapes.emplace_back( - /* tl */ tl, - /* tr */ tr, - /* bl */ bl, - /* br */ br, - /* image */ image, - /* angle */ 0, - /* anchors */ anchor, - /* minScale */ Placement::globalMinScale, - /* maxScale */ std::numeric_limits<float>::infinity()); - - placement.minScale = anchor.scale; - - return placement; -} - -Placement Placement::getGlyphs(Anchor &anchor, const vec2<float> &origin, const Shaping &shaping, - const GlyphPositions &face, float boxScale, bool horizontal, - const std::vector<Coordinate> &line, - const StyleLayoutSymbol &layout) { - const float maxAngle = layout.text.max_angle * M_PI / 180; - const float rotate = layout.text.rotate * M_PI / 180; - const float padding = layout.text.padding; - const bool alongLine = layout.text.rotation_alignment != RotationAlignmentType::Viewport; - const bool keepUpright = layout.text.keep_upright; - - Placement placement; - - const uint32_t glyphPadding = 1; - const uint32_t buffer = 3 + glyphPadding; - - for (const auto& 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.hasArea()) - 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 auto& 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 auto& box : placement.boxes) { - placement.minScale = util::min(placement.minScale, box.minScale); - } - placement.minScale = util::max(minPlacementScale, Placement::globalMinScale); - - return placement; -} -} diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp deleted file mode 100644 index 40762b8d70..0000000000 --- a/src/mbgl/text/placement.hpp +++ /dev/null @@ -1,31 +0,0 @@ -#ifndef MBGL_TEXT_PLACEMENT -#define MBGL_TEXT_PLACEMENT - -#include <mbgl/text/types.hpp> -#include <mbgl/text/glyph.hpp> - -#include <mbgl/util/vec.hpp> - -namespace mbgl { - -struct Anchor; -class StyleLayoutSymbol; - -class Placement { -public: - static Placement getIcon(Anchor &anchor, const Rect<uint16_t> &image, float iconBoxScale, - const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout); - - static Placement getGlyphs(Anchor &anchor, const vec2<float> &origin, const Shaping &shaping, - const GlyphPositions &face, float boxScale, bool horizontal, - const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout); - - static const float globalMinScale; - - GlyphBoxes boxes; - PlacedGlyphs shapes; - float minScale; -}; -} - -#endif diff --git a/src/mbgl/text/quads.cpp b/src/mbgl/text/quads.cpp new file mode 100644 index 0000000000..9434396156 --- /dev/null +++ b/src/mbgl/text/quads.cpp @@ -0,0 +1,205 @@ +#include <mbgl/text/quads.hpp> +#include <mbgl/text/shaping.hpp> +#include <mbgl/geometry/anchor.hpp> +#include <mbgl/style/style_layout.hpp> +#include <mbgl/util/math.hpp> +#include <cassert> + +namespace mbgl { + +const float globalMinScale = 0.5f; // underscale by 1 zoom level + +SymbolQuads getIconQuads(Anchor &anchor, const PositionedIcon &shapedIcon, + const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout, + const bool alongLine) { + + const float border = 1.0; + auto left = shapedIcon.left - border; + auto right = left + shapedIcon.image.w; + auto top = shapedIcon.top - border; + auto bottom = top + shapedIcon.image.h; + vec2<float> tl{left, top}; + vec2<float> tr{right, top}; + vec2<float> br{right, bottom}; + vec2<float> bl{left, bottom}; + + + float angle = layout.icon.rotate * M_PI / 180.0f; + if (alongLine) { + assert(static_cast<unsigned int>(anchor.segment) < line.size()); + const Coordinate &prev= line[anchor.segment]; + angle += std::atan2(anchor.y - prev.y, anchor.x - prev.x); + } + + + 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); + } + + SymbolQuads quads; + quads.emplace_back(tl, tr, bl, br, shapedIcon.image, 0, anchor, globalMinScale, std::numeric_limits<float>::infinity()); + return quads; +} + +struct GlyphInstance { + explicit GlyphInstance(const vec2<float> &anchor_) : anchor(anchor_) {} + explicit GlyphInstance(const vec2<float> &anchor_, float offset_, float minScale_, float maxScale_, + float angle_) + : anchor(anchor_), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {} + + const vec2<float> anchor; + const float offset = 0.0f; + const float minScale = globalMinScale; + const float maxScale = std::numeric_limits<float>::infinity(); + const float angle = 0.0f; +}; + +typedef std::vector<GlyphInstance> GlyphInstances; + +void getSegmentGlyphs(std::back_insert_iterator<GlyphInstances> glyphs, Anchor &anchor, + float offset, const std::vector<Coordinate> &line, int segment, int8_t direction) { + + const bool upsideDown = direction < 0; + + if (offset < 0) + direction *= -1; + + if (direction > 0) + segment++; + + assert((int)line.size() > segment); + vec2<float> end = line[segment]; + vec2<float> newAnchor = anchor; + float prevscale = std::numeric_limits<float>::infinity(); + + offset = std::fabs(offset); + + const float placementScale = anchor.scale; + + while (true) { + const float dist = util::dist<float>(newAnchor, end); + const float scale = offset / dist; + float angle = std::atan2(end.y - newAnchor.y, end.x - newAnchor.x); + if (direction < 0) + angle += M_PI; + if (upsideDown) + angle += M_PI; + + glyphs = GlyphInstance{ + /* anchor */ newAnchor, + /* offset */ static_cast<float>(upsideDown ? M_PI : 0.0), + /* minScale */ scale, + /* maxScale */ prevscale, + /* angle */ static_cast<float>(std::fmod((angle + 2.0 * M_PI), (2.0 * M_PI)))}; + + if (scale <= placementScale) + break; + + newAnchor = end; + + // skip duplicate nodes + while (newAnchor == end) { + segment += direction; + if ((int)line.size() <= segment || segment < 0) { + anchor.scale = scale; + return; + } + end = line[segment]; + } + + vec2<float> normal = util::normal<float>(newAnchor, end) * dist; + newAnchor = newAnchor - normal; + + prevscale = scale; + } +} + +SymbolQuads getGlyphQuads(Anchor &anchor, const Shaping &shapedText, + const float boxScale, const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout, + const bool alongLine, const GlyphPositions &face) { + + const float textRotate = layout.text.rotate * M_PI / 180; + const bool keepUpright = layout.text.keep_upright; + + SymbolQuads quads; + + for (const PositionedGlyph &positionedGlyph: shapedText.positionedGlyphs) { + auto face_it = face.find(positionedGlyph.glyph); + if (face_it == face.end()) + continue; + const Glyph &glyph = face_it->second; + const Rect<uint16_t> &rect = glyph.rect; + + if (!glyph) + continue; + + if (!rect.hasArea()) + continue; + + const float centerX = (positionedGlyph.x + glyph.metrics.advance / 2.0f) * boxScale; + + GlyphInstances glyphInstances; + if (alongLine) { + getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, 1); + if (keepUpright) + getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, -1); + + } else { + glyphInstances.emplace_back(GlyphInstance{anchor}); + } + + // The rects have an addditional buffer that is not included in their size; + const float glyphPadding = 1.0f; + const float rectBuffer = 3.0f + glyphPadding; + + const float x1 = positionedGlyph.x + glyph.metrics.left - rectBuffer; + const float y1 = positionedGlyph.y - glyph.metrics.top - rectBuffer; + const float x2 = x1 + rect.w; + const float y2 = y1 + rect.h; + + const vec2<float> otl{x1, y1}; + const vec2<float> otr{x2, y1}; + const vec2<float> obl{x1, y2}; + const vec2<float> obr{x2, y2}; + + for (const GlyphInstance &instance : glyphInstances) { + + vec2<float> tl = otl; + vec2<float> tr = otr; + vec2<float> bl = obl; + vec2<float> br = obr; + const float angle = instance.angle + textRotate; + + if (angle) { + // Compute the transformation matrix. + float angle_sin = std::sin(angle); + float angle_cos = std::cos(angle); + std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}}; + + tl = tl.matMul(matrix); + tr = tr.matMul(matrix); + bl = bl.matMul(matrix); + br = br.matMul(matrix); + } + + // Prevent label from extending past the end of the line + const float glyphMinScale = std::max(instance.minScale, anchor.scale); + + const float glyphAngle = std::fmod((anchor.angle + textRotate + instance.offset + 2 * M_PI), (2 * M_PI)); + quads.emplace_back(tl, tr, bl, br, rect, glyphAngle, instance.anchor, glyphMinScale, instance.maxScale); + + } + + } + + return quads; +} +} diff --git a/src/mbgl/text/quads.hpp b/src/mbgl/text/quads.hpp new file mode 100644 index 0000000000..b47cc718b6 --- /dev/null +++ b/src/mbgl/text/quads.hpp @@ -0,0 +1,48 @@ +#ifndef MBGL_TEXT_QUADS +#define MBGL_TEXT_QUADS + +#include <mbgl/text/glyph.hpp> +#include <mbgl/util/vec.hpp> + +#include <vector> + +namespace mbgl { + + struct SymbolQuad { + explicit SymbolQuad(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<SymbolQuad> SymbolQuads; + + struct Anchor; + class StyleLayoutSymbol; + class PositionedIcon; + + SymbolQuads getIconQuads(Anchor &anchor, const PositionedIcon &shapedIcon, + const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout, + const bool alongLine); + + SymbolQuads getGlyphQuads(Anchor &anchor, const Shaping &shapedText, + const float boxScale, const std::vector<Coordinate> &line, const StyleLayoutSymbol &layout, + const bool alongLine, const GlyphPositions &face); +} + +#endif diff --git a/src/mbgl/text/rotation_range.cpp b/src/mbgl/text/rotation_range.cpp deleted file mode 100644 index efaa1c67ed..0000000000 --- a/src/mbgl/text/rotation_range.cpp +++ /dev/null @@ -1,263 +0,0 @@ -#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 (const auto& 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 deleted file mode 100644 index 4968fda164..0000000000 --- a/src/mbgl/text/rotation_range.hpp +++ /dev/null @@ -1,54 +0,0 @@ -#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/shaping.cpp b/src/mbgl/text/shaping.cpp new file mode 100644 index 0000000000..35fe5dc24b --- /dev/null +++ b/src/mbgl/text/shaping.cpp @@ -0,0 +1,17 @@ +#include <mbgl/text/shaping.hpp> +#include <mbgl/style/style_layout.hpp> + +namespace mbgl { + +PositionedIcon shapeIcon(const Rect<uint16_t> &image, const StyleLayoutSymbol &layout) { + float dx = layout.icon.offset[0]; + float dy = layout.icon.offset[1]; + float x1 = dx - image.originalW / 2.0f; + float x2 = x1 + image.originalW; + float y1 = dy - image.originalH / 2.0f; + float y2 = y1 + image.originalH; + + return PositionedIcon(image, y1, y2, x1, x2); +} + +} diff --git a/src/mbgl/text/shaping.hpp b/src/mbgl/text/shaping.hpp new file mode 100644 index 0000000000..c409e6ed0a --- /dev/null +++ b/src/mbgl/text/shaping.hpp @@ -0,0 +1,31 @@ +#ifndef MBGL_TEXT_SHAPING +#define MBGL_TEXT_SHAPING + +#include <mbgl/text/glyph.hpp> + +#include <mbgl/util/vec.hpp> + +namespace mbgl { + + class PositionedIcon { + public: + inline explicit PositionedIcon() {} + inline explicit PositionedIcon(Rect<uint16_t> _image, + float _top, float _bottom, float _left, float _right) : + image(_image), top(_top), bottom(_bottom), left(_left), right(_right) {} + Rect<uint16_t> image; + float top = 0; + float bottom = 0; + float left = 0; + float right = 0; + + operator bool() const { return image.hasArea(); } + }; + + class StyleLayoutSymbol; + + PositionedIcon shapeIcon(const Rect<uint16_t> &image, const StyleLayoutSymbol &layout); + +} + +#endif diff --git a/src/mbgl/text/types.hpp b/src/mbgl/text/types.hpp deleted file mode 100644 index 23f49aa748..0000000000 --- a/src/mbgl/text/types.hpp +++ /dev/null @@ -1,113 +0,0 @@ -#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 diff --git a/src/mbgl/util/clip_lines.cpp b/src/mbgl/util/clip_lines.cpp new file mode 100644 index 0000000000..407db01fec --- /dev/null +++ b/src/mbgl/util/clip_lines.cpp @@ -0,0 +1,66 @@ +#include "clip_lines.hpp" + +namespace mbgl { +namespace util { + +std::vector<std::vector<Coordinate>> clipLines(const std::vector<std::vector<Coordinate>> &lines, + const int16_t x1, const int16_t y1, const int16_t x2, const int16_t y2) { + + std::vector<std::vector<Coordinate>> clippedLines; + + for (auto& line : lines) { + + if (!line.size()) + continue; + + auto end = line.end() - 1; + for (auto it = line.begin(); it != end; it++) { + Coordinate p0 = *(it); + Coordinate p1 = *(it + 1); + + if (p0.x < x1 && p1.x < x1) { + continue; + } else if (p0.x < x1) { + p0 = { x1, static_cast<int16_t>(p0.y + (p1.y - p0.y) * ((float)(x1 - p0.x) / (p1.x - p0.x))) }; + } else if (p1.x < x1) { + p1 = { x1, static_cast<int16_t>(p0.y + (p1.y - p0.y) * ((float)(x1 - p0.x) / (p1.x - p0.x))) }; + } + + if (p0.y < y1 && p1.y < y1) { + continue; + } else if (p0.y < y1) { + p0 = { static_cast<int16_t>(p0.x + (p1.x - p0.x) * ((float)(y1 - p0.y) / (p1.y - p0.y))), y1 }; + } else if (p1.y < y1) { + p1 = { static_cast<int16_t>(p0.x + (p1.x - p0.x) * ((float)(y1 - p0.y) / (p1.y - p0.y))), y1 }; + } + + if (p0.x >= x2 && p1.x >= x2) { + continue; + } else if (p0.x >= x2) { + p0 = { x2, static_cast<int16_t>(p0.y + (p1.y - p0.y) * ((float)(x2 - p0.x) / (p1.x - p0.x))) }; + } else if (p1.x >= x2) { + p1 = { x2, static_cast<int16_t>(p0.y + (p1.y - p0.y) * ((float)(x2 - p0.x) / (p1.x - p0.x))) }; + } + + if (p0.y >= y2 && p1.y >= y2) { + continue; + } else if (p0.y >= y2) { + p0 = { static_cast<int16_t>(p0.x + (p1.x - p0.x) * ((float)(y2 - p0.y) / (p1.y - p0.y))), y2 }; + } else if (p1.y >= y2) { + p1 = { static_cast<int16_t>(p0.x + (p1.x - p0.x) * ((float)(y2 - p0.y) / (p1.y - p0.y))), y2 }; + } + + if (!clippedLines.size() || (clippedLines.back().size() && !(p0 == clippedLines.back().back()))) { + clippedLines.emplace_back(); + clippedLines.back().push_back(p0); + } + + clippedLines.back().push_back(p1); + } + } + + return clippedLines; +} + +} // end namespace util +} // end namespace mbgl diff --git a/src/mbgl/util/clip_lines.hpp b/src/mbgl/util/clip_lines.hpp new file mode 100644 index 0000000000..6e49b48085 --- /dev/null +++ b/src/mbgl/util/clip_lines.hpp @@ -0,0 +1,19 @@ +#ifndef MBGL_UTIL_CLIP_LINES +#define MBGL_UTIL_CLIP_LINES + +#include <map> +#include <string> +#include <vector> +#include <mbgl/renderer/symbol_bucket.hpp> + +namespace mbgl { +namespace util { + + +std::vector<std::vector<Coordinate>> clipLines(const std::vector<std::vector<Coordinate>> &lines, + const int16_t x1, const int16_t y1, const int16_t x2, const int16_t y2); + +} // end namespace util +} // end namespace mbgl + +#endif diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp index 5185e78d92..f410b8e813 100644 --- a/src/mbgl/util/tile_cover.cpp +++ b/src/mbgl/util/tile_cover.cpp @@ -65,7 +65,7 @@ static void scanTriangle(const mbgl::vec2<double> a, const mbgl::vec2<double> b, if (bc.dy) scanSpans(ca, bc, ymin, ymax, scanLine); } -std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds) { +std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds, int8_t actualZ) { int32_t tiles = 1 << z; std::forward_list<mbgl::TileID> t; @@ -73,7 +73,7 @@ std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds) { int32_t x; if (y >= 0 && y <= tiles) { for (x = x0; x < x1; x++) { - t.emplace_front(z, x, y); + t.emplace_front(actualZ, x, y, z); } } }; diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp index 78121a30ba..99c19a3052 100644 --- a/src/mbgl/util/tile_cover.hpp +++ b/src/mbgl/util/tile_cover.hpp @@ -8,7 +8,7 @@ namespace mbgl { -std::forward_list<TileID> tileCover(int8_t z, const box& bounds); +std::forward_list<TileID> tileCover(int8_t z, const box& bounds, int8_t actualZ); } |