From albanycs!leah:rsb584 Fri Jan 29 02:16:08 1988
Received: by albanycs.albany.edu (5.54/4.8)
	id AA00170; Thu, 28 Jan 88 12:23:50 EST
Date: Thu, 28 Jan 88 12:23:47 EST
From: albanycs!leah:rsb584 (Raymond S Brand)
Received: by leah.Albany.EDU (5.58/1.1)
	id AA07708; Thu, 28 Jan 88 12:23:47 EST
Message-Id: <8801281723.AA07708@leah.Albany.EDU>
To: albanycs:beowulf!rsbx

>From kent@xanth.UUCP Mon Jan 25 12:26:30 1988
Path: leah!itsgw!nysernic!rutgers!cmcl2!brl-adm!umd5!uvaarpa!mcnc!xanth!kent
From: kent@xanth.cs.odu.edu (Kent Paul Dolan)
Newsgroups: comp.graphics
Subject: Re: thick lines, circles and ellipses
Summary: A bit of history on a way that worked well
Keywords: computer graphics, circles, ellipses, algorithms
Message-ID: <3747@xanth.cs.odu.edu>
Date: 25 Jan 88 17:26:30 GMT
References: <694@prefix.liu.se> <16183@watmath.waterloo.edu> <696@portofix.liu.se> <471@ecrcvax.UUCP>
Reply-To: kent@xanth.UUCP (Kent Paul Dolan)
Organization: Old Dominion University, Norfolk Va.
Lines: 69


In article <471@ecrcvax.UUCP> johng@ecrcvax.UUCP (John Gregor) writes:
>In article <696@portofix.liu.se> kjepo@portofix.liu.se (Kjell Post) writes:
>>Why not use a thicker pencil?
>>
>>What I'm saying is that you can print a larger dot instead of just a pixel.
>>This is the method used by ditroff where they draw lines, arcs and b-splines
>>with the '.' character. By altering the fontsize you get different line widths.
>
>That may be fine for output to a laser printer, but it is extremely inefficient
>for any sort of interactive graphics.  Here is an example:
>
>Assume your big dot is:         ##
>				####
>Also assuming square pixels    ####
>				 ##
>
>Then drawing a line (slope == 1) would look like:
>
>             11
>            2211
>           23221
>	   23232       The numbers correspond to the number of times the 
>	  12232        pixel is written.
>	  1122
>	   11
>
>Even though there is a fix for lines, this scheme is completely impractical
>for curves.  I recommend scan converting the polygon.
>
>				John Gregor
>                      johng%ecrcvax.UUCP@germany.CSNET


Uh...completely impractical it is not.  Just break the curve down into
reasonable sized line segments, and store precalculated sausages for
each possible orientation at each desired size, and merge them to make
the final curve.

I did this for offsets -7 to +7 in x and y, line thicknesses 1 to 100,
for the Department of Commerce's National Ocean Survey about 12 years
ago.  The resulting object code porked out (in FORTRAN IV on an IBM
360/195) at about .75 MegaByte with the table stored in the
executable, but the CPU usage fee savings over calculating the dots on
the fly amounted to ~$1M/year.

Of course the application was a bit abusive of normal thinking: 2000
documents per year, 7 color separations per document, sizes to 42" x
60" (E sized drawings) and resolution of 800 dpi in x and y, with
typically 20M black pixels per separation (we still did halftone
screens by hand from solid plots), but a megabuck saved per year in
computer costs wasn't to be sneezed at.

Yes, it took a pair of BIG disk packs to sort the pixels before run
length coding them onto tape for the laser onto film raster plotter,
but you should have seen the code the vendor sold us before I did this
fix!  It scan converted the curves from first principles.  Ugh!  Took
a dozen times as long to run.

We used the National Weather Services computers, and even though the
weather forcasts occassionally ran a bit late, our nautical charts
were beautiful, because the round ended sausages prevented gaps in the
lines as they turned around curves or corners.

Don't give up on this approach until you check it out carefully.
These days, I could probably do the computation at home on my Amiga
without too much trouble.

Kent, the man from xanth.