Curve-drawing algorithms for Raster displays
- 1 April 1985
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 4 (2), 147-169
- https://doi.org/10.1145/282918.282943
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.Keywords
This publication has 8 references indexed in Scilit:
- Best approximate circles on integer gridsACM Transactions on Graphics, 1983
- Using program transformations to derive line-drawing algorithmsACM Transactions on Graphics, 1982
- A linear algorithm for incremental digital display of circular arcsCommunications of the ACM, 1977
- Circle generators for display devicesComputer Graphics and Image Processing, 1976
- An Improved Algorithm for the Generation of Nonparametric CurvesIEEE Transactions on Computers, 1973
- Incremental Curve GenerationIEEE Transactions on Computers, 1970
- Algorithm for drawing ellipses or hyperbolae with a digital plotterThe Computer Journal, 1967
- Algorithm for computer control of a digital plotterIBM Systems Journal, 1965