| [AD] Line clipping fix |
[ Thread Index | Date Index | More lists.liballeg.org/allegro-developers Archives ]
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.
*
* See readme.txt for copyright information.
*/
@@ -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/ |