Curve-drawing algorithms for Raster displays

ABSTRACT

The midpoint method for deriving efficient scan-conversion algorithms to draw geometric curves on raster displays in described. The method is general and is used to transform the nonparametric equation f(x,y) = 0, which describes the curve, into an algorithms that draws the curve. Floating point arithmetic and time-consuming operations such as multiplies are avoided. The maximum error of the digital approximation produced by the algorithm is one-half the distance between two adjacent pixels on the display grid. The midpoint method is compared with the two-point method used by Bresenham, and is seen to be more accurate (in terms of the linear error) in the general case, without increasing the amount of computation required. The use of the midpoint method is illustrated with examples of lines, circles, and ellipses. The considerzations involved in using the method to derive algorithms for drawing more general classes of curves are discussed.

REFERENCES

• 1: BRESENHAM, J.E. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1 (1965), 25-30.
• 2: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 3: DANIELSSON, P.E. Incremental curve generation. IEEE Trans. Comput. C-19 (1970), 783-793.
• 4: DE Roo, J., WAMBACQ, P., VAN E~CKEN, L., OOSTERLINCK, A., AND VAN DEN BERGHE, H. A hardware implemented universal graphics generator. In Proceedings of the Conference on Pattern Recognition and Image Processing (Dallas, Tex., Aug. 3-5), IEEE, New York, 1981, pp. 300-305.
• 5: HORN, B. K.P. Circle generators for display devices. Comput. Graph. Image Process. 5 (1976) 280-288.
• 6: JORDAN, B. W., LENNON, W. J., AND HOLM, B.C. An improved algorithm for the generation of nonparametric curves. IEEE Trans. Comput. C-22, 12 (Dec. 1973), 1052-1060.
• 7: M. D. McIlroy, Best approximate circles on integer grids, ACM Transactions on Graphics (TOG), v.2 n.4, p.237-263, October 1983 [doi>10.1145/245.246]
• 8: PITTEWAY, M. Algorithm for drawing ellipses or hyperbolae with a digital plotter. Comput. J. 10, 3 (Nov. 1967), 282-289.
• 9: R. F. Sproull, Using program transformations to derive line-drawing algorithms, ACM Transactions on Graphics (TOG), v.1 n.4, p.259-273, Oct. 1982 [doi>10.1145/357311.357312]
• 10: SUENAGA, Y., KAMAE, W., AND KOBAYASHI, W. A high-speed algorithm for the generation of straight lines and circular arcs. IEEE Trans. Comput. C-28, 10 {Oct. 1979), 728-736.
• 11: VAN AKEN, J. An efficient ellipse-drawing algorithm. IEEE Comput. Graph. & Appl. 4, 9 (Sept. 1984), 24-35.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms

Keywords:
curver representations, display algorithms