15,609,332 members
Articles / Multimedia / GDI
Article
Posted 8 Mar 2006

239.6K views
108 bookmarked

# Antialiasing: Wu Algorithm

Rate me:
Generating smooth lines with antialiasing; sample code for animation is included

## Introduction

Jagged lines are major obstacles in achieving professional displays of raster graphics. Antialiasing can produce very smooth lines and provide a stylish appearance. You must already have observed good-looking antialiased diagrams in PowerPoint 2003. They look very smooth. Although GDI+ offers antialiasing, most computers may not have its redistributable. With .NET, you get antialiasing, but again, most computers may not have the .NET framework available. So I prefer writing "Windows portable" programs in VC++ 6. Hence, here is an MFC version of the Wu Antialiasing Algorithm.

## Background

Research has led to the creation of several techniques for antialiasing. Graphics textbooks like Foley, Van Dam discuss the 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, neither have MFC-usable code, so I have implemented their code on MFC.

I wrote a simple `WuCircle` routine to generate a circle made up of line segments. Now let's see the difference that we achieve by using this implementation. Figure 2 shows the zoomed views of the above spokes. The image on the left side shows normal drawing. The jagged edges are clearly visible in it. The right-side image is the antialiased drawing and we can see the smoothing achieved using "GrayScale" intensities.

## Using the Code

You can reuse the function `DrawWuLine`. Just call it anywhere you need to draw an antialiased line.

C++
```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, which you can reuse. Internally, it calls the line routine explained above.

C++
```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 applications.

## Demo: Spokes Animation

This application generates some spokes and concentric circles using both "normal" GDI (non-antialiased) and antialiased line routines. You can press the "a" key to toggle the animation. The animated wheels show a clear distinction between antialiased and normal line drawing.

`RotorThread` is a routine that animates spooked wheels. It uses a memory bitmap and a device context. At ~20 fps (frames per second), it rotates the wheels on a memory bitmap. Using `BitBlt`, the drawing is brought on the main window.

Pressing "a" again terminates the thread.

C++
```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 the implementation of the `DrawWuLine` function:

C++
```void DrawWuLine (CDC *pDC, short X0, short Y0, short X1, short Y1,
short BaseColor, short NumLevels, unsigned short IntensityBits)
{
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) */
/* 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 current 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,
}
/* 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 current 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,
}
/* 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

I hope this will come in handy for some of your applications.

## Resources

Good reference materials:

## Credits

Eien posted a colored version of the algorithm that I had planned as the next installment, for simplicity. :) Thank you, Eien!

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. At the moment, the FLTK project is using this work.

## History

• 8th March, 2006 -- Original version posted
• 10th March, 2006 -- Article moved
• 6th November, 2007 -- Article contents updated

Written By
Architect GE India Innovation Center
India
Suchit is an Architect at GE India Innovation Center, Hyderabad.

He architected and developed portions of Proficy RX, a Process Analytical Technology (PAT) Solution of GE Fanuc Intelligent Platforms.

He also is the Architect of OPC Server for hardware devices of GE Sensing. These devices sense temperature, humidity, combustibles, fluid flow, pressure and various engineering parameters - primarily used in Industrial Automation & Process Control applications.

Interests: Computer Graphics, Mathematical Modeling, Scientific Applications Development.

 First PrevNext
 My vote of 5 Manoj Kumar Choubey26-Mar-12 0:36 Manoj Kumar Choubey 26-Mar-12 0:36
 BaseColor + Weighting ???? How does that work? hugh.court17-Aug-11 23:03 hugh.court 17-Aug-11 23:03
 Some code copied and pasted from Dr. Dobbs Journal? bob1697210-Apr-11 16:16 bob16972 10-Apr-11 16:16
 Alpha channel? mwhouser25-Feb-10 7:52 mwhouser 25-Feb-10 7:52
 doubt about antialising viritha20-Nov-07 22:44 viritha 20-Nov-07 22:44
 Excellent NormDroid14-Nov-07 21:39 NormDroid 14-Nov-07 21:39
 Re: Excellent .Suchit14-Nov-07 22:29 .Suchit 14-Nov-07 22:29
 Re: Excellent NormDroid14-Nov-07 22:33 NormDroid 14-Nov-07 22:33
 What about GDI+? Letto7-Nov-07 12:29 Letto 7-Nov-07 12:29
 Excellent! keanny25-Jul-07 22:42 keanny 25-Jul-07 22:42
 Re: Excellent! .Suchit5-Nov-07 4:22 .Suchit 5-Nov-07 4:22
 Line Thickness K.Dog9-Oct-06 22:54 K.Dog 9-Oct-06 22:54
 Re: Line Thickness .Suchit12-Oct-06 17:48 .Suchit 12-Oct-06 17:48
 http://www.antigrain.com/ Pierre Couderc8-Aug-06 19:59 Pierre Couderc 8-Aug-06 19:59
 Re: http://www.antigrain.com/ .Suchit9-Aug-06 6:17 .Suchit 9-Aug-06 6:17
 Floating point endpoints? tilmanator13-Mar-06 18:20 tilmanator 13-Mar-06 18:20
 Re: Floating point endpoints? .Suchit9-Apr-06 3:04 .Suchit 9-Apr-06 3:04
 Re: Floating point endpoints? hairy_hats25-Aug-11 1:17 hairy_hats 25-Aug-11 1:17
 Thread usage? HumanOsc9-Mar-06 3:54 HumanOsc 9-Mar-06 3:54
 speed concerns .dan.g.8-Mar-06 13:32 .dan.g. 8-Mar-06 13:32
 Re: speed concerns Kochise8-Mar-06 21:10 Kochise 8-Mar-06 21:10
 Re: speed concerns .dan.g.8-Mar-06 21:34 .dan.g. 8-Mar-06 21:34
 Re: speed concerns ETA28-Mar-06 7:28 ETA 28-Mar-06 7:28
 Re: speed concerns .Suchit1-Jun-06 4:34 .Suchit 1-Jun-06 4:34
 Re: speed concerns .Suchit9-Mar-06 2:23 .Suchit 9-Mar-06 2:23
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Mar-23 5:54 Refresh 12 Next ᐅ