summaryrefslogtreecommitdiffstats
path: root/generic
diff options
context:
space:
mode:
authordrh <drh@sqlite.org>2003-01-08 23:02:19 (GMT)
committerdrh <drh@sqlite.org>2003-01-08 23:02:19 (GMT)
commit429e43b644753e770d265227a59ab078bb9eaf04 (patch)
treeac3d9da91203ca0c8d8e76775c90ca1893242007 /generic
parent891029fe3efdaa4b484b55a7d937c4e2d39b7722 (diff)
downloadtk-429e43b644753e770d265227a59ab078bb9eaf04.zip
tk-429e43b644753e770d265227a59ab078bb9eaf04.tar.gz
tk-429e43b644753e770d265227a59ab078bb9eaf04.tar.bz2
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.
Diffstat (limited to 'generic')
-rw-r--r--generic/tkCanvLine.c18
-rw-r--r--generic/tkCanvUtil.c269
-rw-r--r--generic/tkCanvas.h11
3 files changed, 285 insertions, 13 deletions
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 <stdio.h>
@@ -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 <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;
+}
diff --git a/generic/tkCanvas.h b/generic/tkCanvas.h
index cb601a9..402eaa1 100644
--- a/generic/tkCanvas.h
+++ b/generic/tkCanvas.h
@@ -11,7 +11,7 @@
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tkCanvas.h,v 1.6 2002/10/10 07:25:24 hobbs Exp $
+ * RCS: @(#) $Id: tkCanvas.h,v 1.7 2003/01/08 23:02:33 drh Exp $
*/
#ifndef _TKCANVAS
@@ -295,4 +295,13 @@ typedef struct TkCanvas {
extern int TkCanvPostscriptCmd _ANSI_ARGS_((TkCanvas *canvasPtr,
Tcl_Interp *interp, int argc, CONST char **argv));
+/*
+ * Other procedures that are shared among Tk canvas modules but not exported
+ * to the outside world:
+ */
+extern int TkCanvTranslatePath _ANSI_ARGS_((TkCanvas *canvPtr,
+ int numVertex, double *coordPtr, int closed,
+ XPoint *outPtr));
+
+
#endif /* _TKCANVAS */