From 429e43b644753e770d265227a59ab078bb9eaf04 Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 8 Jan 2003 23:02:19 +0000 Subject: Implement Cohen-Sutherland polygon clipping for long lines in the canvas widget so that coordinates do not overflow the 16-bit limit imposed by X11 and Win32. Bug #663981. --- ChangeLog | 8 ++ generic/tkCanvLine.c | 18 ++-- generic/tkCanvUtil.c | 269 ++++++++++++++++++++++++++++++++++++++++++++++++++- generic/tkCanvas.h | 11 ++- 4 files changed, 293 insertions(+), 13 deletions(-) diff --git a/ChangeLog b/ChangeLog index 22f3287..3857b9c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2003-01-08 D. Richard Hipp + + * generic/tkCanvLine.c: + * generic/tkCanvas.h: + * generic/tkCanvUtil.c: Clip long lines so that they will display + properly even on windowing systems where coordinates are expressed + as 16-bit numbers. [But #663981] + 2003-01-03 Jeff Hobbs * generic/tkFrame.c (CreateFrame): throw a Tcl error instead of a diff --git a/generic/tkCanvLine.c b/generic/tkCanvLine.c index 6431830..f597843 100644 --- a/generic/tkCanvLine.c +++ b/generic/tkCanvLine.c @@ -10,7 +10,7 @@ * See the file "license.terms" for information on usage and redistribution * of this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tkCanvLine.c,v 1.11 2002/08/05 04:30:38 dgp Exp $ + * RCS: @(#) $Id: tkCanvLine.c,v 1.12 2003/01/08 23:02:28 drh Exp $ */ #include @@ -848,11 +848,10 @@ DisplayLine(canvas, itemPtr, display, drawable, x, y, width, height) * must be redisplayed (not used). */ { LineItem *linePtr = (LineItem *) itemPtr; - XPoint staticPoints[MAX_STATIC_POINTS]; + XPoint staticPoints[MAX_STATIC_POINTS*3]; XPoint *pointPtr; - XPoint *pPtr; - double *coordPtr, linewidth; - int i, numPoints; + double linewidth; + int numPoints; Tk_State state = itemPtr->state; Pixmap stipple = linePtr->outline.stipple; @@ -897,7 +896,7 @@ DisplayLine(canvas, itemPtr, display, drawable, x, y, width, height) if (numPoints <= MAX_STATIC_POINTS) { pointPtr = staticPoints; } else { - pointPtr = (XPoint *) ckalloc((unsigned) (numPoints * sizeof(XPoint))); + pointPtr = (XPoint *)ckalloc((unsigned)(numPoints * 3*sizeof(XPoint))); } if ((linePtr->smooth) && (linePtr->numPoints > 2)) { @@ -905,11 +904,8 @@ DisplayLine(canvas, itemPtr, display, drawable, x, y, width, height) linePtr->numPoints, linePtr->splineSteps, pointPtr, (double *) NULL); } else { - for (i = 0, coordPtr = linePtr->coordPtr, pPtr = pointPtr; - i < linePtr->numPoints; i += 1, coordPtr += 2, pPtr++) { - Tk_CanvasDrawableCoords(canvas, coordPtr[0], coordPtr[1], - &pPtr->x, &pPtr->y); - } + numPoints = TkCanvTranslatePath((TkCanvas*)canvas, numPoints, + linePtr->coordPtr, 0, pointPtr); } /* diff --git a/generic/tkCanvUtil.c b/generic/tkCanvUtil.c index eb0c3cc..129e63f 100644 --- a/generic/tkCanvUtil.c +++ b/generic/tkCanvUtil.c @@ -10,12 +10,13 @@ * See the file "license.terms" for information on usage and redistribution * of this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tkCanvUtil.c,v 1.8 2002/08/08 04:54:01 hobbs Exp $ + * RCS: @(#) $Id: tkCanvUtil.c,v 1.9 2003/01/08 23:02:30 drh Exp $ */ #include "tkInt.h" #include "tkCanvas.h" #include "tkPort.h" +#include /* @@ -1479,3 +1480,269 @@ DashConvert (l, p, n, width) } return result; } + +/* + *---------------------------------------------------------------------- + * + * translateAndAppendCoords -- + * + * This is a helper routine for TkCanvTranslatePath() below. + * + * Given an (x,y) coordinate pair within a canvas, this procedure + * computes the corresponding coordinates at which the point should + * be drawn in the drawable used for display. Those coordinates are + * then written into outArr[numOut*2] and outArr[numOut*2+1]. + * + * Results: + * There is no return value. + * + * Side effects: + * None. + * + *---------------------------------------------------------------------- + */ + +static void +translateAndAppendCoords(canvPtr, x, y, outArr, numOut) + TkCanvas *canvPtr; /* The canvas. */ + double x, y; /* Coordinates in canvas space. */ + XPoint *outArr; /* Write results into this array */ + int numOut; /* Num of prior entries in outArr[] */ +{ + double tmp; + + tmp = x - canvPtr->drawableXOrigin; + if (tmp > 0) { + tmp += 0.5; + } else { + tmp -= 0.5; + } + outArr[numOut].x = (short) tmp; + + tmp = y - canvPtr->drawableYOrigin; + if (tmp > 0) { + tmp += 0.5; + } else { + tmp -= 0.5; + } + outArr[numOut].y = (short) tmp; +} + +/* + *-------------------------------------------------------------- + * + * TkCanvTranslatePath + * + * Translate a line or polygon path so that all vertices are + * within a rectangle that is 1000 pixels larger than the total + * size of the canvas window. This will prevent pixel coordinates + * from overflowing the 16-bit integer size limitation imposed by + * most windowing systems. + * + * coordPtr must point to an array of doubles, two doubles per + * vertex. There are a total of numVertex vertices, or 2*numVertex + * entries in coordPtr. The result vertices written into outArr + * have their coordinate origin shifted to canvPtr->drawableXOrigin + * by canvPtr->drawableYOrigin. There might be as many as 3 times + * more output vertices than there are input vertices. The calling + * function should allocate space accordingly. + * + * This routine limits the width and height of a canvas window + * to 31767 pixels. At the highest resolution display devices + * available today (210 ppi in Jan 2003) that's a window that is + * over 13 feet wide and tall. Should be enough for the near + * future. + * + * Results: + * Clipped and translated path vertices are written into outArr[]. + * There might be as many as twice the vertices in outArr[] as there + * are in coordPtr[]. The return value is the number of vertices + * actually written into outArr[]. + * + * Side effects: + * None + * + *-------------------------------------------------------------- + */ +int +TkCanvTranslatePath (canvPtr, numVertex, coordArr, closedPath, outArr) + TkCanvas *canvPtr; /* The canvas */ + int numVertex; /* Number of vertices specified by coordArr[] */ + double *coordArr; /* X and Y coordinates for each vertex */ + int closedPath; /* True if this is a closed polygon */ + XPoint *outArr; /* Write results here, if not NULL */ +{ + int numOutput = 0; /* Number of output coordinates */ + double lft, rgh; /* Left and right sides of the bounding box */ + double top, btm; /* Top and bottom sizes of the bounding box */ + double *tempArr; /* Temporary storage used by the clipper */ + double *a, *b, *t; /* Pointers to parts of the temporary storage */ + int i, j; /* Loop counters */ + int maxOutput; /* Maximum number of outputs that we will allow */ + double limit[4]; /* Boundries at which clipping occurs */ + double staticSpace[480]; /* Temp space from the stack */ + + /* Constrain all vertices of the path to be within a box that is 1000 + ** pixels larger than the size of the visible canvas. + ** + ** The complete canvas is used rather than just the redrawing pixmap, + ** so that the line path will always be the same length. Having the + ** same path length is important if the line is dotted or dashed. + */ + assert( canvPtr->tkwin!=NULL ); + lft = canvPtr->xOrigin - 1000; + top = canvPtr->yOrigin - 1000; + rgh = lft + Tk_Width(canvPtr->tkwin) + 2000; + btm = top + Tk_Height(canvPtr->tkwin) + 2000; + + /* Try the common case first - no clipping. Loop over the input + ** coordinates and translate them into appropriate output coordinates. + ** But if a vertex outside of the bounding box is seen, break out of + ** the loop. + ** + ** Most of the time, no clipping is needed, so this one loop is + ** sufficient to do the translation. + */ + for(i=0; irgh || ybtm ) break; + translateAndAppendCoords(canvPtr, x, y, outArr, numOutput++); + } + if( i==numVertex ){ + assert( numOutput==numVertex ); + return numOutput; + } + + /* If we reach this point, it means that some clipping is required. + ** Begin by allocating some working storage - at least 6 times as much space + ** as coordArr[] requires. Divide this space into two separate arrays + ** a[] and b[]. Initialize a[] to be equal to coordArr[]. + */ + if( numVertex*12 <= sizeof(staticSpace)/sizeof(staticSpace[0]) ){ + tempArr = staticSpace; + } else { + tempArr = (double*)ckalloc( numVertex*12*sizeof(tempArr[0]) ); + } + for(i=0; i=xClip ){ + /* The current vertex is to the right of xClip. + */ + if( inside ){ + /* If the current vertex is to the right of xClip but + ** the previous vertex was left of xClip, then draw a + ** line segment from the previous vertex to until it + ** intersects the vertical at xClip. + */ + double x0, y0, yN; + assert( i>0 ); + x0 = a[i*2-2]; + y0 = a[i*2-1]; + yN = y0 + (y - y0)*(xClip-x0)/(x-x0); + b[numOutput*2] = -yN; + b[numOutput*2+1] = xClip; + numOutput++; + assert( numOutput<=maxOutput ); + priorY = yN; + inside = 0; + }else if( i==0 ){ + /* If the first vertex is to the right of xClip, add + ** a vertex that is the projection of the first vertex + ** onto the vertical xClip line. + */ + b[0] = -y; + b[1] = xClip; + numOutput = 1; + priorY = y; + } + }else{ + /* The current vertex is to the left of xClip + */ + if( !inside ){ + /* If the current vertex is on the left of xClip and + ** one or more prior vertices where to the right, then + ** we have to draw a line segment along xClip that extends + ** from the spot where we first crossed from left to right + ** to the spot where we cross back from right to left. + */ + double x0, y0, yN; + assert( i>0 ); + x0 = a[i*2-2]; + y0 = a[i*2-1]; + yN = y0 + (y - y0)*(xClip-x0)/(x-x0); + if( yN!=priorY ){ + b[numOutput*2] = -yN; + b[numOutput*2+1] = xClip; + numOutput++; + assert( numOutput<=maxOutput ); + } + inside = 1; + } + b[numOutput*2] = -y; + b[numOutput*2+1] = x; + numOutput++; + assert( numOutput<=maxOutput ); + } + } + + /* Interchange a[] and b[] in preparation for the next pass. + */ + t = a; + a = b; + b = t; + numVertex = numOutput; + } + + /* All clipping is now finished. Convert the coordinates from doubles + ** into XPoints and translate the origin for the drawable. + */ + for(i=0; i