Click here to Skip to main content
Click here to Skip to main content

Antialiasing: Wu Algorithm

, 6 Nov 2007
Rate this:
Please Sign up or sign in to vote.
Generating smooth lines with antialiasing; sample code for animation is included

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 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.

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.

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.

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:

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

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. Smile | :) 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

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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

.Suchit
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 his wife and 2 kidbots. Loves reading books if these 2 small buddies allow him to. Smile | :)
 
Homepage : http://www.Suchit-Tiwari.Org

Comments and Discussions

 
GeneralMy vote of 5 Pinmembermanoj kumar choubey26-Mar-12 0:36 
QuestionBaseColor + Weighting ???? How does that work? Pinmemberhugh.court17-Aug-11 23:03 
QuestionSome code copied and pasted from Dr. Dobbs Journal? [modified] Pinmemberbob1697210-Apr-11 16:16 
QuestionAlpha channel? Pinmembermwhouser25-Feb-10 7:52 
Generaldoubt about antialising Pinmemberviritha20-Nov-07 22:44 
GeneralExcellent Pinmembernorm .net14-Nov-07 21:39 
GeneralRe: Excellent Pinmember.Suchit14-Nov-07 22:29 
GeneralRe: Excellent Pinmembernorm .net14-Nov-07 22:33 
QuestionWhat about GDI+? PinmemberLetto7-Nov-07 12:29 
GeneralExcellent! Pinmemberkeanny25-Jul-07 22:42 
GeneralRe: Excellent! Pinmember.Suchit5-Nov-07 4:22 
QuestionLine Thickness PinmemberK.Dog9-Oct-06 22:54 
AnswerRe: Line Thickness Pinmember.Suchit12-Oct-06 17:48 
Generalhttp://www.antigrain.com/ PinmemberPierre Couderc8-Aug-06 19:59 
GeneralRe: http://www.antigrain.com/ Pinmember.Suchit9-Aug-06 6:17 
QuestionFloating point endpoints? Pinmembertilmanator13-Mar-06 18:20 
AnswerRe: Floating point endpoints? Pinmember.Suchit9-Apr-06 3:04 
GeneralRe: Floating point endpoints? Pinmemberviaducting25-Aug-11 1:17 
QuestionThread usage? PinmemberHumanOsc9-Mar-06 3:54 
Generalspeed concerns Pinmember.dan.g.8-Mar-06 13:32 
GeneralRe: speed concerns PinmemberKochise8-Mar-06 21:10 
GeneralRe: speed concerns Pinmember.dan.g.8-Mar-06 21:34 
GeneralRe: speed concerns PinmemberETA28-Mar-06 7:28 
GeneralRe: speed concerns Pinmember.Suchit1-Jun-06 4:34 
AnswerRe: speed concerns Pinmember.Suchit9-Mar-06 2:23 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 6 Nov 2007
Article Copyright 2006 by .Suchit
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid