View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0007908 | Scribus | Story Editor / Text Frames | public | 2009-03-29 16:02 | 2009-04-19 21:01 |
Reporter | mecirt | Assigned To | jghali | ||
Priority | normal | Severity | minor | Reproducibility | have not tried |
Status | closed | Resolution | fixed | ||
Platform | x86-64 | OS | linux | OS Version | opensuse 11 |
Product Version | 1.3.5svn | ||||
Fixed in Version | 1.3.5svn | ||||
Summary | 0007908: Text relayouting is slow (partial patch attached) | ||||
Description | Relayouting the text is a rather slow operation, especially in large documents. There are several things that can be improved here, I am attaching a patch that fixes one of the issues. I have found out that the endOfLine function, which locates the end of line, was operating by getting some X coordinate, then increasing it by steps of 0.125, until it reaches a coordinate that no longer fits within the enclosing frame. I have improved this algorithm to use a variation of binary searching - first X gets increased in steps of 128, then by 64 within the last matching interval, and so on, until steps of 0.125 are reached. This gives the same result in all cases, but operates significantly faster. | ||||
Tags | No tags attached. | ||||
Patch | |||||
2009-03-29 16:02
|
scribus-layout-speedup.patch (1,931 bytes)
Index: scribus/pageitem_textframe.cpp =================================================================== --- scribus/pageitem_textframe.cpp (revision 13356) +++ scribus/pageitem_textframe.cpp (working copy) @@ -493,19 +493,32 @@ /// find x position where this line must end double endOfLine(const QRegion& shape, const QMatrix& pf2, double ascent, double descent, double morespace = 0) { - double EndX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); QPoint pt1, pt2; - // qDebug() << QString("endx start=%1, hl is '%2'").arg(EndX).arg(hl->ch); - do { - EndX += 0.125; - pt1 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(yPos+descent)); - pt2 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(ceil(yPos-ascent))); - } while - ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) - && shape.contains(pf2.map(pt1)) - && shape.contains(pf2.map(pt2)) - ); - + pt1.setY (static_cast<int>(yPos+descent)); + pt2.setY (static_cast<int>(ceil(yPos-ascent))); + double StartX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); + double EndX; + // this locates the highest X that falls within the box + // it does so by first finding an interval of size 128 + // then it keeps reducing the steps by half, until it gets down + // to 0.125 steps + double Interval = 128.0; + while (Interval > 0.125) { + EndX = StartX; + + do { + EndX += Interval; + int xPos = static_cast<int>(ceil(EndX + insets.Right)); + pt1.setX (xPos); + pt2.setX (xPos); + } while + ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) + && shape.contains(pf2.map(pt1)) + && shape.contains(pf2.map(pt2)) + ); + StartX = EndX - Interval; + Interval /= 2; + } return EndX; } |
2009-03-29 18:55
|
scribus-layout-speedup-fixed.patch (2,816 bytes)
Index: scribus/pageitem_textframe.cpp =================================================================== --- scribus/pageitem_textframe.cpp (revision 13359) +++ scribus/pageitem_textframe.cpp (working copy) @@ -493,19 +493,44 @@ /// find x position where this line must end double endOfLine(const QRegion& shape, const QMatrix& pf2, double ascent, double descent, double morespace = 0) { - double EndX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); - QPoint pt1, pt2; - // qDebug() << QString("endx start=%1, hl is '%2'").arg(EndX).arg(hl->ch); - do { - EndX += 0.125; - pt1 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(yPos+descent)); - pt2 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(ceil(yPos-ascent))); - } while - ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) - && shape.contains(pf2.map(pt1)) - && shape.contains(pf2.map(pt2)) - ); - + // if we aren't restricted further, we'll end at this maxX: + double maxX = colRight - morespace; + if (legacy) maxX -= lineCorr + insets.Right; + + double StartX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); + int xPos = static_cast<int>(ceil(maxX + insets.Right)); + int yDesc = static_cast<int>(yPos+descent); + int yAsc = static_cast<int>(ceil(yPos-ascent)); + + QPoint pt1 (xPos, yDesc); + QPoint pt2 (xPos, yAsc); + + // simple and fast case: transformed line completely falls within range + // this will happen if we don't wrap around anything - ie. very often + QPolygon p; + p.append (pf2.map (QPoint (StartX, yAsc))); + p.append (pf2.map (QPoint (StartX, yDesc))); + p.append (pf2.map (pt1)); + p.append (pf2.map (pt2)); + // check if something gets in the way + QRegion line = shape.intersected (p.boundingRect()); + // if the intersection only has 1 rectangle, then nothing gets in the way + if (line.numRects() == 1) return maxX; + + // qDebug()<<"endOfLine: going for the hard case"; + double EndX; + double Interval = 0.125; + EndX = StartX; + do { + EndX += Interval; + int xPos = static_cast<int>(ceil(EndX + insets.Right)); + pt1.setX (xPos); + pt2.setX (xPos); + } while + ((EndX < maxX) + && shape.contains(pf2.map(pt1)) + && shape.contains(pf2.map(pt2)) + ); return EndX; } |
|
my previous patch was wrong - uploaded a fixed version that behaves differently. instead of binary searching, it checks if our line can intersect with any object. if it finds out that it can't, it simply returns the right margin - otherwise it goes for the full check. |
|
just a minor fix: replace if (line.numRects() == 1) return maxX; by if (lineI.numRects() == 1) { int steps = static_cast<int>((maxX - startX - insets.right)/0.125); if (steps > 0) startX += steps * 0.125; } ... then continue into the loop, which should take only 1 or to steps now. |
|
mecirt.. we need to be 100% sure if and what cases this change might cause wrapping/layout differences. we would be looking to 0 changes for 1.3.5svn. |
2009-03-29 22:58
|
7908equalEndX.diff (2,378 bytes)
Index: pageitem_textframe.cpp =================================================================== --- pageitem_textframe.cpp (revision 13363) +++ pageitem_textframe.cpp (working copy) @@ -500,14 +500,57 @@ EndX += 0.125; pt1 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(yPos+descent)); pt2 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(ceil(yPos-ascent))); - } while - ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) - && shape.contains(pf2.map(pt1)) - && shape.contains(pf2.map(pt2)) - ); - - return EndX; + } while ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) + && shape.contains(pf2.map(pt1)) + && shape.contains(pf2.map(pt2)) + ); + //original endX calculated now + + + // if we aren't restricted further, we'll end at this maxX: + double maxX = colRight - morespace; + if (legacy) maxX -= lineCorr + insets.Right; + + double StartX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); + int xPos = static_cast<int>(ceil(maxX + insets.Right)); + int yDesc = static_cast<int>(yPos+descent); + int yAsc = static_cast<int>(ceil(yPos-ascent)); + + QPoint pt12 (xPos, yDesc); + QPoint pt22 (xPos, yAsc); + + // simple and fast case: transformed line completely falls within range + // this will happen if we don't wrap around anything - ie. very often + QPolygon p; + p.append (pf2.map (QPoint (StartX, yAsc))); + p.append (pf2.map (QPoint (StartX, yDesc))); + p.append (pf2.map (pt12)); + p.append (pf2.map (pt22)); + // check if something gets in the way + QRegion lineI = shape.intersected (p.boundingRect()); + // if the intersection only has 1 rectangle, then nothing gets in the way + if (lineI.numRects() == 1) + { + int steps = static_cast<int>((maxX - StartX - insets.Right - 2)/0.125); + if (steps > 0) + StartX += steps * 0.125; } + + // qDebug()<<"endOfLine: going for the hard case"; + double EndX2; + double Interval = 0.125; + EndX2 = StartX; + do { + EndX2 += Interval; + int xPos = static_cast<int>(ceil(EndX2 + insets.Right)); + pt12.setX (xPos); + pt22.setX (xPos); + } while ((EndX2 < maxX) && shape.contains(pf2.map(pt12)) && shape.contains(pf2.map(pt22))); + + qDebug()<<EndX<<EndX2<<StartX<<maxX; + if (EndX!=EndX2) qDebug()<<"DIFFERING ENDX!!!!!"; + return EndX; +} double getLineAscent(const StoryText& itemText) |
|
I have uploaded a combo patch that runs both the old and the new code (includes the above change plus a -2 fudge factor to avoid the ceil(), per a conversation Andreas and I had in IRC. All this does is compare the endX values, however this does look like a winner. Needs more testing on real docs with different wrapping options and frame shapes |
2009-04-16 20:17
|
7908_p2.diff (2,378 bytes)
Index: pageitem_textframe.cpp =================================================================== --- pageitem_textframe.cpp (revision 13393) +++ pageitem_textframe.cpp (working copy) @@ -500,14 +500,57 @@ EndX += 0.125; pt1 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(yPos+descent)); pt2 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(ceil(yPos-ascent))); - } while - ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) - && shape.contains(pf2.map(pt1)) - && shape.contains(pf2.map(pt2)) - ); - - return EndX; + } while ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) + && shape.contains(pf2.map(pt1)) + && shape.contains(pf2.map(pt2)) + ); + //original endX calculated now + + + // if we aren't restricted further, we'll end at this maxX: + double maxX = colRight - morespace; + if (legacy) maxX -= lineCorr + insets.Right; + + double StartX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); + int xPos = static_cast<int>(ceil(maxX + insets.Right)); + int yDesc = static_cast<int>(yPos+descent); + int yAsc = static_cast<int>(ceil(yPos-ascent)); + + QPoint pt12 (xPos, yDesc); + QPoint pt22 (xPos, yAsc); + + // simple and fast case: transformed line completely falls within range + // this will happen if we don't wrap around anything - ie. very often + QPolygon p; + p.append (pf2.map (QPoint (StartX, yAsc))); + p.append (pf2.map (QPoint (StartX, yDesc))); + p.append (pf2.map (pt12)); + p.append (pf2.map (pt22)); + // check if something gets in the way + QRegion lineI = shape.intersected (p.boundingRect()); + // if the intersection only has 1 rectangle, then nothing gets in the way + if (lineI.numRects() == 1) + { + int steps = static_cast<int>((maxX - StartX - insets.Right - 2)/0.125); + if (steps > 0) + StartX += steps * 0.125; } + + // qDebug()<<"endOfLine: going for the hard case"; + double EndX2; + double Interval = 0.125; + EndX2 = StartX; + do { + EndX2 += Interval; + int xPos = static_cast<int>(ceil(EndX2 + insets.Right)); + pt12.setX (xPos); + pt22.setX (xPos); + } while ((EndX2 < maxX) && shape.contains(pf2.map(pt12)) && shape.contains(pf2.map(pt22))); + + qDebug()<<EndX<<EndX2<<StartX<<maxX; + if (EndX!=EndX2) qDebug()<<"DIFFERING ENDX!!!!!"; + return EndX; +} double getLineAscent(const StoryText& itemText) |
|
This patch is still producing wildly differing results in some cases.. can u please find out why? |
2009-04-16 20:57
|
|
2009-04-17 19:43
|
7908_p3.diff (2,664 bytes)
Index: scribus/pageitem_textframe.cpp =================================================================== --- scribus/pageitem_textframe.cpp (revision 13396) +++ scribus/pageitem_textframe.cpp (working copy) @@ -500,12 +500,65 @@ EndX += 0.125; pt1 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(yPos+descent)); pt2 = QPoint(qRound(ceil(EndX + insets.Right)), static_cast<int>(ceil(yPos-ascent))); - } while - ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) - && shape.contains(pf2.map(pt1)) - && shape.contains(pf2.map(pt2)) - ); - + } while ( (EndX + (legacy? lineCorr + insets.Right : 0) < colRight - morespace) + && shape.contains(pf2.map(pt1)) + && shape.contains(pf2.map(pt2)) + ); + //original endX calculated now + + + // if we aren't restricted further, we'll end at this maxX: + double maxX = colRight - morespace; + if (legacy) maxX -= (lineCorr + insets.Right); + + double StartX = floor(qMax(line.x, qMin(colRight,breakXPos) - 1)); + double oStartX = StartX; + int xPos = static_cast<int>(ceil(maxX + insets.Right)); + int yDesc = static_cast<int>(yPos+descent); + int yAsc = static_cast<int>(ceil(yPos-ascent)); + + QPoint pt12 (xPos, yDesc); + QPoint pt22 (xPos, yAsc); + + // simple and fast case: transformed line completely falls within range + // this will happen if we don't wrap around anything - ie. very often + QPolygon p; + p.append (pf2.map (QPoint (StartX, yAsc))); + p.append (pf2.map (QPoint (StartX, yDesc))); + p.append (pf2.map (pt12)); + p.append (pf2.map (pt22)); + // check if something gets in the way + QRegion lineI = shape.intersected (p.boundingRect()); + // if the intersection only has 1 rectangle, then nothing gets in the way + if (lineI.numRects() == 1) + { + pt12.setX(StartX + 0.125); + pt22.setX(StartX + 0.125); + if (shape.contains(pf2.map(pt12)) && shape.contains(pf2.map(pt22))) + { + QRect rect = lineI.rects().at(0); + double mx = qMax(rect.left(), rect.right()) - pf2.dx(); + int steps = static_cast<int>((mx - StartX - insets.Right - 2)/0.125); + if (steps > 0) + StartX += steps * 0.125; + } + } + + // qDebug()<<"endOfLine: going for the hard case"; + double EndX2 = StartX; + double Interval = 0.125; + do { + EndX2 += Interval; + int xPos = qRound(ceil(EndX2 + insets.Right)); + pt12.setX (xPos); + pt22.setX (xPos); + } while ((EndX2 < maxX) && shape.contains(pf2.map(pt12)) && shape.contains(pf2.map(pt22))); + + if (EndX!=EndX2) + { + qDebug()<<EndX<<EndX2<<oStartX<<StartX<<maxX; + qDebug()<<"DIFFERING ENDX!!!!!"; + } return EndX; } |
|
I have uploaded a new patch which suppress differences observed when opening that doc. |
|
Committed patch with a small additional fix |
Date Modified | Username | Field | Change |
---|---|---|---|
2009-03-29 16:02 | mecirt | New Issue | |
2009-03-29 16:02 | mecirt | File Added: scribus-layout-speedup.patch | |
2009-03-29 18:55 | mecirt | File Added: scribus-layout-speedup-fixed.patch | |
2009-03-29 18:56 | mecirt | Note Added: 0021437 | |
2009-03-29 21:45 | avox | Note Added: 0021438 | |
2009-03-29 21:47 | cbradney | Note Added: 0021439 | |
2009-03-29 22:58 | cbradney | File Added: 7908equalEndX.diff | |
2009-03-29 22:59 | cbradney | Note Added: 0021440 | |
2009-04-16 20:17 | cbradney | File Added: 7908_p2.diff | |
2009-04-16 20:41 | cbradney | Note Added: 0021539 | |
2009-04-16 20:57 | cbradney | File Added: 20050102-small.sla.gz | |
2009-04-17 19:43 | jghali | File Added: 7908_p3.diff | |
2009-04-17 20:03 | jghali | Note Added: 0021547 | |
2009-04-17 20:40 | cbradney | Status | new => assigned |
2009-04-17 20:40 | cbradney | Assigned To | => jghali |
2009-04-17 23:04 | jghali | Note Added: 0021548 | |
2009-04-17 23:04 | jghali | Status | assigned => resolved |
2009-04-17 23:04 | jghali | Fixed in Version | => 1.3.5svn |
2009-04-17 23:04 | jghali | Resolution | open => fixed |
2009-04-19 21:01 | cbradney | Status | resolved => closed |
2015-09-17 20:08 | Kunda | Category | Story Editor / Text Frames => Story Ed/Txt Frames |
2015-09-17 20:12 | Kunda | Category | Story Ed/Txt Frames => Story Editor / Text Frames |