diff options
Diffstat (limited to 'src/mbgl/text/placement.cpp')
| -rw-r--r-- | src/mbgl/text/placement.cpp | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp new file mode 100644 index 0000000000..84d4e20b2f --- /dev/null +++ b/src/mbgl/text/placement.cpp @@ -0,0 +1,312 @@ +#include <mbgl/text/placement.hpp> +#include <mbgl/geometry/anchor.hpp> +#include <mbgl/text/glyph.hpp> +#include <mbgl/text/placement.hpp> +#include <mbgl/text/glyph_store.hpp> +#include <mbgl/style/style_bucket.hpp> + +#include <mbgl/util/math.hpp> + +namespace mbgl { + +const float Placement::globalMinScale = 0.5; // underscale by 1 zoom level + +struct GlyphInstance { + explicit GlyphInstance(const vec2<float> &anchor_) : anchor(anchor_) {} + explicit GlyphInstance(const vec2<float> &anchor_, float offset_, float minScale_, float maxScale_, + float angle_) + : anchor(anchor_), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {} + + const vec2<float> anchor; + const float offset = 0.0f; + const float minScale = Placement::globalMinScale; + const float maxScale = std::numeric_limits<float>::infinity(); + const float angle = 0.0f; +}; + +typedef std::vector<GlyphInstance> GlyphInstances; + +void getSegmentGlyphs(std::back_insert_iterator<GlyphInstances> glyphs, Anchor &anchor, + float offset, const std::vector<Coordinate> &line, int segment, + int8_t direction, float maxAngle) { + const bool upsideDown = direction < 0; + + if (offset < 0) + direction *= -1; + + if (direction > 0) + segment++; + + vec2<float> newAnchor = anchor; + + if ((int)line.size() <= segment) { + return; + } + vec2<float> end = line[segment]; + float prevscale = std::numeric_limits<float>::infinity(); + float prevAngle = 0.0f; + + offset = std::fabs(offset); + + const float placementScale = anchor.scale; + + while (true) { + const float dist = util::dist<float>(newAnchor, end); + const float scale = offset / dist; + float angle = + -std::atan2(end.x - newAnchor.x, end.y - newAnchor.y) + direction * M_PI / 2.0f; + if (upsideDown) + angle += M_PI; + + // Don't place around sharp corners + float angleDiff = std::fmod((angle - prevAngle), (2.0f * M_PI)); + if (prevAngle && std::fabs(angleDiff) > maxAngle) { + anchor.scale = prevscale; + break; + } + + glyphs = GlyphInstance{ + /* anchor */ newAnchor, + /* offset */ static_cast<float>(upsideDown ? M_PI : 0.0), + /* minScale */ scale, + /* maxScale */ prevscale, + /* angle */ static_cast<float>(std::fmod((angle + 2.0 * M_PI), (2.0 * M_PI)))}; + + if (scale <= placementScale) + break; + + newAnchor = end; + + // skip duplicate nodes + while (newAnchor == end) { + segment += direction; + if ((int)line.size() <= segment || segment < 0) { + anchor.scale = scale; + return; + } + end = line[segment]; + } + + vec2<float> normal = util::normal<float>(newAnchor, end) * dist; + newAnchor = newAnchor - normal; + + prevscale = scale; + prevAngle = angle; + } +} + +GlyphBox getMergedBoxes(const GlyphBoxes &glyphs, const Anchor &anchor) { + // Collision checks between rotating and fixed labels are relatively expensive, + // so we use one box per label, not per glyph for horizontal labels. + + const float inf = std::numeric_limits<float>::infinity(); + + GlyphBox mergedglyphs{/* box */ CollisionRect{inf, inf, -inf, -inf}, + /* anchor */ anchor, + /* minScale */ 0, + /* maxScale */ inf, + /* padding */ -inf}; + + CollisionRect &box = mergedglyphs.box; + + for (const GlyphBox &glyph : glyphs) { + const CollisionRect &gbox = glyph.box; + box.tl.x = util::min(box.tl.x, gbox.tl.x); + box.tl.y = util::min(box.tl.y, gbox.tl.y); + box.br.x = util::max(box.br.x, gbox.br.x); + box.br.y = util::max(box.br.y, gbox.br.y); + mergedglyphs.minScale = util::max(mergedglyphs.minScale, glyph.minScale); + mergedglyphs.padding = util::max(mergedglyphs.padding, glyph.padding); + } + // for all horizontal labels, calculate bbox covering all rotated positions + float x12 = box.tl.x * box.tl.x, y12 = box.tl.y * box.tl.y, x22 = box.br.x * box.br.x, + y22 = box.br.y * box.br.y, + diag = std::sqrt(util::max(x12 + y12, x12 + y22, x22 + y12, x22 + y22)); + + mergedglyphs.hBox = CollisionRect{-diag, -diag, diag, diag}; + + return mergedglyphs; +} + +Placement Placement::getIcon(Anchor &anchor, const Rect<uint16_t> &image, float boxScale, + const std::vector<Coordinate> &line, const StyleBucketSymbol &props) { + const float x = image.w / 2.0f; // No need to divide by image.pixelRatio here? + const float y = image.h / 2.0f; // image.pixelRatio; + + const float dx = props.icon.offset.x; + const float dy = props.icon.offset.y; + float x1 = (dx - x); + float x2 = (dx + x); + float y1 = (dy - y); + float y2 = (dy + y); + + vec2<float> tl{x1, y1}; + vec2<float> tr{x2, y1}; + vec2<float> br{x2, y2}; + vec2<float> bl{x1, y2}; + + float angle = props.icon.rotate * M_PI / 180.0f; + if (anchor.segment >= 0 && props.icon.rotation_alignment != RotationAlignmentType::Viewport) { + const Coordinate &next = line[anchor.segment]; + angle += -std::atan2(next.x - anchor.x, next.y - anchor.y) + M_PI / 2; + } + + if (angle) { + // Compute the transformation matrix. + float angle_sin = std::sin(angle); + float angle_cos = std::cos(angle); + std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}}; + + tl = tl.matMul(matrix); + tr = tr.matMul(matrix); + bl = bl.matMul(matrix); + br = br.matMul(matrix); + + x1 = util::min(tl.x, tr.x, bl.x, br.x); + x2 = util::max(tl.x, tr.x, bl.x, br.x); + y1 = util::min(tl.y, tr.y, bl.y, br.y); + y2 = util::max(tl.y, tr.y, bl.y, br.y); + } + + const CollisionRect box{/* x1 */ x1 * boxScale, + /* y1 */ y1 * boxScale, + /* x2 */ x2 * boxScale, + /* y2 */ y2 * boxScale}; + + Placement placement; + + placement.boxes.emplace_back( + /* box */ box, + /* anchor */ anchor, + /* minScale */ Placement::globalMinScale, + /* maxScale */ std::numeric_limits<float>::infinity(), + /* padding */ props.icon.padding); + + placement.shapes.emplace_back( + /* tl */ tl, + /* tr */ tr, + /* bl */ bl, + /* br */ br, + /* image */ image, + /* angle */ 0, + /* anchors */ anchor, + /* minScale */ Placement::globalMinScale, + /* maxScale */ std::numeric_limits<float>::infinity()); + + placement.minScale = anchor.scale; + + return placement; +} + +Placement Placement::getGlyphs(Anchor &anchor, const vec2<float> &origin, const Shaping &shaping, + const GlyphPositions &face, float boxScale, bool horizontal, + const std::vector<Coordinate> &line, + const StyleBucketSymbol &props) { + const float maxAngle = props.text.max_angle * M_PI / 180; + const float rotate = props.text.rotate * M_PI / 180; + const float padding = props.text.padding; + const bool alongLine = props.text.rotation_alignment != RotationAlignmentType::Viewport; + const bool keepUpright = props.text.keep_upright; + + Placement placement; + + const uint32_t buffer = 3; + + for (const PositionedGlyph &shape : shaping) { + auto face_it = face.find(shape.glyph); + if (face_it == face.end()) + continue; + const Glyph &glyph = face_it->second; + const Rect<uint16_t> &rect = glyph.rect; + + if (!glyph) + continue; + + if (!rect) + continue; + + const float x = (origin.x + shape.x + glyph.metrics.left - buffer + rect.w / 2) * boxScale; + + GlyphInstances glyphInstances; + if (anchor.segment >= 0 && alongLine) { + getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, x, line, anchor.segment, 1, + maxAngle); + if (keepUpright) + getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, x, line, + anchor.segment, -1, maxAngle); + + } else { + glyphInstances.emplace_back(GlyphInstance{anchor}); + } + + const float x1 = origin.x + shape.x + glyph.metrics.left - buffer; + const float y1 = origin.y + shape.y - glyph.metrics.top - buffer; + const float x2 = x1 + glyph.rect.w; + const float y2 = y1 + glyph.rect.h; + + const vec2<float> otl{x1, y1}; + const vec2<float> otr{x2, y1}; + const vec2<float> obl{x1, y2}; + const vec2<float> obr{x2, y2}; + + const CollisionRect obox{boxScale * x1, boxScale * y1, boxScale * x2, boxScale * y2}; + + for (const GlyphInstance &instance : glyphInstances) { + vec2<float> tl = otl; + vec2<float> tr = otr; + vec2<float> bl = obl; + vec2<float> br = obr; + + CollisionRect box = obox; + + // Clamp to -90/+90 degrees + const float angle = instance.angle + rotate; + + if (angle) { + // Compute the transformation matrix. + float angle_sin = std::sin(angle); + float angle_cos = std::cos(angle); + std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}}; + + tl = tl.matMul(matrix); + tr = tr.matMul(matrix); + bl = bl.matMul(matrix); + br = br.matMul(matrix); + } + + // Prevent label from extending past the end of the line + const float glyphMinScale = std::max(instance.minScale, anchor.scale); + + // Remember the glyph for later insertion. + placement.shapes.emplace_back( + tl, tr, bl, br, rect, + float(std::fmod((anchor.angle + rotate + instance.offset + 2 * M_PI), (2 * M_PI))), + instance.anchor, glyphMinScale, instance.maxScale); + + if (!instance.offset) { // not a flipped glyph + if (angle) { + // Calculate the rotated glyph's bounding box offsets from the anchor point. + box = CollisionRect{boxScale * util::min(tl.x, tr.x, bl.x, br.x), + boxScale * util::min(tl.y, tr.y, bl.y, br.y), + boxScale * util::max(tl.x, tr.x, bl.x, br.x), + boxScale * util::max(tl.y, tr.y, bl.y, br.y)}; + } + placement.boxes.emplace_back(box, instance.anchor, glyphMinScale, instance.maxScale, padding); + } + } + } + + // TODO avoid creating the boxes in the first place? + if (horizontal) + placement.boxes = {getMergedBoxes(placement.boxes, anchor)}; + + const float minPlacementScale = anchor.scale; + placement.minScale = std::numeric_limits<float>::infinity(); + for (const GlyphBox &box : placement.boxes) { + placement.minScale = util::min(placement.minScale, box.minScale); + } + placement.minScale = util::max(minPlacementScale, Placement::globalMinScale); + + return placement; +} +} |