Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!usc!apple!voder!pyramid!versatc.versatec.COM!ritter From: ritter@versatc.versatec.COM (Jack Ritter) Newsgroups: comp.graphics Subject: Re: Multi-width Brezenham lines Keywords: Brezenham, line, vector, walk Message-ID: <19697@versatc.versatec.COM> Date: 24 Oct 89 17:58:28 GMT References: <4162@deimos.cis.ksu.edu> Organization: Versatec, Santa Clara, Ca. 95051 Lines: 65 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 --( / __ - .. (( / / / -- ) . \ \ // . ( / ** ) // _*_ // * .. ) (( . \ / . * ) //