summaryrefslogtreecommitdiff
path: root/src/mbgl/text/glyph_set.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mbgl/text/glyph_set.cpp')
-rw-r--r--src/mbgl/text/glyph_set.cpp142
1 files changed, 102 insertions, 40 deletions
diff --git a/src/mbgl/text/glyph_set.cpp b/src/mbgl/text/glyph_set.cpp
index 537d9c0579..0040926103 100644
--- a/src/mbgl/text/glyph_set.cpp
+++ b/src/mbgl/text/glyph_set.cpp
@@ -64,7 +64,7 @@ void align(Shaping& shaping,
const float verticalAlign,
const float maxLineLength,
const float lineHeight,
- const uint32_t lineCount,
+ const std::size_t lineCount,
const Point<float>& translate) {
const float shiftX =
(justify - horizontalAlign) * maxLineLength + ::round(translate.x * 24 /* one em */);
@@ -80,8 +80,8 @@ void align(Shaping& shaping,
// justify left = 0, right = 1, center = .5
void justifyLine(std::vector<PositionedGlyph>& positionedGlyphs,
const std::map<uint32_t, SDFGlyph>& sdfs,
- uint32_t start,
- uint32_t end,
+ std::size_t start,
+ std::size_t end,
float justify) {
if (!justify) {
return;
@@ -93,34 +93,104 @@ void justifyLine(std::vector<PositionedGlyph>& positionedGlyphs,
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;
}
}
}
-float GlyphSet::determineIdeographicLineWidth(const std::u16string& logicalInput,
+float GlyphSet::determineAverageLineWidth(const std::u16string& logicalInput,
const float spacing,
float maxWidth) const {
float totalWidth = 0;
- // totalWidth doesn't include the last character for magical tuning reasons. This makes the
- // algorithm a little more agressive about trying to fit the text into fewer lines, taking
- // advantage of the tolerance for going a little over maxWidth
- for (uint32_t i = 0; i < logicalInput.size() - 1; i++) {
- auto it = sdfs.find(logicalInput[i]);
+ for (char16_t chr : logicalInput) {
+ auto it = sdfs.find(chr);
if (it != sdfs.end()) {
totalWidth += it->second.metrics.advance + spacing;
}
}
- int32_t lineCount = std::fmax(1, std::ceil(totalWidth / maxWidth));
- return totalWidth / lineCount;
+ 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 && lineWidth < targetWidth) {
+ // Be more tolerant of short final lines
+ return std::fmax(0, raggedness - 150);
+ }
+ if (penalty < 0) {
+ return raggedness - std::pow(penalty, 2);
+ }
+ return raggedness + std::pow(penalty, 2);
+}
+
+float calculatePenalty(char16_t codePoint, char16_t previousCodePoint) {
+ float penalty = 0;
+ // Force break on newline
+ if (codePoint == 0x0a) {
+ penalty -= 10000;
+ }
+ // Penalize open parenthesis at end of line
+ if (previousCodePoint && (previousCodePoint == 0x28 || previousCodePoint == 0xff08)) {
+ penalty += 50;
+ }
+ // Penalize close parenthesis at beginning of line
+ if (codePoint == 0x29 || codePoint == 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<int32_t> GlyphSet::determineLineBreaks(const std::u16string& logicalInput,
+std::set<std::size_t> GlyphSet::determineLineBreaks(const std::u16string& logicalInput,
const float spacing,
float maxWidth) const {
if (!maxWidth) {
@@ -130,42 +200,34 @@ std::set<int32_t> GlyphSet::determineLineBreaks(const std::u16string& logicalInp
if (logicalInput.empty()) {
return {};
}
-
- if (util::i18n::allowsIdeographicBreaking(logicalInput)) {
- maxWidth = determineIdeographicLineWidth(logicalInput, spacing, maxWidth);
- }
-
- std::set<int32_t> lineBreakPoints;
+
+ const float targetWidth = determineAverageLineWidth(logicalInput, spacing, maxWidth);
+
+ std::list<PotentialBreak> potentialBreaks;
float currentX = 0;
- uint32_t lastSafeBreak = 0;
- float lastSafeBreakX = 0;
- for (uint32_t i = 0; i < logicalInput.size(); i++) {
- auto it = sdfs.find(logicalInput[i]);
+ 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()) {
continue;
}
- const SDFGlyph& glyph = it->second;
-
// Ideographic characters, spaces, and word-breaking punctuation that often appear without
// surrounding spaces.
- if (util::i18n::allowsWordBreaking(glyph.id) ||
- util::i18n::allowsIdeographicBreaking(glyph.id)) {
- lastSafeBreak = i;
- lastSafeBreakX = currentX;
- }
+ if (util::i18n::allowsWordBreaking(codePoint) ||
+ util::i18n::allowsIdeographicBreaking(codePoint)) {
+ const char16_t previousCodePoint = i > 0 ? logicalInput[i-1] : 0;
- if (currentX > maxWidth && lastSafeBreak > 0) {
- lineBreakPoints.insert(lastSafeBreak);
- currentX -= lastSafeBreakX;
- lastSafeBreakX = 0;
+ potentialBreaks.push_back(evaluateBreak(i, currentX, targetWidth, potentialBreaks,
+ calculatePenalty(codePoint, previousCodePoint),
+ false));
}
- currentX += glyph.metrics.advance + spacing;
+ currentX += it->second.metrics.advance + spacing;
}
- return lineBreakPoints;
+ return leastBadBreaks(evaluateBreak(logicalInput.size(), currentX, targetWidth, potentialBreaks, 0, true));
}
void GlyphSet::shapeLines(Shaping& shaping,
@@ -194,7 +256,7 @@ void GlyphSet::shapeLines(Shaping& shaping,
continue;
}
- uint32_t lineStartIndex = static_cast<uint32_t>(shaping.positionedGlyphs.size());
+ std::size_t lineStartIndex = shaping.positionedGlyphs.size();
for (char16_t chr : line) {
auto it = sdfs.find(chr);
if (it == sdfs.end()) {
@@ -207,12 +269,12 @@ void GlyphSet::shapeLines(Shaping& shaping,
}
// Only justify if we placed at least one glyph
- if (static_cast<uint32_t>(shaping.positionedGlyphs.size()) != lineStartIndex) {
+ if (shaping.positionedGlyphs.size() != lineStartIndex) {
float lineLength = x - spacing; // Don't count trailing spacing
maxLineLength = util::max(lineLength, maxLineLength);
justifyLine(shaping.positionedGlyphs, sdfs, lineStartIndex,
- static_cast<uint32_t>(shaping.positionedGlyphs.size()) - 1, justify);
+ shaping.positionedGlyphs.size() - 1, justify);
}
x = 0;
@@ -220,7 +282,7 @@ void GlyphSet::shapeLines(Shaping& shaping,
}
align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight,
- static_cast<uint32_t>(lines.size()), translate);
+ lines.size(), translate);
const uint32_t height = lines.size() * lineHeight;
// Calculate the bounding box
View Lorry Controller Status