From owner-svn-src-stable@FreeBSD.ORG Sat Feb 4 04:31:29 2012 Return-Path: Delivered-To: svn-src-stable@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 60F42106566B; Sat, 4 Feb 2012 04:31:29 +0000 (UTC) (envelope-from pfg@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 4E47E8FC13; Sat, 4 Feb 2012 04:31:29 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id q144VT65019187; Sat, 4 Feb 2012 04:31:29 GMT (envelope-from pfg@svn.freebsd.org) Received: (from pfg@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id q144VTcm019185; Sat, 4 Feb 2012 04:31:29 GMT (envelope-from pfg@svn.freebsd.org) Message-Id: <201202040431.q144VTcm019185@svn.freebsd.org> From: "Pedro F. Giffuni" Date: Sat, 4 Feb 2012 04:31:29 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-9@freebsd.org X-SVN-Group: stable-9 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r230975 - stable/9/lib/libvgl X-BeenThere: svn-src-stable@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for all the -stable branches of the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 04 Feb 2012 04:31:29 -0000 Author: pfg Date: Sat Feb 4 04:31:28 2012 New Revision: 230975 URL: http://svn.freebsd.org/changeset/base/230975 Log: MFC: r229415, r229516 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. Make sure this doesn't give problems to clang. PR: 18769 Approved by: jhb (mentor) Modified: stable/9/lib/libvgl/simple.c Directory Properties: stable/9/lib/libvgl/ (props changed) Modified: stable/9/lib/libvgl/simple.c ============================================================================== --- stable/9/lib/libvgl/simple.c Sat Feb 4 03:08:23 2012 (r230974) +++ stable/9/lib/libvgl/simple.c Sat Feb 4 04:31:28 2012 (r230975) @@ -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; } } }