ritter@versatc.versatec.COM (Jack Ritter) (10/25/89)
In article <4162@deimos.cis.ksu.edu>, neil@calvin.ksu.ksu.edu (Neil Erdwien) writes: > I'm looking for references/ideas for implementing a variable-width > version of Bresenham's algorithm for quantising line segments. > -- (Have to resend, 1st time it screwed up). A simple solution, as already suggested by someone, is to do the Brez. walk, and simply replicate N pixels each step, for width N lines. The problem is, the eye is VERY GOOD at detecting different effective widths. Consider the following two lines of width 3: *** *** *** *** *** & *** *** *** *** *** They will look very different to the eye. For small N, I would recommend a table, describing how to step, for a variety of angles & widths. A step description should be more than just "do 3 pixels". It should be a more complex sequence like, "do 3,4,4, [repeat]". You'll have to experiment. You only need to do angles for one octant. If you connect lines end to end (as in text), you must position the lines consistently; a line that is an EVEN number of pixels wide cannot be exactly centered. You must chose one of the 2 possibilities (plus, or minus, the half pixel). This scheme must be consistent for ALL DIRECTIONS. Note that you arent really drawing thin rectangles, but rather thin parellograms. For large N, the eye will notice. For these cases, you must do a Brezenham walk of half a width from the end point, in a direction perpendicular to the line's direction, to find the 2 corners of the rectangle. You then fracture the rectangle into an upper triangle, a middle parellelogram, and a bottom triangle. Each of these pieces is then drawn by doing 2 simultaneous Brez. walks down its left & right edges, and filling the pixels in between. This is the fastest way. An alternative to fracturing is to walk along the end segment, drawing N single width, parallel lines. This may cause holes to appear ("stitching"). To avoid holes, draw the CORNER PIXEL whenever you step diagonally. None of this is elegant, unfortunately. It's a messy problem. -- Versatec, Inc. Jack Ritter, M.S. 1-7 2710 Walsh Ave. P.O. Box 58091 Santa Clara, CA 95052-8091 (408)982-4332, or (408)988-2800 X 5743 UUCP: {ames,apple,sun,pyramid}!versatc!ritter --( / __ - .. (( / / / -- ) . \ \ // . ( / ** ) // _*_ // * .. ) (( . \ / . * ) //
forsythe@convex.com (Charles Forsythe) (10/26/89)
>> 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 ####
flip@pixar.uucp (Flip Phillips) (10/26/89)
In article <19697@versatc.versatec.COM> ritter@versatc.versatec.COM (Jack Ritter) writes: :In article <4162@deimos.cis.ksu.edu>, neil@calvin.ksu.ksu.edu (Neil Erdwien) writes: :> I'm looking for references/ideas for implementing a variable-width :> version of Bresenham's algorithm for quantising line segments. :> -- [...] well, if you want to do it "right" one approach is the following, generate the bresenham points on the line, use them as centers for drawing properly filtered disks (circles) at each point. depending on the filter you can have a variety of line types, from a soft, felt-tipped pen look, to a hard edged thing... we here at pixar are big fans of properly filtering things... Flip Phillips {sun | ucbvax}!pixar!flip Pixar - Marin County, California "Below the light, in the black lake, the mad smelts run. The wet net waits. Be careful little smelts."