Author: pfg Date: Tue Jan 3 19:47:32 2012 New Revision: 229415 URL: http://svn.freebsd.org/changeset/base/229415
Log: Integrate the line drawing algorithm from the book "Graphic Gems 1". http://www.graphicsgems.org/ At the time it claimed to be 3-4 times faster than the traditional algorithm. PR: 18769 Approved by: jhb (mentor) MFC after: 2 weeks Modified: head/lib/libvgl/simple.c Modified: head/lib/libvgl/simple.c ============================================================================== --- head/lib/libvgl/simple.c Tue Jan 3 19:44:36 2012 (r229414) +++ head/lib/libvgl/simple.c Tue Jan 3 19:47:32 2012 (r229415) @@ -198,36 +198,205 @@ get_planar: return 0; /* XXX black? */ } + /* + * Symmetric Double Step Line Algorithm by Brian Wyvill from + * "Graphics Gems", Academic Press, 1990. + */ + +#define SL_SWAP(a,b) {a^=b; b^=a; a^=b;} +#define SL_ABSOLUTE(i,j,k) ( (i-j)*(k = ( (i-j)<0 ? -1 : 1))) + +void +plot(VGLBitmap * object, int x, int y, int flag, byte color) +{ + /* non-zero flag indicates the pixels need swapping back. */ + if (flag) + VGLSetXY(object, y, x, color); + else + VGLSetXY(object, x, y, color); +} + + void VGLLine(VGLBitmap *object, int x1, int y1, int x2, int y2, u_long color) { - int d, x, y, ax, ay, sx, sy, dx, dy; + int dx, dy, incr1, incr2, D, x, y, xend, c, pixels_left; + int sign_x, sign_y, step, reverse, i; - dx = x2-x1; ax = ABS(dx)<<1; sx = SGN(dx); x = x1; - dy = y2-y1; ay = ABS(dy)<<1; sy = SGN(dy); y = y1; + dx = SL_ABSOLUTE(x2, x1, sign_x); + dy = SL_ABSOLUTE(y2, y1, sign_y); + /* decide increment sign by the slope sign */ + if (sign_x == sign_y) + step = 1; + else + step = -1; + + if (dy > dx) { /* chooses axis of greatest movement (make dx) */ + SL_SWAP(x1, y1); + SL_SWAP(x2, y2); + SL_SWAP(dx, dy); + reverse = 1; + } else + reverse = 0; + /* note error check for dx==0 should be included here */ + if (x1 > x2) { /* start from the smaller coordinate */ + x = x2; + y = y2; + x1 = x1; + y1 = y1; + } else { + x = x1; + y = y1; + x1 = x2; + y1 = y2; + } + + + /* Note dx=n implies 0 - n or (dx+1) pixels to be set */ + /* Go round loop dx/4 times then plot last 0,1,2 or 3 pixels */ + /* In fact (dx-1)/4 as 2 pixels are already plotted */ + xend = (dx - 1) / 4; + pixels_left = (dx - 1) % 4; /* number of pixels left over at the + * end */ + plot(object, x, y, reverse, color); + if (pixels_left < 0) + return; /* plot only one pixel for zero length + * vectors */ + plot(object, x1, y1, reverse, color); /* plot first two points */ + incr2 = 4 * dy - 2 * dx; + if (incr2 < 0) { /* slope less than 1/2 */ + c = 2 * dy; + incr1 = 2 * c; + D = incr1 - dx; + + for (i = 0; i < xend; i++) { /* plotting loop */ + ++x; + --x1; + if (D < 0) { + /* pattern 1 forwards */ + plot(object, x, y, reverse, color); + plot(object, ++x, y, reverse, color); + /* pattern 1 backwards */ + plot(object, x1, y1, reverse, color); + plot(object, --x1, y1, reverse, color); + D += incr1; + } else { + if (D < c) { + /* pattern 2 forwards */ + plot(object, x, y, reverse, color); + plot(object, ++x, y += step, reverse, + color); + /* pattern 2 backwards */ + plot(object, x1, y1, reverse, color); + plot(object, --x1, y1 -= step, reverse, + color); + } else { + /* pattern 3 forwards */ + plot(object, x, y += step, reverse, color); + plot(object, ++x, y, reverse, color); + /* pattern 3 backwards */ + plot(object, x1, y1 -= step, reverse, + color); + plot(object, --x1, y1, reverse, color); + } + D += incr2; + } + } /* end for */ - if (ax>ay) { /* x dominant */ - d = ay-(ax>>1); - for (;;) { - VGLSetXY(object, x, y, color); - if (x==x2) - break; - if (d>=0) { - y += sy; d -= ax; + /* plot last pattern */ + if (pixels_left) { + if (D < 0) { + plot(object, ++x, y, reverse, color); /* pattern 1 */ + if (pixels_left > 1) + plot(object, ++x, y, reverse, color); + if (pixels_left > 2) + plot(object, --x1, y1, reverse, color); + } else { + if (D < c) { + plot(object, ++x, y, reverse, color); /* pattern 2 */ + if (pixels_left > 1) + plot(object, ++x, y += step, reverse, color); + if (pixels_left > 2) + plot(object, --x1, y1, reverse, color); + } else { + /* pattern 3 */ + plot(object, ++x, y += step, reverse, color); + if (pixels_left > 1) + plot(object, ++x, y, reverse, color); + if (pixels_left > 2) + plot(object, --x1, y1 -= step, reverse, color); + } } - x += sx; d += ay; - } + } /* end if pixels_left */ } - else { /* y dominant */ - d = ax-(ay>>1); - for (;;) { - VGLSetXY(object, x, y, color); - if (y==y2) - break; - if (d>=0) { - x += sx; d -= ay; + /* end slope < 1/2 */ + else { /* slope greater than 1/2 */ + c = 2 * (dy - dx); + incr1 = 2 * c; + D = incr1 + dx; + for (i = 0; i < xend; i++) { + ++x; + --x1; + if (D > 0) { + /* pattern 4 forwards */ + plot(object, x, y += step, reverse, color); + plot(object, ++x, y += step, reverse, color); + /* pattern 4 backwards */ + plot(object, x1, y1 -= step, reverse, color); + plot(object, --x1, y1 -= step, reverse, color); + D += incr1; + } else { + if (D < c) { + /* pattern 2 forwards */ + plot(object, x, y, reverse, color); + plot(object, ++x, y += step, reverse, + color); + + /* pattern 2 backwards */ + plot(object, x1, y1, reverse, color); + plot(object, --x1, y1 -= step, reverse, + color); + } else { + /* pattern 3 forwards */ + plot(object, x, y += step, reverse, color); + plot(object, ++x, y, reverse, color); + /* pattern 3 backwards */ + plot(object, x1, y1 -= step, reverse, color); + plot(object, --x1, y1, reverse, color); + } + D += incr2; + } + } /* end for */ + /* plot last pattern */ + if (pixels_left) { + if (D > 0) { + plot(object, ++x, y += step, reverse, color); /* pattern 4 */ + if (pixels_left > 1) + plot(object, ++x, y += step, reverse, + color); + if (pixels_left > 2) + plot(object, --x1, y1 -= step, reverse, + color); + } else { + if (D < c) { + plot(object, ++x, y, reverse, color); /* pattern 2 */ + if (pixels_left > 1) + plot(object, ++x, y += step, reverse, color); + if (pixels_left > 2) + plot(object, --x1, y1, reverse, color); + } else { + /* pattern 3 */ + plot(object, ++x, y += step, reverse, color); + if (pixels_left > 1) + plot(object, ++x, y, reverse, color); + if (pixels_left > 2) { + if (D > c) /* step 3 */ + plot(object, --x1, y1 -= step, reverse, color); + else /* step 2 */ + plot(object, --x1, y1, reverse, color); + } + } } - y += sy; d += ax; } } } _______________________________________________ svn-src-all@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
