Click here to Skip to main content
15,867,330 members
Articles / Multimedia / GDI

Antialiasing: Wu Algorithm

Rate me:
Please Sign up or sign in to vote.
4.95/5 (43 votes)
6 Nov 2007CPOL3 min read 253.1K   5.4K   109   26
Generating smooth lines with antialiasing; sample code for animation is included

Image 1

Table of Contents

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.

Image 2

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)
{
   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 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,
               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 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,
            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

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!

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

Your comments and suggestions are always welcome. Just post here.

History

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect GE India Innovation Center
India 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.

He lives in Hyderabad India with. Loves reading books.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey26-Mar-12 0:36
professionalManoj Kumar Choubey26-Mar-12 0:36 
QuestionBaseColor + Weighting ???? How does that work? Pin
hugh.court17-Aug-11 23:03
hugh.court17-Aug-11 23:03 
QuestionSome code copied and pasted from Dr. Dobbs Journal? Pin
bob1697210-Apr-11 16:16
bob1697210-Apr-11 16:16 
QuestionAlpha channel? Pin
mwhouser25-Feb-10 7:52
mwhouser25-Feb-10 7:52 
Generaldoubt about antialising Pin
viritha20-Nov-07 22:44
viritha20-Nov-07 22:44 
GeneralExcellent Pin
NormDroid14-Nov-07 21:39
professionalNormDroid14-Nov-07 21:39 
GeneralRe: Excellent Pin
.Suchit14-Nov-07 22:29
.Suchit14-Nov-07 22:29 
GeneralRe: Excellent Pin
NormDroid14-Nov-07 22:33
professionalNormDroid14-Nov-07 22:33 
QuestionWhat about GDI+? Pin
Letto7-Nov-07 12:29
Letto7-Nov-07 12:29 
GeneralExcellent! Pin
keanny25-Jul-07 22:42
keanny25-Jul-07 22:42 
GeneralRe: Excellent! Pin
.Suchit5-Nov-07 4:22
.Suchit5-Nov-07 4:22 
QuestionLine Thickness Pin
K.Dog9-Oct-06 22:54
K.Dog9-Oct-06 22:54 
AnswerRe: Line Thickness Pin
.Suchit12-Oct-06 17:48
.Suchit12-Oct-06 17:48 
Generalhttp://www.antigrain.com/ Pin
Pierre Couderc8-Aug-06 19:59
Pierre Couderc8-Aug-06 19:59 
GeneralRe: http://www.antigrain.com/ Pin
.Suchit9-Aug-06 6:17
.Suchit9-Aug-06 6:17 
QuestionFloating point endpoints? Pin
tilmanator13-Mar-06 18:20
tilmanator13-Mar-06 18:20 
AnswerRe: Floating point endpoints? Pin
.Suchit9-Apr-06 3:04
.Suchit9-Apr-06 3:04 
GeneralRe: Floating point endpoints? Pin
hairy_hats25-Aug-11 1:17
hairy_hats25-Aug-11 1:17 
QuestionThread usage? Pin
HumanOsc9-Mar-06 3:54
HumanOsc9-Mar-06 3:54 
Generalspeed concerns Pin
.dan.g.8-Mar-06 13:32
professional.dan.g.8-Mar-06 13:32 
GeneralRe: speed concerns Pin
Kochise8-Mar-06 21:10
Kochise8-Mar-06 21:10 
GeneralRe: speed concerns Pin
.dan.g.8-Mar-06 21:34
professional.dan.g.8-Mar-06 21:34 
Kochise wrote:
I think the author just wanted to show how the algorithm performs


indeed (and as i commented), but solutions like this are often ideal where weight is important but only if they are fast enough. and i'm not talking games or other apps with very dynamic requirements, i'm just talking apps that do a bit of drawing.

so if there was a version of the function that was a little more abstracted it might appeal more and to more people (like myself Wink | ;) ).

.dan.g.

AbstractSpoon Software
abstractspoon2_at_optusnet_dot_com_dot_au
GeneralRe: speed concerns Pin
ETA28-Mar-06 7:28
ETA28-Mar-06 7:28 
GeneralRe: speed concerns Pin
.Suchit1-Jun-06 4:34
.Suchit1-Jun-06 4:34 
AnswerRe: speed concerns Pin
.Suchit9-Mar-06 2:23
.Suchit9-Mar-06 2:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.