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.

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 <drh@hwaci.com>
+
+	* 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  <jeffh@ActiveState.com>
 
 	* 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 <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 */