Bug 18769
| Summary: | Minor speedups for libvgl's boxing functions | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Product: | Base System | Reporter: | Pedro F. Giffuni <giffunip> | ||||||||||
| Component: | misc | Assignee: | Pedro F. Giffuni <pfg> | ||||||||||
| Status: | Closed FIXED | ||||||||||||
| Severity: | Affects Only Me | ||||||||||||
| Priority: | Normal | ||||||||||||
| Version: | Unspecified | ||||||||||||
| Hardware: | Any | ||||||||||||
| OS: | Any | ||||||||||||
| Attachments: |
|
||||||||||||
|
Description
Pedro F. Giffuni
2000-05-23 07:20:00 UTC
The attached uu-encoded diff for simple.c further improves VGLFilledBox by avoiding some loops. I am sorry, the previous patch had a minor typo with a problem difficult to notice: 2 --> x2 on VGLBoxFill. The attached file fixes this. Also feel free to nuke the comments. Responsible Changed From-To: freebsd-bugs->sos vgl is another of Soren's babies. I integrated the line drawing algorithm in "Graphic Gems 1"; it claims to be 3-4 times faster than the traditional algorithm. State Changed From-To: open->closed Long since this was relevant, I think vgl is no longer used.. > Long since this was relevant, I think vgl is no > longer used.. > I respectfully disagree with the reasoning around this decision. As long as libvgl is distributed, and in fact included in the FreeBSD base distribution, well documented changes like the generic line drawing algorithm from "Graphic Gems" shouldn't be just dumped in the bit bucket. ______________________________________________________________________ Yahoo! Cellulari: loghi, suonerie, picture message per il tuo telefonino http://it.yahoo.com/mail_it/foot/?http://it.mobile.yahoo.com/index2002.html State Changed From-To: closed->open reopen - unly for the fast line function. Responsible Changed From-To: sos->pfg Assign to myself. 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-unsubscribe@freebsd.org" State Changed From-To: open->patched Commited to head. 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; } } } _______________________________________________ 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-unsubscribe@freebsd.org" State Changed From-To: patched->closed Line drawing algorith was MFC/9 |
