diff options
Diffstat (limited to 'generic/tkCanvUtil.c')
| -rw-r--r-- | generic/tkCanvUtil.c | 269 |
1 files changed, 268 insertions, 1 deletions
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 <assert.h> /* @@ -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; i<numVertex; i++){ + double x, y; + x = coordArr[i*2]; + y = coordArr[i*2+1]; + if( x<lft || x>rgh || y<top || y>btm ) 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<numVertex*2; i++){ + tempArr[i] = coordArr[i]; + } + a = tempArr; + b = &tempArr[numVertex*6]; + + /* We will make four passes through the input data. On each pass, + ** we copy the contents of a[] over into b[]. As we copy, we clip + ** any line segments that extend to the right past xClip then we + ** rotate the coordinate system 90 degrees clockwise. After each + ** pass is complete, we interchange a[] and b[] in preparation for + ** the next pass. + ** + ** Each pass clips line segments that extend beyond a single side + ** of the bounding box, and four passes rotate the coordinate system + ** back to its original value. I'm not an expert on graphics + ** algorithms, but I think this is called Cohen-Sutherland polygon + ** clipping. + ** + ** The limit[] array contains the xClip value used for each of the + ** four passes. + */ + limit[0] = rgh; + limit[1] = -top; + limit[2] = -lft; + limit[3] = btm; + + /* This is the loop that makes the four passes through the data. + */ + maxOutput = numVertex*3; + for(j=0; j<4; j++){ + double xClip = limit[j]; + int inside = a[0]<xClip; + double priorY = a[1]; + numOutput = 0; + + /* Clip everything to the right of xClip. Store the results in + ** b[] rotated by 90 degrees clockwise. + */ + for(i=0; i<numVertex; i++){ + double x = a[i*2]; + double y = a[i*2+1]; + if( x>=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<numVertex; i++){ + translateAndAppendCoords(canvPtr, a[i*2], a[i*2+1], outArr, i); + } + if( tempArr!=staticSpace ){ + ckfree((char *) tempArr); + } + return numOutput; +} |