A linear algorithm for incremental digital display of circular arcs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A linear algorithm for incremental digital display of circular arcs

Full text

Pdf (562 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 2 (February 1977) table of contents

Pages: 100 - 106

Year of Publication: 1977

ISSN:0001-0782

Author

Jack Bresenham

IBM System Communications Divison, White Plains, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 144, Citation Count: 32

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359423.359432 What is a DOI?

ABSTRACT

Circular arcs can be drawn on an incremental display device such as a cathode ray tube, digital plotter, or matrix printer using only sign testing and elementary addition and subtraction. This paper describes methodology for producing dot or step patterns closest to the true circle.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bresenham, J.E. An incremental algorithm for digital plotting. Presented at ACM Nat. Conf. (Aug. 1963).
	2	Bresenham, J.E. Algorithm for computer control of a digital plotter. IBMSystems J. 4, 1 (1965), 25-30.
	3	Bresenham, J.E. A linear, incremental algorithm for digitally plotting circles. Tech. Rep. No. TR02.286, IBM General Products Div., San Jose, Calif. Jan 27, 1964.
	4	Cohen, D. On linear difference curves. Proc. Int. Symp. CG- 70, Vol. I, Brunel U. Uxbridge, England, April 1970.
	5	Cohen, D. Incremental methods for computer graphics. Tech. Rep. ESD-TR69-193 Harvard U., Cambridge, Mass., April 1969.
	6	Danielsen, P.E. Incremental curve generation. IEEE Trans. Computers C-19, 9 (Sept. 1970), 783-793.
	7	Denert, E. A method for computing points on a circle using only integers. Comptr. Graphics and Image Processing 2, 1 (Aug. 1973), 83-91.
	8	Jordan, B.W., Lennon, W.J., and Holm, B.C. An improved algorithm for the generation of nonparametric curves. IEEE Trans. Computers C-22, 12 (Dec. 1973), 1052-1060.
	9	Metzger, R.A. Computer generated graphic segments in a raster display. Proc. AFIPS 1969 SJCC, AFIPS Press, Montvale, N.J., pp. 161-172.
	10	Pitteway, M.L.V. Algorithm for drawing ellipses or hyperbolae with a digital plotter. Comptr. J. 10, 3 (Nov. 1967), 282-289.
	11	Pitteway, M.L.V. Integer circles, etc.--three move extension of Bresenham's algorithm. Comptr. Graphics and Image Processing 3, 3 (Sept. 1974), 260-261.
	12	Pitteway, M.L.V. Integer circles--some further thoughts. Compt. Graphics and Image Processing 3, 3 (Sept. 1974), 262-265.

CITED BY 32

	Roger D. Hersch, Character generation under grid constraints, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.243-252, July 1987
	Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985
	Chengfu Yao , Jon G. Rokne, Hybrid Scan-Conversion of Circles, IEEE Transactions on Visualization and Computer Graphics, v.1 n.4, p.311-318, December 1995
	Ronald Baecker , David Miller , William Reeves, Towards a laboratory instrument for motion analysis, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.191-197, August 1981
	Nelson L. Max, ATOMLLL: ATOMS with shading and highlights, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.165-173, August 1979
	John E. Rager, Graphics packages for teaching graphics, ACM SIGCSE Bulletin, v.18 n.1, p.225-231, February 1986
	Xiaolin Wu, An efficient antialiasing technique, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.143-152, July 1991
	Arie Kaufman , Eyal Shimony, 3D scan-conversion algorithms for voxel-based graphics, Proceedings of the 1986 workshop on Interactive 3D graphics, p.45-75, January 1987, Chapel Hill, North Carolina, United States
	Colin J. Prosser , Alistair C. Kilgour, An Integer Method for the Graphical Output of Conic Sections, ACM Transactions on Graphics (TOG), v.2 n.3, p.182-191, July 1983
	K. C. Posch , W. D. Fellner, The circle-brush algorithm, ACM Transactions on Graphics (TOG), v.8 n.1, p.1-24, Jan. 1989
	Gautam B. Singh, GRIP: graphics reduced instruction processor, Proceedings of the 24th annual international symposium on Microarchitecture, p.143-152, September 1991, Albuquerque, New Mexico, Puerto Rico
	Eric Andres , Marie-Andrée Jacob, The Discrete Analytical Hyperspheres, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.75-86, January 1997
	William E. Wright, Rendering: Parallelization of Bresenham's Line and Circle Algorithms, IEEE Computer Graphics and Applications, v.10 n.5, p.60-67, September 1990
	Tony Barrera , Anders Hast , Ewert Bengtsson, A fast all-integer ellipse discretization algorithm, Graphics programming methods, Charles River Media, Inc., Rockland, MA, 2003
	Richard E. Chandler, A Tracking Algorithm for Implicitly Defined Curves, IEEE Computer Graphics and Applications, v.8 n.2, p.83-89, March 1988
	Michael B. Gousie , Wm. Randolph Franklin, Constructing a dem from grid-based data by computing intermediate contours, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.71-77, November 07-08, 2003, New Orleans, Louisiana, USA
	M. D. McIlroy, Best approximate circles on integer grids, ACM Transactions on Graphics (TOG), v.2 n.4, p.237-263, October 1983
	M. Douglas McIlroy, Getting raster ellipses right, ACM Transactions on Graphics (TOG), v.11 n.3, p.259-275, July 1992
	Pierre Soille , Edmond J. Breen , Ronald Jones, Recursive Implementation of Erosions and Dilations Along Discrete Lines at Arbitrary Angles, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.5, p.562-567, May 1996
	R. Lin , S. Olariu , J. L. Schwing , B.-F. Wang, The Mesh with Hybrid Buses: An Efficient Parallel Architecture for Digital Geometry, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.266-280, March 1999
	Benedek Nagy, Characterization of digital circles in triangular grid, Pattern Recognition Letters, v.25 n.11, p.1231-1242, August 2004
	Jianhua Huang , Ebad Banissi, An Improved Parallel Circle-Drawing Algorithm, IEEE Computer Graphics and Applications, v.17 n.1, p.40-41, January 1997
	Ian Galton, Arcs: An Efficient Three-Point Arc Algorithm, IEEE Computer Graphics and Applications, v.9 n.6, p.44-49, November 1989
	Songhua Xu , Francis C. M. Lau , William K. Cheung , Yunhe Pan, Automatic Generation of Artistic Chinese Calligraphy, IEEE Intelligent Systems, v.20 n.3, p.32-39, May 2005
	Ernst Piller , Herbert Widner, Real-time raster scan unit with improved picture quality, ACM SIGGRAPH Computer Graphics, v.14 n.1-2, July 1980
	Thomas K. Porter, Spherical shading, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.282-285, August 1978
	Partha Bhowmick , Bhargab B. Bhattacharya, Number-theoretic interpretation and construction of a digital circle, Discrete Applied Mathematics, v.156 n.12, p.2381-2399, June, 2008
	Fabrice Mairesse , Tadeusz Sliwa , Stéphane Binczak , Yvon Voisin, Subpixel determination of imperfect circles characteristics, Pattern Recognition, v.41 n.1, p.250-271, January, 2008
	Weibin Sun , Xubo Yang , Shuangjiu Xiao , Wencong Hu, Robust checkerboard recognition for efficient nonplanar geometry registration in projector-camera systems, Proceedings of the 5th ACM/IEEE International Workshop on Projector camera systems, August 10-10, 2008, Marina del Rey, California
	Christopher Stuetzle , W. Randolph Franklin , Barbara Cutler, Evaluating hydrology preservation of simplified terrain representations, SIGSPATIAL Special, v.1 n.1, p.51-56, March 2009
	Antoine Vacavant , David Coeurjolly , Laure Tougne, A framework for dynamic implicit curve approximation by an irregular discrete approach, Graphical Models, v.71 n.3, p.113-124, May, 2009
	Partha Bhowmick , Bhargab B. Bhattacharya, Real Polygonal Covers of Digital Discs - Some Theories and Experiments, Fundamenta Informaticae, v.91 n.3-4, p.487-505, August 2009

INDEX TERMS

Keywords:
circle algorithm, circle drawing, dot generation, graphics, incremental digital plotting, integer arithmetic, raster display, step generation

Adobe Acrobat

QuickTime

Windows Media Player

Real Player