Previous Table of Contents Next


LISTING 42.6 L42-6.ASM

; C near-callable function to draw an antialiased line from
; (X0,Y0) to (X1,Y1), in mode 13h, the VGA's standard 320x200 256-color
; mode. Uses 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). No clipping is
; performed in DrawWuLine. Handles a maximum of 256 intensity levels per
; antialiased color. 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.
; Tested with TASM.
;
; C near-callable as:
;   void DrawWuLine(int X0, int Y0, int X1, int Y1, int BaseColor,
;      int NumLevels, unsigned int IntensityBits);

SCREEN_WIDTH_IN_BYTES equ 320;# of bytes from the start of one scan line
; to the start of the next
SCREEN_SEGMENT   equ   0a000h;segment in which screen memory resides

; Parameters passed in stack frame.
parms   struc
     dw    2 dup (?) ;pushed BP and return address
X0   dw    ?         ;X coordinate of line start point
Y0   dw    ?         ;Y coordinate of line start point
X1   dw    ?         ;X coordinate of line end point
Y1   dw    ?         ;Y coordinate of line end point
BaseColor dw     ?       ;color # of first color in block used for
                     ;antialiasing, the 100% intensity version of the
                     ;drawing color
NumLevels dw     ?       ;size of color block, with BaseColor+NumLevels-1
                     ; being the 0% intensity version of the drawing color
                     ; (maximum NumLevels = 256)
IntensityBits dw ?       ;log base 2 of NumLevels; the # of bits used to
                     ; describe the intensity of the drawing color.
                     ; 2**IntensityBits==NumLevels
                     ; (maximum IntensityBits = 8)
parms ends

.model  small
.code
; Screen dimension globals, used in main program to scale.
_ScreenWidthInPixels    dw      320
_ScreenHeightInPixels   dw      200

        .code
        public   _DrawWuLine
_DrawWuLine proc near
        push    bp      ;preserve caller's stack frame
        mov     bp,sp   ;point to local stack frame
        push    si      ;preserve C's register variables
        push    di
        push    ds      ;preserve C's default data segment
        cld             ;make string instructions increment their pointers

; Make sure the line runs top to bottom.
        mov     si,[bp].X0
        mov     ax,[bp].Y0
        cmp     ax,[bp].Y1   ;swap endpoints if necessary to ensure that
        jna     NoSwap       ; Y0 <= Y1
        xchg    [bp].Y1,ax
        mov     [bp].Y0,ax
        xchg    [bp].X1,si
        mov     [bp].X0,si
NoSwap:

; Draw the initial pixel, which is always exactly intersected by the line
; and so needs no weighting.
        mov     dx,SCREEN_SEGMENT
        mov     ds,dx           ;point DS to the screen segment
        mov     dx,SCREEN_WIDTH_IN_BYTES
        mul     dx              ;Y0 * SCREEN_WIDTH_IN_BYTES yields the offset
                                ; of the start of the row start the initial
                                ; pixel is on
        add     si,ax           ;point DS:SI to the initial pixel
        mov     al,byte ptr [bp].BaseColor ;color with which to draw
        mov     [si],al         ;draw the initial pixel

        mov     bx,1            ;XDir = 1; assume DeltaX >= 0
        mov     cx,[bp].X1
        sub     cx,[bp].X0      ;DeltaX; is it >= 1?
        jns     DeltaXSet       ;yes, move left->right, all set
                                ;no, move right->left
        neg     cx              ;make DeltaX positive
        neg     bx              ;XDir = -1
DeltaXSet:

; Special-case horizontal, vertical, and diagonal lines, which require no
; weighting because they go right through the center of every pixel.
        mov     dx,[bp].Y1
        sub     dx,[bp].Y0      ;DeltaY; is it 0?
        jnz     NotHorz         ;no, not horizontal
                                ;yes, is horizontal, special case
        and     bx,bx           ;draw from left->right?
        jns     DoHorz          ;yes, all set
        std                     ;no, draw right->left
DoHorz:
        lea     di,[bx+si]      ;point DI to next pixel to draw
        mov     ax,ds
        mov     es,ax           ;point ES:DI to next pixel to draw
        mov     al,byte ptr [bp].BaseColor ;color with which to draw
                                ;CX = DeltaX at this point
        rep     stosb           ;draw the rest of the horizontal line
        cld                             ;restore default direction flag
        jmp     Done                    ;and we're done

        align2
NotHorz:
        and     cx,cx                   ;is DeltaX 0?
        jnz     NotVert                 ;no, not a vertical line
                                        ;yes, is vertical, special case
        mov     al,byte ptr [bp].BaseColor  ;color with which to draw
VertLoop:
        add     si,SCREEN_WIDTH_IN_BYTES    ;point to next pixel to draw
        mov     [si],al                 ;draw the next pixel
        dec     dx                      ;--DeltaY
        jnz     VertLoop
        jmp     Done                    ;and we're done
        
        align2
NotVert:
        cmp     cx,dx                   ;DeltaX == DeltaY?
        jnz     NotDiag                 ;no, not diagonal
                                        ;yes, is diagonal, special case
        mov     al,byte ptr [bp].BaseColor  ;color with which to draw
DiagLoop:
        lea     si,[si+SCREEN_WIDTH_IN_BYTES+bx]
                                        ;advance to next pixel to draw by
                                        ; incrementing Y and adding XDir to X
        mov     [si],al                 ;draw the next pixel
        dec     dx                      ;--DeltaY
        jnz     DiagLoop
        jmp     Done                    ;and we're done

; Line is not horizontal, diagonal, or vertical.
        align2
NotDiag:
; Is this an X-major or Y-major line?
        cmp     dx,cx
        jbX     Major                   ;it's X-major

; It's a Y-major line. Calculate the 16-bit fixed-point fractional part of a
; pixel that X advances each time Y advances 1 pixel, truncating the result
; to avoid overrunning the endpoint along the X axis.
        xchg    dx,cx           ;DX = DeltaX, CX = DeltaY
        sub     ax,ax           ;make DeltaX 16.16 fixed-point value in DX:AX
        div     cx              ;AX = (DeltaX << 16) / DeltaY. Won't overflow
                                ; because DeltaX < DeltaY
        mov     di,cx           ;DI = DeltaY (loop count)
        sub     si,bx           ;back up the start X by 1, as explained below
        mov     dx,-1           ;initialize the line error accumulator to -1,
                                ; so that it will turn over immediately and
                                ; advance X to the start X. This is necessary
                                ; properly to bias error sums of 0 to mean
                                ; "advance next time" rather than "advance
                                ; this time," so that the final error sum can
                                ; never cause drawing to overrun the final X
                                ; coordinate (works in conjunction with
                                ; truncating ErrorAdj, to make sure X can't
                                ; overrun)
        mov     cx,8            ;CL = # of bits by which to shift
        sub     cx,[bp].IntensityBits  ; ErrorAcc to get intensity level (8
                                ; instead of 16 because we work only
                                ; with the high byte of ErrorAcc)
        mov     ch,byte ptr [bp].NumLevels  ;mask used to flip all bits in an
        dec     ch              ; intensity weighting, producing
                                ; result (1 - intensity weighting)
        mov     bp,BaseColor[bp]  ;***stack frame not available***
                                ;***from now on              ***
        xchg    bp,ax           ;BP = ErrorAdj, AL = BaseColor,
                                ; AH = scratch register

; Draw all remaining pixels.
YMajorLoop:
        add     dx,bp           ;calculate error for next pixel
        jnc     NoXAdvance      ;not time to step in X yet
                                ;the error accumulator turned over,
                                ;so advance the X coord
        add     si,bx           ;add XDir to the pixel pointer
NoXAdvance:
        add     si,SCREEN_WIDTH_IN_BYTES ;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.
        mov     ah,dh           ;msb of ErrorAcc
        shr     ah,cl           ;Weighting = ErrorAcc >> IntensityShift;
        add     ah,al           ;BaseColor + Weighting
        mov     [si],ah         ;DrawPixel(X, Y, BaseColor + Weighting);
        mov     ah,dh           ;msb of ErrorAcc
        shr     ah,cl           ;Weighting = ErrorAcc >> IntensityShift;
        xor     ah,ch           ;Weighting ^ WeightingComplementMask
        add     ah,al           ;BaseColor + (Weighting ^ WeightingComplementMask)
        mov     [si+bx],ah      ;DrawPixel(X+XDir, Y,
                                ; BaseColor + (Weighting ^ WeightingComplementMask));
        dec     di              ;--DeltaY
        jnz     YMajorLoop
        jmp     Done            ;we're done with this line

; It's an X-major line.
        align2
XMajor:
; Calculate the 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.
        sub     ax,ax           ;make DeltaY 16.16 fixed-point value in DX:AX
        div     cx              ;AX = (DeltaY << 16) / Deltax. Won't overflow
                                ; because DeltaY < DeltaX
        mov     di,cx           ;DI = DeltaX (loop count)
        sub     si,SCREEN_WIDTH_IN_BYTES ;back up the start X by 1, as
                                ; explained below
        mov     dx,-1           ;initialize the line error accumulator to -1,
                                ; so that it will turn over immediately and
                                ; advance Y to the start Y. This is necessary
                                ; properly to bias error sums of 0 to mean
                                ; "advance next time" rather than "advance
                                ; this time," so that the final error sum can
                                ; never cause drawing to overrun the final Y
                                ; coordinate (works in conjunction with
                                ; truncating ErrorAdj, to make sure Y can't
                                ; overrun)
        mov     cx,8            ;CL = # of bits by which to shift
        sub     cx,[bp].IntensityBits ; ErrorAcc to get intensity level (8
                                ; instead of 16 because we work only
                                ; with the high byte of ErrorAcc)
        mov     ch,byte ptr [bp].NumLevels  ;mask used to flip all bits in an
        dec     ch              ; intensity weighting, producing
                                ; result (1 - intensity weighting)
        mov     bp,BaseColor[bp];***stack frame not available***
                                ;***from now on              ***
        xchg    bp,ax           ;BP = ErrorAdj, AL = BaseColor,
                                ; AH = scratch register
                                ; Draw all remaining pixels.
XMajorLoop:
        add     dx,bp           ;calculate error for next pixel
        jnc     NoYAdvance      ;not time to step in Y yet
                                ;the error accumulator turned over,
                                ; so advance the Y coord
        add     si,SCREEN_WIDTH_IN_BYTES ;advance Y
NoYAdvance:
        add     si,bx           ;X-major, so add XDir to the pixel pointer

; 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.
        mov     ah,dh           ;msb of ErrorAcc
        shr     ah,cl           ;Weighting = ErrorAcc >> IntensityShift;
        add     ah,al           ;BaseColor + Weighting
        mov     [si],ah         ;DrawPixel(X, Y, BaseColor + Weighting);
        mov     ah,dh           ;msb of ErrorAcc
        shr     ah,cl           ;Weighting = ErrorAcc >> IntensityShift;
        xor     ah,ch           ;Weighting ^ WeightingComplementMask
        add     ah,al           ;BaseColor + (Weighting ^ WeightingComplementMask)
        mov     [si+SCREEN_WIDTH_IN_BYTES],ah
 ;DrawPixel(X, Y+SCREEN_WIDTH_IN_BYTES,
 ; BaseColor + (Weighting ^ WeightingComplementMask));
        dec     di              ;--DeltaX
        jnz     XMajorLoop
        
Done:                           ;we're done with this line
        pop     ds              ;restore C's default data segment
        pop     di              ;restore C's register variables
        pop     si
        pop     bp              ;restore caller's stack frame
        ret                     ;done
_DrawWuLine endp
        end

Notes on Wu Antialiasing

Wu antialiasing can be applied to any curve for which it’s possible to calculate at each step the positions and intensities of two bracketing pixels, although the implementation will generally be nowhere near as efficient as it is for lines. However, Wu’s article in Computer Graphics does describe an efficient algorithm for drawing antialiased circles. Wu also describes a technique for antialiasing solids, such as filled circles and polygons. Wu’s approach biases the edges of filled objects outward. Although this is no good for adjacent polygons of the sort used in rendering, it’s certainly possible to design a more accurate polygon-antialiasing approach around Wu’s basic weighting technique. The results would not be quite so good as more sophisticated antialiasing techniques, but they would be much faster.

In general, the results obtained by Wu antialiasing are only so-so, by theoretical measures. Wu antialiasing amounts to a simple box filter placed over a fixed-point step approximation of a line, and that process introduces a good deal of deviation from the ideal. On the other hand, Wu notes that even a 10 percent error in intensity doesn’t lead to noticeable loss of image quality, and for Wu-antialiased lines up to 1K pixels in length, the error is under 10 percent. If it looks good, it is good—and it looks good.

With a 16-bit error accumulator, fixed-point inaccuracy becomes a problem for Wu-antialiased lines longer than 1K. For such lines, you should switch to using 32-bit error values, which would let you handle lines of any practical length.

In the listings, I have chosen to truncate, rather than round, the error-adjust value. This increases the intensity error of the line but guarantees that fixed-point inaccuracy won’t cause the minor axis to advance past the endpoint. Overrunning the endpoint would result in the drawing of pixels outside the line’s bounding box, and potentially even in an attempt to access pixels off the edge of the bitmap.

Finally, I should mention that, as published, Wu’s algorithm draws lines symmetrically, from both ends at once. I haven’t done this for a number of reasons, not least of which is that symmetric drawing is an inefficient way to draw lines that span banks on banked Super-VGAs. Banking aside, however, symmetric drawing is potentially faster, because it eliminates half of all calculations; in so doing, it cuts cumulative error in half, as well.

With or without symmetrical processing, Wu antialiasing beats fried, stewed chicken hands-down. Trust me on this one.


Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash