[AD] Line clipping fix

```Hi Everyone,

I have gotten line drawing to clip properly while
keeping track of the bresenham state.  It should be
faster than 4.1.11 for clipped lines and should be
almost as fast as the pixel incorrect version in
4.1.12.  I dont know if there are standardized speed
or regression tests that need to be run.

I've also made a test program to show the problems
with 4.1.12.

I dont know anything about gettign this code into
allegro.  I assume that someone can (test and) apply
this patch?

Doug Eleveld

__________________________________
Do you Yahoo!?
Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes
http://hotjobs.sweepstakes.yahoo.com/signingbonus```
```--- gfx12.c	2004-01-15 14:35:24.000000000 +0000
+++ gfx.c	2004-01-15 14:45:24.000000000 +0000
@@ -16,7 +16,7 @@
*
*      Bresenham arc routine by Romano Signorelli.
*
- *      Cohen-Sutherland line clipping by Jon Rafkind.
+ *      Clipping of Bresenham state for line drawing by Doug Eleveld.
*
*/
@@ -684,132 +684,250 @@

/* _normal_line:
- *  Draws a line from x1, y1 to x2, y2, using putpixel() to do the work.
- *  This is an implementation of the Cohen-Sutherland line clipping algorithm.
- *  Loops over the line until it can be either trivially rejected or trivially
- *  accepted. If it is neither rejected nor accepted, subdivide it into two
- *  segments, one of which can be rejected.
+ *  Draws a line from x1, y1 to x2, y2.  The start and end points are clipped
+ *  using the Bresenham state and Cohen-Sutherland line algorithm is used to
+ *  trivially reject lines.
*/
void _normal_line(BITMAP *bmp, int x1, int y1, int x2, int y2, int color)
{
-   int code0, code1;
-   int outcode;
-   int x, y;
-   int xmax, xmin, ymax, ymin;
-   int done = 0, accept = 0;
-   int clip_orig;
-   ASSERT(bmp);
-
-   if ((clip_orig = bmp->clip) != 0) {  /* save clipping state */
-      #define TOP     0x8
-      #define BOTTOM  0x4
-      #define LEFT    0x2
-      #define RIGHT   0x1
-
-      #define COMPCLIP(code, x, y)  \
-      {                             \
-	 code = 0;                  \
-	 if (y < ymin)              \
-	    code |= TOP;            \
-	 else if (y > ymax)         \
-	    code |= BOTTOM;         \
-	 if (x < xmin)              \
-	    code |= LEFT;           \
-	 else if (x > xmax)         \
-	    code |= RIGHT;          \
-      }
-
-      xmin = bmp->cl;
-      xmax = bmp->cr-1;
-      ymin = bmp->ct;
-      ymax = bmp->cb-1;
-
-      COMPCLIP(code0, x1, y1);
-      COMPCLIP(code1, x2, y2);
-
-      do {
-
-	 if (!(code0 | code1)) {
-	    /* Trivially accept. */
-	    accept = done = 1;
-	 }
-	 else if (code0 & code1) {
-	    /* Trivially reject. */
-	    done = 1;
-	 }
-	 else {
-	    /* Didn't reject or accept, so do some calculations. */
-	    outcode = code0 ? code0 : code1;  /* pick one endpoint */
-
-	    if (outcode & TOP) {
-	       if (y2 == y1)
-		  x = x1;
-	       else
-		  x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
-	       y = ymin;
-	    }
-	    else if (outcode & BOTTOM) {
-	       if (y2 == y1)
-		  x = x1;
-	       else
-		  x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
-	       y = ymax;
-	    }
-	    else if (outcode & LEFT) {
-	       if (x2 == x1)
-		  y = y1;
-	       else
-		  y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
-	       x = xmin;
-	    }
-	    else {  /* outcode & RIGHT */
-	       if (x2 == x1)
-		  y = y1;
-	       else
-		  y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
-	       x = xmax;
-	    }
-
-	    if (outcode == code0) {
-	       x1 = x;
-	       y1 = y;
-	       COMPCLIP(code0, x1, y1);
-	    }
-	    else {
-	       x2 = x;
-	       y2 = y;
-	       COMPCLIP(code1, x2, y2);
-	    }
-	 }
-      } while (!done);
-
-      #undef COMPCLIP
-      #undef TOP
-      #undef BOTTOM
-      #undef LEFT
-      #undef RIGHT
-
-      if (!accept)
-	 return;
-
-      /* We have already done the clipping, no need to do it again. */
-      bmp->clip = FALSE;
-   }
-
-   if (x1 == x2) {
-      bmp->vtable->vline(bmp, x1, y1, y2, color);
-   }
-   else if (y1 == y2) {
-      bmp->vtable->hline(bmp, x1, y1, x2, color);
-   }
-   else {
-      acquire_bitmap(bmp);
-      do_line(bmp, x1, y1, x2, y2, color, bmp->vtable->putpixel);
-      release_bitmap(bmp);
-   }
-
-   /* Restore original clipping state. */
-   bmp->clip = clip_orig;
+#define CLIP_VLINE(bmp, xa, ya, yb)                                       \
+   (((xa) < (bmp)->cl) ||                                                 \
+    ((xa) > (bmp)->cr) ||                                                 \
+    (((yb) = MIN((yb), ((bmp)->cb))) < ((ya) = MAX((ya), ((bmp)->ct)))))
+
+#define CLIP_HLINE(bmp, xa, ya, xb)                                       \
+   (((ya) < (bmp)->ct) ||                                                 \
+    ((ya) > (bmp)->cb) ||                                                 \
+    (((xb) = MIN((xb), ((bmp)->cr))) < ((xa) = MAX((xa), ((bmp)->cl)))))
+
+#define GETCODE(x, y, code) \
+    do {                    \
+        if (x < bmp->cl)    \
+            code |= 1;      \
+        if (x >= bmp->cr)   \
+            code |= 2;      \
+        if (y < bmp->ct)    \
+            code |= 4;      \
+        if (y >= bmp->cb)   \
+            code |= 8;      \
+    } while (0)
+
+#define SWAP(a,b)           \
+    do {                    \
+        const int temp = a; \
+        a = b;              \
+        b = temp;           \
+    } while (0)
+
+    int code1 = 0, code2 = 0;
+    const int clip_orig = bmp->clip;
+    const int dy = abs(y2 - y1) << 1;
+    const int dx = abs(x2 - x1) << 1;
+    const int cl = bmp->cl;
+    const int cr = bmp->cr - 1;
+    const int ct = bmp->ct;
+    const int cb = bmp->cb - 1;
+
+    if ((cr < cl) ||
+        (cb < ct))
+        return;
+
+    GETCODE(x1, y1, code1);
+    GETCODE(x2, y2, code2);
+    if (code1 & code2)
+        return;
+
+    /* Within this function we dont need clipping */
+    bmp->clip = FALSE;
+
+    if (dx == 0) {
+
+        if (y2 < y1) {
+            SWAP(x1, x2);
+            SWAP(y1, y2);
+        }
+
+        if (clip_orig)
+            if (CLIP_VLINE(bmp, x1, y1, y2))
+                goto done;
+
+        bmp->vtable->vline(bmp, x1, y1, y2, color);
+
+    } else if (dy == 0) {
+
+        if (x2 < x1) {
+            SWAP(x1, x2);
+            SWAP(y1, y2);
+        }
+
+        if (clip_orig)
+           if (CLIP_HLINE(bmp, x1, y1, x2))
+                goto done;
+
+        bmp->vtable->hline(bmp, x1, y1, x2, color);
+
+    } else if (dx > dy) {
+        int stepy, stopy;
+        int fraction = dy - (dx >> 1);
+
+        if (x2 < x1) {
+            SWAP(x1, x2);
+            SWAP(y1, y2);
+        }
+
+        if (y2 > y1) {
+            stepy = 1;
+            stopy = cb + 1;
+        } else {
+            stepy = -1;
+            stopy = ct - 1;
+        }
+
+        if (x1 < cl) {
+            const int xn = cl - x1;
+            const int cy = (fraction + xn * dy - dy + dx) / dx;
+
+            x1 = cl;
+            y1 = y1 + cy * stepy;
+            fraction = fraction - cy * dx + xn * dy;
+        }
+
+        x2 = MIN(x2, cr);
+        if (x1 > x2)
+            goto done;;
+
+        if (((stepy == 1) && (y1 > cb)) ||
+            ((stepy == -1) && (y1 < ct)))
+            goto done;;
+
+        if (y2 == y1) {
+            if (clip_orig)
+                if (CLIP_HLINE(bmp, x1, y1, x2))
+                    goto done;
+
+            bmp->vtable->hline(bmp, x1, y1, x2, color);
+            goto done;
+
+        } else if ((stepy == 1) && (y1 < ct)) {
+            const int yn = ct - y1;
+            const int cx = (dy - dx - fraction + yn * dx + dy - 1) / dy;
+
+            x1 = x1 + cx;
+            y1 = ct;
+            fraction = fraction - yn * dx + cx * dy;
+
+        } else if ((stepy == -1) && (y1 > cb)) {
+            const int yn = y1 - cb;
+            const int cx = (dy - dx - fraction + yn * dx + dy - 1) / dy;
+
+            x1 = x1 + cx;
+            y1 = cb;
+            fraction = fraction - yn * dx + cx * dy;
+        }
+
+        if (x1 > x2)
+            goto done;
+
+        acquire_bitmap(bmp);
+
+        while ((x1 <= x2) && (y1 != stopy)) {
+            bmp->vtable->putpixel(bmp, x1, y1, color);
+
+            if (fraction >= 0) {
+                y1 += stepy;
+                fraction -= dx;
+            }
+            ++x1;
+            fraction += dy;
+        }
+
+        release_bitmap(bmp);
+
+    } else {
+        int stepx, stopx;
+        int fraction = dx - (dy >> 1);
+
+        if (y2 < y1) {
+            SWAP(y1, y2);
+            SWAP(x1, x2);
+        }
+
+        if (x2 > x1) {
+            stepx = 1;
+            stopx = cr + 1;
+        } else {
+            stepx = -1;
+            stopx = cl - 1;
+        }
+
+        if (y1 < ct) {
+            const int yn = ct - y1;
+            const int cx = (fraction + yn * dx - dx + dy) / dy;
+
+            y1 = ct;
+            x1 = x1 + cx * stepx;
+            fraction = fraction - cx * dy + yn * dx;
+        }
+
+        y2 = MIN(y2, cb);
+        if (y1 > y2)
+            goto done;;
+
+        if (((stepx == 1) && (x1 > cr)) ||
+            ((stepx == -1) && (x1 < cl)))
+            goto done;
+
+        if (x2 == x1) {
+            if (clip_orig)
+                if (CLIP_VLINE(bmp, x1, y1, y2))
+                    goto done;
+
+            bmp->vtable->vline(bmp, x1, y1, y2, color);
+            goto done;
+
+        } else if ((stepx == 1) && (x1 < cl)) {
+            const int xn = cl - x1;
+            const int cy = (dx - dy - fraction + xn * dy + dx - 1) / dx;
+
+            y1 = y1 + cy;
+            x1 = cl;
+            fraction = fraction - xn * dy + cy * dx;
+
+        } else if ((stepx == -1) && (x1 > cr)) {
+            const int xn = x1 - cr;
+            const int cy = (dx - dy - fraction + xn * dy + dx - 1) / dx;
+
+            y1 = y1 + cy;
+            x1 = cr;
+            fraction = fraction - xn * dy + cy * dx;
+        }
+
+        if (y1 > y2)
+            goto done;
+
+        acquire_bitmap(bmp);
+
+        while ((y1 <= y2) && (x1 != stopx)) {
+            bmp->vtable->putpixel(bmp, x1, y1, color);
+
+            if (fraction >= 0) {
+                x1 += stepx;
+                fraction -= dy;
+            }
+            ++y1;
+            fraction += dx;
+        }
+
+        release_bitmap(bmp);
+    }
+
+#undef CLIP_VLINE
+#undef CLIP_HLINE
+#undef GETCODE
+#undef SWAP
+
+done:
+    bmp->clip = clip_orig;
}

```

Attachment: Linetest.c
Description: Linetest.c

```CFLAGS = -O4 -fomit-frame-pointer -DNDEBUG -s

EXAMPLES = linetest.exe

all : \$(EXAMPLES)

%o : %c
gcc -c \$(CFLAGS) \$<

%exe : %o
gcc -L. -s -o \$@ \$(?F) -lalleg

```

 Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/