The circle-brush algorithm

ABSTRACT

Brushing commonly refers to the drawing of curves with various line widths in hit-mapped graphics systems. It is best done with circles of suitable diameter so that a constant line width, independent of the curve's slope, is obtained. Allowing all possible integer diameters corresponding to all possible integer line widths results in every second width having an odd value. Thus, the underlying circle algorithm must be able to handle both integer and half-integer radii. Our circle-brush algorithm handles both situations and produces a “best approximation”: All grid points produced simultaneously minimize (1) the residual, (2) the Euclidean distance to the circle, and (3) the displacement along the grid line from the intersection with the circle. Our circle-brush algorithm was developed in careful consideration of its implementation in VLSI.

REFERENCES

• 1: AMERICAN NATIONAL STANDARDS INSTITUTE. Graphical kernel system--GKS. ANSI Standard X3.124-1985, ANSI, New York, Oct. 1985.
• 2: BRESENHAM, J.E. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1 (1965), 25-30.
• 3: 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]
• 4: CHAIKIN, G.M. An algorithm for high-speed curve generation. Comput. Graph. Image Process. 3 (1979), 346-349.
• 5: Michael R. Dunlavey, Efficient polygon-filling algorithms for raster displays, ACM Transactions on Graphics (TOG), v.2 n.4, p.264-273, October 1983 [doi>10.1145/245.248]
• 6: Lance A. Glasser , Daniel W. Dobberpuhl, The design and analysis of VLSI circuits, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 7: HORN, B. K.P. Circle generators for display devices. Comput. Graph. Image Process. 5, 2 (June 1976), 280-288.
• 8: INTERNATIONAL STANDARDIZATION ORGANIZATION. Information processing--Computer graphics--Graphical kernel system (GKS)--Functional description. ISO IS 7942, ISO, Geneva, Switzerland, Aug. 1985.
• 9: MAXWELL, P. C., AND BAKER, P.W. The generation of polygons representing circles, ellipses and hyperbolas. Comput. Graph. Image Process. 10 (May 1979), 84-93.
• 10: 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]
• 11: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 12: PITTEWAY, M. L.V. Algorithm for drawing ellipses or hyperbolae with a digital plotter. Comput. J. 10, 3 (Nov. 1967), 282-289.
• 13: SUENAGA, Y., KAMAE, T., &ND KOBAYASHI, T. A high-speed algorithm for the generation of straight lines and circular arcs. IEEE Trans. Comput. C-28 (Oct. 1979), 728-736.
• 14: 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 [doi>10.1145/282918.282943]
• 15: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Raster display devices

General Terms:
Algorithms, Design, Performance