summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRaph Levien <raph@google.com>2015-06-12 21:59:04 +0000
committerAndroid (Google) Code Review <android-gerrit@google.com>2015-06-12 21:59:05 +0000
commit17e78fa864df7b1f3ee737db6ad6c193dffc2396 (patch)
tree58d5e11e78eab28fb38c5667e55df71130030baf
parent4ea1cc82b0e8170d6ab6a7e9ee274c81315cd59e (diff)
parentabae97a39c26e191e350575932611a90e6b04d06 (diff)
downloadandroid_frameworks_minikin-17e78fa864df7b1f3ee737db6ad6c193dffc2396.tar.gz
android_frameworks_minikin-17e78fa864df7b1f3ee737db6ad6c193dffc2396.tar.bz2
android_frameworks_minikin-17e78fa864df7b1f3ee737db6ad6c193dffc2396.zip
Merge "Increase hyphenation penalty for short last line" into mnc-dev
-rw-r--r--include/minikin/LineBreaker.h9
-rw-r--r--libs/minikin/LineBreaker.cpp100
2 files changed, 39 insertions, 70 deletions
diff --git a/include/minikin/LineBreaker.h b/include/minikin/LineBreaker.h
index 36314fb..e031fb3 100644
--- a/include/minikin/LineBreaker.h
+++ b/include/minikin/LineBreaker.h
@@ -200,9 +200,6 @@ class LineBreaker {
float currentLineWidth() const;
- // compute shrink/stretch penalty for line
- float computeScore(float delta, bool atEnd);
-
void addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty,
uint8_t hyph);
@@ -213,10 +210,7 @@ class LineBreaker {
void computeBreaksGreedy();
- void computeBreaksOptimal();
-
- // special case when LineWidth is constant (layout is rectangle)
- void computeBreaksOptimalRect();
+ void computeBreaksOptimal(bool isRectangular);
void finishBreaksOptimal();
@@ -241,6 +235,7 @@ class LineBreaker {
ParaWidth mWidth = 0;
std::vector<Candidate> mCandidates;
+ float mLinePenalty = 0.0f;
// the following are state for greedy breaker (updated while adding style runs)
size_t mLastBreak;
diff --git a/libs/minikin/LineBreaker.cpp b/libs/minikin/LineBreaker.cpp
index dbd6ea8..8275a6c 100644
--- a/libs/minikin/LineBreaker.cpp
+++ b/libs/minikin/LineBreaker.cpp
@@ -37,6 +37,13 @@ const float SCORE_INFTY = std::numeric_limits<float>::max();
const float SCORE_OVERFULL = 1e12f;
const float SCORE_DESPERATE = 1e10f;
+// Multiplier for hyphen penalty on last line.
+const float LAST_LINE_PENALTY_MULTIPLIER = 4.0f;
+// Penalty assigned to each line break (to try to minimize number of lines)
+// TODO: when we implement full justification (so spaces can shrink and stretch), this is
+// probably not the most appropriate method.
+const float LINE_PENALTY_MULTIPLIER = 2.0f;
+
// Very long words trigger O(n^2) behavior in hyphenation, so we disable hyphenation for
// unreasonably long words. This is somewhat of a heuristic because extremely long words
// are possible in some languages. This does mean that very long real words can get
@@ -122,6 +129,8 @@ float LineBreaker::addStyleRun(MinikinPaint* paint, const FontCollection* typefa
if (mHyphenationFrequency == kHyphenationFrequency_Normal) {
hyphenPenalty *= 4.0; // TODO: Replace with a better value after some testing
}
+
+ mLinePenalty = std::max(mLinePenalty, hyphenPenalty * LINE_PENALTY_MULTIPLIER);
}
size_t current = (size_t)mBreakIterator->current();
@@ -235,17 +244,6 @@ void LineBreaker::addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth post
addCandidate(cand);
}
-// TODO: for justified text, refine with shrink/stretch
-float LineBreaker::computeScore(float delta, bool atEnd) {
- if (delta < 0) {
- return SCORE_OVERFULL;
- } else if (atEnd && mStrategy != kBreakStrategy_Balanced) {
- return 0.0;
- } else {
- return delta * delta;
- }
-}
-
// TODO performance: could avoid populating mCandidates if greedy only
void LineBreaker::addCandidate(Candidate cand) {
size_t candIndex = mCandidates.size();
@@ -320,75 +318,51 @@ void LineBreaker::finishBreaksOptimal() {
std::reverse(mFlags.begin(), mFlags.end());
}
-void LineBreaker::computeBreaksOptimal() {
+void LineBreaker::computeBreaksOptimal(bool isRectangle) {
size_t active = 0;
size_t nCand = mCandidates.size();
+ float width = mLineWidths.getLineWidth(0);
for (size_t i = 1; i < nCand; i++) {
bool atEnd = i == nCand - 1;
float best = SCORE_INFTY;
size_t bestPrev = 0;
+ size_t lineNumberLast = 0;
- size_t lineNumberLast = mCandidates[active].lineNumber;
- float width = mLineWidths.getLineWidth(lineNumberLast);
+ if (!isRectangle) {
+ size_t lineNumberLast = mCandidates[active].lineNumber;
+ width = mLineWidths.getLineWidth(lineNumberLast);
+ }
ParaWidth leftEdge = mCandidates[i].postBreak - width;
float bestHope = 0;
for (size_t j = active; j < i; j++) {
- size_t lineNumber = mCandidates[j].lineNumber;
- if (lineNumber != lineNumberLast) {
- float widthNew = mLineWidths.getLineWidth(lineNumber);
- if (widthNew != width) {
- leftEdge = mCandidates[i].postBreak - width;
- bestHope = 0;
- width = widthNew;
+ if (!isRectangle) {
+ size_t lineNumber = mCandidates[j].lineNumber;
+ if (lineNumber != lineNumberLast) {
+ float widthNew = mLineWidths.getLineWidth(lineNumber);
+ if (widthNew != width) {
+ leftEdge = mCandidates[i].postBreak - width;
+ bestHope = 0;
+ width = widthNew;
+ }
+ lineNumberLast = lineNumber;
}
- lineNumberLast = lineNumber;
}
float jScore = mCandidates[j].score;
if (jScore + bestHope >= best) continue;
float delta = mCandidates[j].preBreak - leftEdge;
- float widthScore = computeScore(delta, atEnd);
+ // compute width score for line
+ float widthScore = 0.0f;
if (delta < 0) {
- active = j + 1;
+ widthScore = SCORE_OVERFULL;
+ } else if (atEnd && mStrategy != kBreakStrategy_Balanced) {
+ // increase penalty for hyphen on last line
+ widthScore = LAST_LINE_PENALTY_MULTIPLIER * mCandidates[j].penalty;
} else {
- bestHope = widthScore;
- }
-
- float score = jScore + widthScore;
- if (score <= best) {
- best = score;
- bestPrev = j;
+ widthScore = delta * delta;
}
- }
- mCandidates[i].score = best + mCandidates[i].penalty;
- mCandidates[i].prev = bestPrev;
- mCandidates[i].lineNumber = mCandidates[bestPrev].lineNumber + 1;
- }
- finishBreaksOptimal();
-}
-
-void LineBreaker::computeBreaksOptimalRect() {
- size_t active = 0;
- size_t nCand = mCandidates.size();
- float width = mLineWidths.getLineWidth(0);
- for (size_t i = 1; i < nCand; i++) {
- bool atEnd = i == nCand - 1;
- float best = SCORE_INFTY;
- size_t bestPrev = 0;
-
- // Width-based component of score increases as line gets shorter, so score will always be
- // at least this.
- float bestHope = 0;
-
- ParaWidth leftEdge = mCandidates[i].postBreak - width;
- for (size_t j = active; j < i; j++) {
- // TODO performance: can break if bestHope >= best; worth it?
- float jScore = mCandidates[j].score;
- if (jScore + bestHope >= best) continue;
- float delta = mCandidates[j].preBreak - leftEdge;
- float widthScore = computeScore(delta, atEnd);
if (delta < 0) {
active = j + 1;
} else {
@@ -401,8 +375,9 @@ void LineBreaker::computeBreaksOptimalRect() {
bestPrev = j;
}
}
- mCandidates[i].score = best + mCandidates[i].penalty;
+ mCandidates[i].score = best + mCandidates[i].penalty + mLinePenalty;
mCandidates[i].prev = bestPrev;
+ mCandidates[i].lineNumber = mCandidates[bestPrev].lineNumber + 1;
}
finishBreaksOptimal();
}
@@ -410,10 +385,8 @@ void LineBreaker::computeBreaksOptimalRect() {
size_t LineBreaker::computeBreaks() {
if (mStrategy == kBreakStrategy_Greedy) {
computeBreaksGreedy();
- } else if (mLineWidths.isConstant()) {
- computeBreaksOptimalRect();
} else {
- computeBreaksOptimal();
+ computeBreaksOptimal(mLineWidths.isConstant());
}
return mBreaks.size();
}
@@ -438,6 +411,7 @@ void LineBreaker::finish() {
}
mStrategy = kBreakStrategy_Greedy;
mHyphenationFrequency = kHyphenationFrequency_Normal;
+ mLinePenalty = 0.0f;
}
} // namespace android