View Issue Details

IDProjectCategoryView StatusLast Update
0007908ScribusStory Editor / Text Framespublic2009-04-19 21:01
Reportermecirt Assigned Tojghali  
PrioritynormalSeverityminorReproducibilityhave not tried
Status closedResolutionfixed 
Platformx86-64OSlinuxOS Versionopensuse 11
Product Version1.3.5svn 
Fixed in Version1.3.5svn 
Summary0007908: Text relayouting is slow (partial patch attached)
DescriptionRelayouting 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.
TagsNo tags attached.
Patch

Activities

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;
 	}
 	
scribus-layout-speedup.patch (1,931 bytes)   

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;
 	}
 	

mecirt

2009-03-29 18:56

reporter   ~0021437

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.

avox

2009-03-29 21:45

administrator   ~0021438

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.

cbradney

2009-03-29 21:47

administrator   ~0021439

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)
7908equalEndX.diff (2,378 bytes)   

cbradney

2009-03-29 22:59

administrator   ~0021440

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)
7908_p2.diff (2,378 bytes)   

cbradney

2009-04-16 20:41

administrator   ~0021539

This patch is still producing wildly differing results in some cases.. can u please find out why?

2009-04-16 20:57

 

20050102-small.sla.gz (19,182 bytes)

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;
 	}
 	
7908_p3.diff (2,664 bytes)   

jghali

2009-04-17 20:03

administrator   ~0021547

I have uploaded a new patch which suppress differences observed when opening that doc.

jghali

2009-04-17 23:04

administrator   ~0021548

Committed patch with a small additional fix

Issue History

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