Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!apple!sun-barr!newstop!texsun!convex!forsythe@convex.com
From: forsythe@convex.com (Charles Forsythe)
Newsgroups: comp.graphics
Subject: Re: Multi-width Brezenham lines
Keywords: Brezenham, line, vector, walk
Message-ID: <2414@convex.UUCP>
Date: 26 Oct 89 08:07:02 GMT
References: <4162@deimos.cis.ksu.edu> <19697@versatc.versatec.COM>
Sender: usenet@convex.UUCP
Lines: 44

>> I'm looking for references/ideas for implementing a variable-width
>> version of Bresenham's algorithm for quantising line segments.

This is kind of a weird question because the Bresenham line algorithm doesn't
really consider the "width" of the line.  Conceptually, it is providing the
nearest quantized coordinates to a zero-width line.  (Sorry to pick nits but:)
What you want is an incremental algorithm, but I don't think it will be
related in any other meaningful way to the Bresenham method.

Jack Ritter hit on one of the problems with trying to apply Bresenham thinking
to lines with width:

>The problem is, the eye is VERY GOOD at detecting
>different effective widths. Consider the following
>two lines of width 3:
>
>***             ***
> ***               ***
>  ***      &         ***
>   ***                  ***
>    ***                   ***

What you really want to do if you want lines that maintain width
despite orientation is to implement an incremental area fill.  You need
to stop thinking of the pixels as points and think of them as
rectangles of unit area (which is what they are).  Implement an algorithm
that traces 4 lines: 2 parallel to the original line and the width apart.
The other two are orthoganal and "cap off" the rectangle.  Turn on all
pixels that lie 50% or more inside this shape.  It's pretty easy to do this
quickly.  This does have problems when the width of the line is less than
one pixel, so you may want to have a Bresenham line-drawer to draw lines
of width < 1;  if you don't, the lines will devolop gaps.  This may be
OK if you're zooming down an image; the gaps will provide automagic dithering
and preserve (to a point) the "color" (dark/light density) of the image.

I've used this approach before and it works very well on preserving width (and
other shape attributes) regardless of orientation etc.

Hope this helps,
	-Charles
"Let him that hath understanding count the number the beast"
		-Revelations 13:18
forsythe@convex.com
#### This has nothing to do with Convex Computer Corporation -- obviously ####