RFC: wideline algorithm

[Arthur J. O'Dwyer]

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

[Ian Woods]

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote in
news:Pine.LNX.4.58-035.0405282235460.14092@unix49.andrew.cmu.edu:
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.)

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

<anip>
Again, comments and code welcomed. Thanks, -Arthur

Have you considered using the principal of 'nearest sample' (as used in
Bresenhams line algorithm)? Instead of using an infinitely thin line and
lighting whichever samples have centers closest to the line, you'd use a
thin filled rectangle instead.

It's been many years since I did any 2D graphics, but this certainly
sticks out in my memory as something I've seen before.

Ian Woods

--
"I'm a paranoid schizophrenic sado-masochist.
My other half's out to get me and I can't wait."
Richard Heathfield

[Ben Pfaff]

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> writes:
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.

Have you considered using an algorithm for drawing convex
polygons? A thick line is just a rectangle whose edges are not
necessarily parallel to the x and y axes, so polygon algorithms
are entirely appropriate.
--
"To prepare for the writing of Software,
the writer must first become one with it,
sometimes two."
--W. C. Carlson

[Gerry Quinn]

In article <Pine.LNX.4.58-035.0405282235460.14092
@unix49.andrew.cmu.edu>, ajo@nospam.andrew.cmu.edu says... 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.

If you want non-integral line width, I think you should draw anti-
aliased polygons.

For an integer-efficient line, albeit with minor end artifacts, you
could adapt Bresenham's algorithm. Distinguish between cases where the
angle is greater than or equal to 45 degrees away from the x-axis, and
others.

If the line is less than 45 degrees from the x-axis, draw a vertical
column of pixels centred on every Bresenham point (obviously you must
compromise slightly if you have an even width). If the line is angled
at 45 degrees or more, draw a horizontal row.

This is easy, quick (for smallish line widths) and XOR-safe, so long as
you go the same direction all the time, as with Bresenham's. The end
points will be a bit angular, but maybe you could find a way to fix this
if necessary. For example, cut off excess bits and draw a disk.
Another defect is that the true width of the line increases as you
approach the horizontal and vertical. You could adjust your row or
column length to correct for this to the nearest integer.

Come to think of it, you could adapt this to do antialiasing quite
efficiently too, although I'm not sure how well this would work with
XOR.

- Gerry Quinn