“Generating smooth 2-D monocolor line drawings on video displays” by Barros and Fuchs

One of the major drawbacks of video display systems for line drawing applications has been the poor image quality they usually produce—“jaggy”, “staircased” line edges, moire patterns in regions of closely spaced lines, even, with some systems, lines disappearing (“falling in”) between pixels. Correcting these effects, with appropriate area-sampling techniques, has generally been too computationally expensive to adopt. A new algorithm is presented which generates precise, smooth images of line drawings and solid polygonal-shaped objects on multi-grey-level pixel-mapped video systems. The method is based on an analysis of boundary conditions at each pixel affected by one or more lines. With this method a number of previously needed steps can be quickly eliminated. The commonality of boundary conditions between adjacent pixels and the coherence of such conditions in a raster-scan ordering of such pixels allows efficient generation of these boundary conditions. A recursive subdivision approach allows handling of arbitrarily complex cases by a simple boundary-analyzing technique. Compared with current line-drawing systems, a video system with this algorithm would also display an improved image with respect to certain common visual effects—e.g., distance modulation of line intensity (which may be desirable), artificial small bright clusters of detail (which is undesirable). Since the software interface to the algorithm may be handled through already-standard graphical subroutines, adoption of the algorithm may be accomplished without burdening graphic system users or graphic system-utilizing software.

1. Catmull, E.(1978), “A Hidden-Surface Algorithm with Anti-Aliasing” Proceedings of 1978 ACM-SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques, (Vol. 12, (3):6-11, Computer Graphics)
2. Crow, F.C.(1977), “The Aliasing Problem in Computer-Generated shaded Images”, Communications of the ACM, 20 (11):799-805
3. Crow, F.C.(1978), “The Use of Grayscale for Improved Raster Display of Vectors and Characters”, Proceedings of 1978 ACM-SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques, (Vol. 12, (3):1-5, Computer Graphics)
4. Genisco Computers(1977) GCT3/GCT3a Programming Reference Manual, Irvine, California
5. Newman, W.M. & Sproull, R.F.(1973), Principles of Interactive Computer Graphics, McGraw-Hill
6. Shoup, Richard G. (1973), “Some Quantization Effects in Digitally Generated Pictures”, Digest of Technical Papers of 1973 International Symposium of the Society for Information Display, 58-59.
7. Sutherland, I.E. (1973), “Polygon Sorting by Subdivision: A Solution to the Hidden-Surface Problem”, unpublished
8. Sutherland, I.E., Sproull, R.F. & Schumacker, R.G.(1974), “A Characterization of Ten Hidden-Surface Algorithms”, Computing Surveys, 6, 1