Previous | Table of Contents | Next

### Tracing and Intensity in One

Horizontal, vertical, and diagonal lines do not require Wu antialiasing because they pass through the center of every pixel they meet; such lines can be drawn with fast, special-case code. For all other cases, Wu lines are traced out one step at a time along the major axis by means of a simple, fixed-point algorithm. The move along the minor axis with respect to a one-pixel move along the major axis (the line slope for lines with slopes less than 1, 1/slope for lines with slopes greater than 1) is calculated with a single integer divide. This value, called the “error adjust,” is stored as a fixed-point fraction, in 0.16 format (that is, all bits are fractional, and the decimal point is just to the left of bit 15). An error accumulator, also in 0.16 format, is initialized to 0. Then the first pixel is drawn; no weighting is needed, because the line intersects its endpoints exactly.

Now the error adjust is added to the error accumulator. The error accumulator indicates how far between pixels the line has progressed along the minor axis at any given step; when the error accumulator turns over, it’s time to advance one pixel along the minor axis. At each step along the line, the major-axis coordinate advances by one pixel. The two bracketing pixels to draw are simply the two pixels nearest the line along the minor axis. For instance, if X is the current major-axis coordinate and Y is the current minor-axis coordinate, the two pixels to be drawn are (X,Y) and (X,Y+1). In short, the derivation of the pixels at which to draw involves nothing more complicated than advancing one pixel along the major axis, adding the error adjust to the error accumulator, and advancing one pixel along the minor axis when the error accumulator turns over.

So far, nothing special; but now we come to the true wonder of Wu antialiasing. We know which pair of pixels to draw at each step along the line, but we also need to generate the two proper intensities, which must be inversely proportional to distance from the ideal line and sum to 1, and that’s a potentially time-consuming operation. Let’s assume, however, that the number of possible intensity levels to be used for weighting is the value NumLevels = 2n for some integer n, with the minimum weighting (0 percent intensity) being the value 2n -1, and the maximum weighting (100 percent intensity) being the value 0. Given that, lo and behold, the most significant n bits of the error accumulator select the proper intensity value for one element of the pixel pair, as shown in Figure 42.2. Better yet, 2n-1 minus the intensity of the first pixel selects the intensity of the other pixel in the pair, because the intensities of the two pixels must sum to 1; as it happens, this result can be obtained simply by flipping the n least-significant bits of the first pixel’s value. All this works because what the error accumulator accumulates is precisely the ideal line’s current distance between the two bracketing pixels.

Figure 42.2 Wu intensity calculations.

The intensity calculations take longer to describe than they do to perform. All that’s involved is a shift of the error accumulator to right-justify the desired intensity weighting bits, and then an XOR to flip the least-significant n bits of the first pixel’s value in order to generate the second pixel’s value. Listing 42.1 illustrates just how efficient Wu antialiasing is; the intensity calculations take only three statements, and the entire Wu line-drawing loop is only nine statements long. Of course, a single C statement can hide a great deal of complexity, but Listing 42.6, an assembly implementation, shows that only 15 instructions are required per step along the major axis—and the number of instructions could be reduced to ten by special-casing and loop unrolling. Make no mistake about it, Wu antialiasing is fast.

LISTING 42.1 L42-1.C

    /* Function to draw an antialiased line from (X0,Y0) to (X1,Y1), using an
     * antialiasing approach published by Xiaolin Wu in the July 1991 issue of
     * Computer Graphics. Requires that the palette be set up so that there
     * are NumLevels intensity levels of the desired drawing color, starting at
     * color BaseColor (100% intensity) and followed by (NumLevels-1) levels of
     * evenly decreasing intensity, with color (BaseColor+NumLevels-1) being 0%
     * intensity of the desired drawing color (black). This code is suitable for
     * use at screen resolutions, with lines typically no more than 1K long; for
     * longer lines, 32-bit error arithmetic must be used to avoid problems with
     * fixed-point inaccuracy. No clipping is performed in DrawWuLine; it must be
     * performed either at a higher level or in the DrawPixel function.
     * Tested with Borland C++ in C compilation mode and the small model.
     */
    extern void DrawPixel(int, int, int);

    /* Wu antialiased line drawer.
     * (X0,Y0),(X1,Y1) = line to draw
     * BaseColor = color # of first color in block used for antialiasing, the
     *          100% intensity version of the drawing color
     * NumLevels = size of color block, with BaseColor+NumLevels-1 being the
     *          0% intensity version of the drawing color
     * IntensityBits = log base 2 of NumLevels; the # of bits used to describe
     *          the intensity of the drawing color. 2**IntensityBits==NumLevels
     */
    void DrawWuLine(int X0, int Y0, int X1, int Y1, int BaseColor, int NumLevels,
       unsigned int IntensityBits)
    {
       unsigned int IntensityShift, ErrorAdj, ErrorAcc;
       unsigned int ErrorAccTemp, Weighting, WeightingComplementMask;
       int 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(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(X0, Y0, BaseColor);
          }
          return;
       }
       if (DeltaX == 0) {
          /* Vertical line */
          do {
             Y0++;
             DrawPixel(X0, Y0, BaseColor);
          } while (--DeltaY != 0);
          return;
       }
       if (DeltaX == DeltaY) {
          /* Diagonal line */
          do {
             X0 += XDir;
             Y0++;
             DrawPixel(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(X0, Y0, BaseColor + Weighting);
             DrawPixel(X0 + XDir, Y0,
                   BaseColor + (Weighting ^ WeightingComplementMask));
          }
          /* Draw the final pixel, which is always exactly intersected by the line
             and so needs no weighting */
          DrawPixel(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(X0, Y0, BaseColor + Weighting);
          DrawPixel(X0, Y0 + 1,
                BaseColor + (Weighting ^ WeightingComplementMask));
       }
       /* Draw the final pixel, which is always exactly intersected by the line
          and so needs no weighting */
       DrawPixel(X1, Y1, BaseColor);
    }

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash