RFC: wideline algorithm

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 05/29/04 

Date: Fri, 28 May 2004 22:51:16 -0400 (EDT)

  This is both a request for comment and a "sources wanted"
post in one; hence the cross-post. (c.s.w gets precious
little traffic, though.)

  I have here a naive algorithm for drawing "wide lines,"
a.k.a. "fat lines," "thick lines," and probably some other
adjectives that I haven't thought to Google yet. It seems
to work, but it is not perfect: it is rather clunky, it
is not XOR-safe (it writes over some pixels more than
once per line), and it does not generalize to non-integer
line thicknesses.

  Looking for comments on this algorithm, and wanting an
algorithm (preferably with unencumbered source code in a
C-like language) that is XOR-safe and generalized.

  A compilable C program is available here:
http://www.contrib.andrew.cmu.edu/~ajo/disseminate/wideline.c
The line-drawing algorithm is as follows:

    Compute the "thin" line as per Bresenham's algorithm.
    For each computed point (x,y) on the line, perform
    the following subroutine:
        Begin computing the "stepped" line from (x,y)
        perpendicular to the original line. Compute
        LINE_THICKNESS points along this line, and then
        return to the calling routine.

    A "thin" line is defined as the line of single-pixel
    width, like this:

        ##
          ###
             ###
                ##

    A "stepped" line is defined as the line without any
    rows of pixels touching only diagonally, like this:

        ###
          ####
             ####
                ###

    We use "stepped" lines in the subroutine as a hack to
    avoid "holes" we'd otherwise get in the wide line.

Again, comments and code welcomed.

Thanks,
-Arthur