Antialiasing: Wu Algorithm

• Download demo executable - 5.97 KB
• Download VC++ source & workspace - 19.7 KB

Table of Contents

• Introduction
• Background
• Using the Code
• Demo: Spokes Animation
• DrawWuLine Function
• Resources
• Credits

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.

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.

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.

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;
}

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

• A colored version of the WuLine is available here.

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

Good reference materials:

• Michael Abrash's Graphics Programming Black Book.
• Hugo Elias' Theory of Wu Lines.
• Textbook: Computer Graphics by Foley, Van Dam et. al.

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

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