diff options
Diffstat (limited to 'src/mbgl/text/glyph_set.cpp')
| -rw-r--r-- | src/mbgl/text/glyph_set.cpp | 316 |
1 files changed, 226 insertions, 90 deletions
diff --git a/src/mbgl/text/glyph_set.cpp b/src/mbgl/text/glyph_set.cpp index 0875a83850..a4b197944e 100644 --- a/src/mbgl/text/glyph_set.cpp +++ b/src/mbgl/text/glyph_set.cpp @@ -1,7 +1,10 @@ +#include <mbgl/math/minmax.hpp> #include <mbgl/text/glyph_set.hpp> #include <mbgl/platform/log.hpp> -#include <mbgl/math/minmax.hpp> +#include <boost/algorithm/string.hpp> + +#include <algorithm> #include <cassert> namespace mbgl { @@ -26,44 +29,46 @@ void GlyphSet::insert(uint32_t id, SDFGlyph&& glyph) { } } -const std::map<uint32_t, SDFGlyph> &GlyphSet::getSDFs() const { +const std::map<uint32_t, SDFGlyph>& GlyphSet::getSDFs() const { return sdfs; } -const Shaping GlyphSet::getShaping(const std::u32string &string, const float maxWidth, - const float lineHeight, const float horizontalAlign, - const float verticalAlign, const float justify, - const float spacing, const Point<float> &translate) const { - Shaping shaping(translate.x * 24, translate.y * 24, string); - - // the y offset *should* be part of the font metadata - const int32_t yOffset = -17; - - float x = 0; - const float y = yOffset; +const Shaping GlyphSet::getShaping(const std::u16string& logicalInput, + const float maxWidth, + const float lineHeight, + const float horizontalAlign, + const float verticalAlign, + const float justify, + const float spacing, + const Point<float>& translate, + BiDi& bidi) const { - // Loop through all characters of this label and shape. - for (uint32_t chr : string) { - auto it = sdfs.find(chr); - if (it != sdfs.end()) { - shaping.positionedGlyphs.emplace_back(chr, x, y); - x += it->second.metrics.advance + spacing; - } - } + // The string stored in shaping.text is used for finding duplicates, but may end up quite + // different from the glyphs that get shown + Shaping shaping(translate.x * 24, translate.y * 24, logicalInput); - if (shaping.positionedGlyphs.empty()) - return shaping; + std::vector<std::u16string> reorderedLines = + bidi.processText(logicalInput, + determineLineBreaks(logicalInput, spacing, maxWidth)); - lineWrap(shaping, lineHeight, maxWidth, horizontalAlign, verticalAlign, justify, translate); + shapeLines(shaping, reorderedLines, spacing, lineHeight, horizontalAlign, verticalAlign, + justify, translate); return shaping; } -void align(Shaping &shaping, const float justify, const float horizontalAlign, - const float verticalAlign, const uint32_t maxLineLength, const float lineHeight, - const uint32_t line, const Point<float> &translate) { - const float shiftX = (justify - horizontalAlign) * maxLineLength + ::round(translate.x * 24/* one em */); - const float shiftY = (-verticalAlign * (line + 1) + 0.5) * lineHeight + ::round(translate.y * 24/* one em */); +void align(Shaping& shaping, + const float justify, + const float horizontalAlign, + const float verticalAlign, + const float maxLineLength, + const float lineHeight, + const std::size_t lineCount, + const Point<float>& translate) { + const float shiftX = + (justify - horizontalAlign) * maxLineLength + ::round(translate.x * 24 /* one em */); + const float shiftY = + (-verticalAlign * lineCount + 0.5) * lineHeight + ::round(translate.y * 24 /* one em */); for (auto& glyph : shaping.positionedGlyphs) { glyph.x += shiftX; @@ -71,94 +76,225 @@ void align(Shaping &shaping, const float justify, const float horizontalAlign, } } -void justifyLine(std::vector<PositionedGlyph> &positionedGlyphs, const std::map<uint32_t, SDFGlyph> &sdfs, uint32_t start, - uint32_t end, float justify) { - PositionedGlyph &glyph = positionedGlyphs[end]; +// justify left = 0, right = 1, center = .5 +void justifyLine(std::vector<PositionedGlyph>& positionedGlyphs, + const std::map<uint32_t, SDFGlyph>& sdfs, + std::size_t start, + std::size_t end, + float justify) { + if (!justify) { + return; + } + + PositionedGlyph& glyph = positionedGlyphs[end]; auto it = sdfs.find(glyph.glyph); if (it != sdfs.end()) { const uint32_t lastAdvance = it->second.metrics.advance; const float lineIndent = float(glyph.x + lastAdvance) * justify; - for (uint32_t j = start; j <= end; j++) { + for (std::size_t j = start; j <= end; j++) { positionedGlyphs[j].x -= lineIndent; } } } -void GlyphSet::lineWrap(Shaping &shaping, const float lineHeight, const float maxWidth, - const float horizontalAlign, const float verticalAlign, - const float justify, const Point<float> &translate) const { - uint32_t lastSafeBreak = 0; +float GlyphSet::determineAverageLineWidth(const std::u16string& logicalInput, + const float spacing, + float maxWidth) const { + float totalWidth = 0; - uint32_t lengthBeforeCurrentLine = 0; - uint32_t lineStartIndex = 0; - uint32_t line = 0; + for (char16_t chr : logicalInput) { + auto it = sdfs.find(chr); + if (it != sdfs.end()) { + totalWidth += it->second.metrics.advance + spacing; + } + } - uint32_t maxLineLength = 0; + int32_t targetLineCount = std::fmax(1, std::ceil(totalWidth / maxWidth)); + return totalWidth / targetLineCount; +} + +float calculateBadness(const float lineWidth, const float targetWidth, const float penalty, const bool isLastBreak) { + const float raggedness = std::pow(lineWidth - targetWidth, 2); + if (isLastBreak) { + // Favor finals lines shorter than average over longer than average + if (lineWidth < targetWidth) { + return raggedness / 2; + } else { + return raggedness * 2; + } + } + if (penalty < 0) { + return raggedness - std::pow(penalty, 2); + } + return raggedness + std::pow(penalty, 2); +} + +float calculatePenalty(char16_t codePoint, char16_t nextCodePoint) { + float penalty = 0; + // Force break on newline + if (codePoint == 0x0a) { + penalty -= 10000; + } + // Penalize open parenthesis at end of line + if (codePoint == 0x28 || codePoint == 0xff08) { + penalty += 50; + } - std::vector<PositionedGlyph> &positionedGlyphs = shaping.positionedGlyphs; + // Penalize close parenthesis at beginning of line + if (nextCodePoint == 0x29 || nextCodePoint == 0xff09) { + penalty += 50; + } + + return penalty; +} + +struct PotentialBreak { + PotentialBreak(const std::size_t p_index, const float p_x, const PotentialBreak* p_priorBreak, const float p_badness) + : index(p_index), x(p_x), priorBreak(p_priorBreak), badness(p_badness) + {} + + const std::size_t index; + const float x; + const PotentialBreak* priorBreak; + const float badness; +}; + + +PotentialBreak evaluateBreak(const std::size_t breakIndex, const float breakX, const float targetWidth, const std::list<PotentialBreak>& potentialBreaks, const float penalty, const bool isLastBreak) { + // We could skip evaluating breaks where the line length (breakX - priorBreak.x) > maxWidth + // ...but in fact we allow lines longer than maxWidth (if there's no break points) + // ...and when targetWidth and maxWidth are close, strictly enforcing maxWidth can give + // more lopsided results. + + const PotentialBreak* bestPriorBreak = nullptr; + float bestBreakBadness = calculateBadness(breakX, targetWidth, penalty, isLastBreak); + for (const auto& potentialBreak : potentialBreaks) { + const float lineWidth = breakX - potentialBreak.x; + float breakBadness = + calculateBadness(lineWidth, targetWidth, penalty, isLastBreak) + potentialBreak.badness; + if (breakBadness <= bestBreakBadness) { + bestPriorBreak = &potentialBreak; + bestBreakBadness = breakBadness; + } + } + + return PotentialBreak(breakIndex, breakX, bestPriorBreak, bestBreakBadness); +} + +std::set<std::size_t> leastBadBreaks(const PotentialBreak& lastLineBreak) { + std::set<std::size_t> leastBadBreaks = { lastLineBreak.index }; + const PotentialBreak* priorBreak = lastLineBreak.priorBreak; + while (priorBreak) { + leastBadBreaks.insert(priorBreak->index); + priorBreak = priorBreak->priorBreak; + } + return leastBadBreaks; +} + + +// We determine line breaks based on shaped text in logical order. Working in visual order would be +// more intuitive, but we can't do that because the visual order may be changed by line breaks! +std::set<std::size_t> GlyphSet::determineLineBreaks(const std::u16string& logicalInput, + const float spacing, + float maxWidth) const { + if (!maxWidth) { + return {}; + } + + if (logicalInput.empty()) { + return {}; + } + + const float targetWidth = determineAverageLineWidth(logicalInput, spacing, maxWidth); + + std::list<PotentialBreak> potentialBreaks; + float currentX = 0; + + for (std::size_t i = 0; i < logicalInput.size(); i++) { + const char16_t codePoint = logicalInput[i]; + auto it = sdfs.find(codePoint); + if (it != sdfs.end() && !boost::algorithm::is_any_of(u" \t\n\v\f\r")(codePoint)) { + currentX += it->second.metrics.advance + spacing; + } + + if (i >= logicalInput.size() - 1) + continue; + + // Spaces, plus word-breaking punctuation that often appears without surrounding spaces. + if (codePoint == 0x20 /* space */ + || codePoint == 0x26 /* ampersand */ + || codePoint == 0x2b /* plus sign */ + || codePoint == 0x2d /* hyphen-minus */ + || codePoint == 0x2f /* solidus */ + || codePoint == 0xad /* soft hyphen */ + || codePoint == 0xb7 /* middle dot */ + || codePoint == 0x200b /* zero-width space */ + || codePoint == 0x2010 /* hyphen */ + || codePoint == 0x2013 /* en dash */) { + potentialBreaks.push_back(evaluateBreak(i+1, currentX, targetWidth, potentialBreaks, + calculatePenalty(codePoint, logicalInput[i+1]), + false)); + } + } - if (maxWidth) { - for (uint32_t i = 0; i < positionedGlyphs.size(); i++) { - PositionedGlyph &shape = positionedGlyphs[i]; + return leastBadBreaks(evaluateBreak(logicalInput.size(), currentX, targetWidth, potentialBreaks, 0, true)); +} - shape.x -= lengthBeforeCurrentLine; - shape.y += lineHeight * line; +void GlyphSet::shapeLines(Shaping& shaping, + const std::vector<std::u16string>& lines, + const float spacing, + const float lineHeight, + const float horizontalAlign, + const float verticalAlign, + const float justify, + const Point<float>& translate) const { - if (shape.x > maxWidth && lastSafeBreak > 0) { + // the y offset *should* be part of the font metadata + const int32_t yOffset = -17; - uint32_t lineLength = positionedGlyphs[lastSafeBreak + 1].x; - maxLineLength = util::max(lineLength, maxLineLength); + float x = 0; + float y = yOffset; - for (uint32_t k = lastSafeBreak + 1; k <= i; k++) { - positionedGlyphs[k].y += lineHeight; - positionedGlyphs[k].x -= lineLength; - } + float maxLineLength = 0; - if (justify) { - // Collapse invisible characters. - uint32_t breakGlyph = positionedGlyphs[lastSafeBreak].glyph; - uint32_t lineEnd = lastSafeBreak; - if (breakGlyph == 0x20 /* space */ - || breakGlyph == 0x200b /* zero-width space */) { - lineEnd--; - } + for (std::u16string line : lines) { + // Collapse whitespace so it doesn't throw off justification + boost::algorithm::trim_if(line, boost::algorithm::is_any_of(u" \t\n\v\f\r")); - justifyLine(positionedGlyphs, sdfs, lineStartIndex, lineEnd, justify); - } + if (line.empty()) { + y += lineHeight; // Still need a line feed after empty line + continue; + } - lineStartIndex = lastSafeBreak + 1; - lastSafeBreak = 0; - lengthBeforeCurrentLine += lineLength; - line++; + std::size_t lineStartIndex = shaping.positionedGlyphs.size(); + for (char16_t chr : line) { + auto it = sdfs.find(chr); + if (it == sdfs.end()) { + continue; } - // Spaces, plus word-breaking punctuation that often appears without surrounding spaces. - if (shape.glyph == 0x20 /* space */ - || shape.glyph == 0x26 /* ampersand */ - || shape.glyph == 0x2b /* plus sign */ - || shape.glyph == 0x2d /* hyphen-minus */ - || shape.glyph == 0x2f /* solidus */ - || shape.glyph == 0xad /* soft hyphen */ - || shape.glyph == 0xb7 /* middle dot */ - || shape.glyph == 0x200b /* zero-width space */ - || shape.glyph == 0x2010 /* hyphen */ - || shape.glyph == 0x2013 /* en dash */) { - lastSafeBreak = i; - } + const SDFGlyph& glyph = it->second; + shaping.positionedGlyphs.emplace_back(chr, x, y); + x += glyph.metrics.advance + spacing; } - } - const PositionedGlyph& lastPositionedGlyph = positionedGlyphs.back(); - const auto lastGlyphIt = sdfs.find(lastPositionedGlyph.glyph); - assert(lastGlyphIt != sdfs.end()); - const uint32_t lastLineLength = lastPositionedGlyph.x + lastGlyphIt->second.metrics.advance; - maxLineLength = std::max(maxLineLength, lastLineLength); + // Only justify if we placed at least one glyph + if (shaping.positionedGlyphs.size() != lineStartIndex) { + float lineLength = x - spacing; // Don't count trailing spacing + maxLineLength = util::max(lineLength, maxLineLength); + + justifyLine(shaping.positionedGlyphs, sdfs, lineStartIndex, + shaping.positionedGlyphs.size() - 1, justify); + } - const uint32_t height = (line + 1) * lineHeight; + x = 0; + y += lineHeight; + } - justifyLine(positionedGlyphs, sdfs, lineStartIndex, uint32_t(positionedGlyphs.size()) - 1, justify); - align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight, line, translate); + align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight, + lines.size(), translate); + const uint32_t height = lines.size() * lineHeight; // Calculate the bounding box shaping.top += -verticalAlign * height; |