Antialiasing: Wu Algorithm
Table of Contents
Introduction
Jagged lines are obstacle in achieving professional display of raster graphics. Antialiasing can produce very smooth lines and provide stylish appearance. You already observed good looking antialiased diagrams in PowerPoint 2003. They look very smooth.
Though GDI+ offers antialiasing, most computers may not have its redistributable. With .NET you get antialiasing but similarly, most computers still may not have .NET framework. So I prefer
writing "Windows Portable" programs in VC++ 6. Hence here is MFC version of Wu Antialiasing Algorithm.
Background
Research has led to creation of several techniques for antialiasing. Graphics text books like Foley, Van Dam
discuss Gupta-Sproul and related algorithms. For fast antialiasing, Xiaolin Wu invented an algorithm -
called by his name Wu Antialiasing.
Michael Abrash's Graphics Programming Black Book gives excellent treatment of this algorithm. Hugo Elias also has an excellent article on the matter. I strongly recommend reading this one.
However, both do not have MFC usable code. So I have implemented their code on MFC. I wrote a simple WuCircle routine to generate circle
made up of line segments.
Now let's see difference that we achieve by implementation. Figure 2, shows zoomed views of above spokes. Left side is normal drawing. Jagged edges are clearly visible. Right side antialiased drawing, we can see smoothing achieved using "GrayScale" intensities.
Using the Code
You can reuse the function DrawWuLine. Just call it anywhere you need to draw antialiased line.
void DrawWuLine (CDC *pDC, short X0, short Y0, short X1, short Y1,
short BaseColor, short NumLevels, unsigned short IntensityBits);
/*
Arguments:
+ pDC is where line is drawn. Can be memory device context.
+ (X0,Y0) is start point of line.
+ (X1, Y1) is end point of line.
+ BaseColor is intensity of line. Pass 0 for black line.
+ NumLevels is number of gray scale levels. Pass 256.
+ IntensityBits denotes bits used to represent color component. Pass 8.
Note: NumLevels and IntensityBits have been preserved from Michael Abrash's implementation.
They come very handy in customizing drawing algorithm on different graphics hardware.
You may hardcode them.
*/
There is a simple routine for circle generation. That also you can reuse. Internally it calls the line routine
explained above.
void DrawWuCirlce (CDC * pDC, int x, int y, int r); /* Arguments: + pDC is where circle is drawn. Can be memory device context. + (x,y) is center of circle. + r is radius of circle. */Both functions can be easily modified to use HDC instead of CDC *, in case you are writing non-MFC Win32 application.
Demo: Spokes Animation
This application generates some spokes and concentric circles using "normal" GDI (non antialiased) and antialiased line routines. You can press 'a' key to toggle animation. Animated wheels show clear distinction between antialiased & normal line drawing.RotorThread is a routine that animates spoked wheels. It uses memory bitmap and device context.
And at ~20 fps (frames per second), it rotates the wheels on memory bitmap. Using BitBlt the drawing
is brought on the main window.
Pressing 'a' again, terminates the thread.
UINT RotorThread (LPVOID lpVoid)
{
bool * pbStop = (bool *) lpVoid;
CWnd * pWnd = AfxGetMainWnd();
CDC * pDC = pWnd->GetDC();
CRect rect;
pWnd->GetClientRect (&rect);
CDC memDC;
memDC.CreateCompatibleDC (pDC);
CBitmap bitmap;
bitmap.CreateCompatibleBitmap (pDC, rect.Width(), rect.Height());
memDC.SelectObject (&bitmap);
CFont font;
font.CreatePointFont (185, "Verdana", &memDC);
memDC.SelectObject (&font);
memDC.SetTextAlign (TA_CENTER);
float phase = 0.0f;
while (!(*pbStop))
{
//1. Erase Background.
memDC.Rectangle (0, 0, rect.Width(), rect.Height());
//2. Draw new contents.
memDC.TextOut (100, 15, "Normal");
memDC.TextOut (350, 15, "Anti-aliased");
short x, y;
for (float theta= phase; theta< 360+phase; theta += 10 )
{
x = (short)(100.0*cos(theta*3.14/180.0)+355.0);
y = (short)(-100.0*sin(theta*3.14/180.0)+155.0);
DrawWuLine (&memDC,x, y, 355, 155, 0, 256, 8);
memDC.MoveTo (x-240,y);
memDC.LineTo (115,155);
}
//3. Blit drawing on screen.
pDC->BitBlt (0, 0, rect.Width(), rect.Height(), &memDC, 0, 0, SRCCOPY);
//4. Update animation parameter.
phase += 1;
::Sleep (67); //15 fps.
}
font.DeleteObject();
bitmap.DeleteObject();
memDC.DeleteDC();
pWnd->ReleaseDC (pDC);
return 0;
}
DrawWuLine Function
Here is implementation of DrawWuLine function.
void DrawWuLine (CDC *pDC, short X0, short Y0, short X1, short Y1,
short BaseColor, short NumLevels, unsigned short IntensityBits)
{
unsigned short IntensityShift, ErrorAdj, ErrorAcc;
unsigned short ErrorAccTemp, Weighting, WeightingComplementMask;
short DeltaX, DeltaY, Temp, XDir;
/* Make sure the line runs top to bottom */
if (Y0 > Y1) {
Temp = Y0; Y0 = Y1; Y1 = Temp;
Temp = X0; X0 = X1; X1 = Temp;
}
/* Draw the initial pixel, which is always exactly intersected by
the line and so needs no weighting */
DrawPixel(pDC,X0, Y0, BaseColor);
if ((DeltaX = X1 - X0) >= 0) {
XDir = 1;
} else {
XDir = -1;
DeltaX = -DeltaX; /* make DeltaX positive */
}
/* Special-case horizontal, vertical, and diagonal lines, which
require no weighting because they go right through the center of
every pixel */
if ((DeltaY = Y1 - Y0) == 0) {
/* Horizontal line */
while (DeltaX-- != 0) {
X0 += XDir;
DrawPixel(pDC,X0, Y0, BaseColor);
}
return;
}
if (DeltaX == 0) {
/* Vertical line */
do {
Y0++;
DrawPixel(pDC,X0, Y0, BaseColor);
} while (--DeltaY != 0);
return;
}
if (DeltaX == DeltaY) {
/* Diagonal line */
do {
X0 += XDir;
Y0++;
DrawPixel(pDC,X0, Y0, BaseColor);
} while (--DeltaY != 0);
return;
}
/* Line is not horizontal, diagonal, or vertical */
ErrorAcc = 0; /* initialize the line error accumulator to 0 */
/* # of bits by which to shift ErrorAcc to get intensity level */
IntensityShift = 16 - IntensityBits;
/* Mask used to flip all bits in an intensity weighting, producing the
result (1 - intensity weighting) */
WeightingComplementMask = NumLevels - 1;
/* Is this an X-major or Y-major line? */
if (DeltaY > DeltaX) {
/* Y-major line; calculate 16-bit fixed-point fractional part of a
pixel that X advances each time Y advances 1 pixel, truncating the
result so that we won't overrun the endpoint along the X axis */
ErrorAdj = ((unsigned long) DeltaX << 16) / (unsigned long) DeltaY;
/* Draw all pixels other than the first and last */
while (--DeltaY) {
ErrorAccTemp = ErrorAcc; /* remember currrent accumulated error */
ErrorAcc += ErrorAdj; /* calculate error for next pixel */
if (ErrorAcc <= ErrorAccTemp) {
/* The error accumulator turned over, so advance the X coord */
X0 += XDir;
}
Y0++; /* Y-major, so always advance Y */
/* The IntensityBits most significant bits of ErrorAcc give us the
intensity weighting for this pixel, and the complement of the
weighting for the paired pixel */
Weighting = ErrorAcc >> IntensityShift;
DrawPixel(pDC,X0, Y0, BaseColor + Weighting);
DrawPixel(pDC,X0 + XDir, Y0,
BaseColor + (Weighting ^ WeightingComplementMask));
}
/* Draw the final pixel, which is always exactly intersected by the line
and so needs no weighting */
DrawPixel(pDC,X1, Y1, BaseColor);
return;
}
/* It's an X-major line; calculate 16-bit fixed-point fractional part of a
pixel that Y advances each time X advances 1 pixel, truncating the
result to avoid overrunning the endpoint along the X axis */
ErrorAdj = ((unsigned long) DeltaY << 16) / (unsigned long) DeltaX;
/* Draw all pixels other than the first and last */
while (--DeltaX) {
ErrorAccTemp = ErrorAcc; /* remember currrent accumulated error */
ErrorAcc += ErrorAdj; /* calculate error for next pixel */
if (ErrorAcc <= ErrorAccTemp) {
/* The error accumulator turned over, so advance the Y coord */
Y0++;
}
X0 += XDir; /* X-major, so always advance X */
/* The IntensityBits most significant bits of ErrorAcc give us the
intensity weighting for this pixel, and the complement of the
weighting for the paired pixel */
Weighting = ErrorAcc >> IntensityShift;
DrawPixel(pDC,X0, Y0, BaseColor + Weighting);
DrawPixel(pDC,X0, Y0 + 1,
BaseColor + (Weighting ^ WeightingComplementMask));
}
/* Draw the final pixel, which is always exactly intersected by the line
and so needs no weighting */
DrawPixel(pDC,X1, Y1, BaseColor);
}
Colored Version of WuLine
Here.Hope this will come handy in some of your applications.
Resources
Good reference material.- Michael Abrash's Graphics Programming Black Book.
- Hugo Elias's Theory of Wu Lines.
- Text Book: Computer Graphics by Foley, Van Dam et. al.
Credits
Eien posted colored version of the algorithm, that I had planned as next installment for simplicity. :) Thank you Eien!Updates
The entire code for this has been hosted at Google Code to enable Open Source development. Please feel free to join that development group and contribute to it. Link to the homepage at Google Code is http://code.google.com/p/wu-antialiasing/. At the moment FLTK project is using this work. http://www.fltk.org/.
Your comments and suggestions are always welcome. Just drop me a line Suchit.Tiwari@Ge.com or post here.