Fast line scan-conversion

ABSTRACT

A major bottleneck in many graphics displays is the time required to scan-convert straight line segments. Most manufacturers use hardware based on Bresenham's [5] line algorithm. In this paper an algorithm is developed based on the original Bresenham scan-conversion together with the symmetry first noted by Gardner [18] and a recent double-step technique [31]. This results in a speed-up of scan-conversion by a factor of approximately 4 as compared to the original Bresenham algorithm. Hardware implementations are simple and efficient since the property of using only shift and increment operations is preserved.

REFERENCES

• 1: Mike Asal , Graham Short , Tom Preston , Richard Simpson , Derek Roskell , Karl Guttag, The texas instruments 34010 graphics system processor, IEEE Computer Graphics and Applications, v.6 n.10, p.24-39, Oct. 1986 [doi>10.1109/MCG.1986.276566]
• 2: Jose Barros , Henry Fuchs, Generating smooth 2-D monocolor line drawings on video displays, Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.260-269, August 08-10, 1979, Chicago, Illinois, United States
• 3: BELZER, K. Comment on 'An improved algorithm for the generation of non-parametric curves'. IEEE Trans. Comput. C-25 (Jan. 1976), 103.
• 4: BOTOTHROYD, J., AND HAMILTON, P.A. Exactly reversible plotter paths. Australian Comput. J. 2 (1970), 20-21.
• 5: BRESENHAM, J.E. Algorithm for computer control of digital plotter. IBM Syst. J. 4 (1965), 25-30.
• 6: BRESENHAM, J.E.Incremental line compaction. Comput. J. 25 (Jan. 1982), 116-120.
• 7: BRESENHAM, J.E. Run length slice algorithms for incremental lines. In Fundamental Algorithms for Computer Graphics, R. A. Earnshaw, Ed. NATO ASI Series, Springer Verlag, New York, 1985, 59-104.
• 8: BRONS, R. Linguistic methods for the description of a straight line on a grid. Comput. Gr. Image Process. 9 (1979), 183-195.
• 9: CASTLE, C. M. A., AND PITTEWAY, M. L.V. An application of Euclid's algorithm to drawing straight lines. In Fundamenta~ Algorithms for Computer Graphics, R. A. Earnshaw, Ed. NATO ASI Series, Springer Verlag, New York, 1985, 135-139.
• 10: C. M. A. Castle , M. L. V. Pitteway, An efficient structural technique for encoding `best-fit' straight lines, The Computer Journal, v.30 n.2, p.168-175, April 1987 [doi>10.1093/comjnl/30.2.168]
• 11: DANIELSSON, PER E. Incremental curve generation. IEEE Trans. Comput. C-19 (Sept. 1970), 783-793.
• 12: DORST, L. Discrete straight line segments: Parameters, primitives and properties. Ph.D. thesis, T. H. Delft, June 1986. Offsetdmkkerij, Kanters BV, Ablasserdam, Holland.
• 13: EARNSHAW, R.A. Line tracking for incremental plotters. Comput. J. 23 (1980), 46-52.
• 14: FIUME, E.L. A mathematical semantic and theory of raster graphics. Tech. Rep. CRSI-185, Computer Systems Research Institute, Univ. of Toronto, Toronto, Canada, 1986.
• 15: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 16: FREEMAN, H. Boundary encoding and processing. In Picture Processing and Psychopictorics. B. S. Lipkin and A. Rosenfeld, Eds., Academic Press, New York 1970, 241-266.
• 17: FREEMAN, H. On the encoding of arbitrary geometric configurations. IRE Trans. EC-102 (1961), 260-268.
• 18: GARDNER, P. L. Modifications of Bresenham's algorithm for displays. IBM Tech. Disclosure Bull. 18 (1975), 1595-1596.
• 19: JORDAN, B. W., LENNON, W. J.~ AND HOLM, S.C. An improved algorithm for the generation of non-parametric curves. IEEE Trans. Comput. C-22 (Dec. 1973), 1052-1060.
• 20: MCILROY, M.D. A note on discrete representation of lines. AT&T Tech. J. 64 (Feb. 1985), 481-490.
• 21: Ernst Piller , Herbert Widner, Real-time raster scan unit with improved picture quality, ACM SIGGRAPH Computer Graphics, v.14 n.1-2, July 1980 [doi>10.1145/988442.988444]
• 22: PITTEWAY, M. Algorithm for drawing ellipses or hyperbolae with digital plotter. Comput. J. 10 (1967), 282-289.
• 23: PITTEWAY, M. Algorithms of conic generation. In Fundamental Algorithms for Computer Graphics, R. A. Earnshaw, Ed. NAT() ASI Series, Springer Verlag, New York, 1985, 219-237.
• 24: PITTEWAY, M. L. V., AND GREI~;N, A. J.R. Bresenham's algorithm with run line coding shortcut. Comput. J. 25 (1982), 114-115.
• 25: RAMOT, J. Non-parametric curves. IEEE Trans. Comput. C-25 (Jan. 1976), 103-104.
• 26: REGIORI, G.B. Digital computer transformations for irregular line drawings. Tech. Rep. 403- 22, Department of Electrical Engineering and Computer Science. New York Univ., Apr. 1972.
• 27: RUBIN, F. Generation of non-parametric curves. IEEE Trans. Comput. C-25 (Jan. 1976), 103.
• 28: 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]
• 29: SUENAGA, Y., KAMAE, T., AND KOBAYASHI, T. A high-speed algorithm for the generation of straight lines and circular arcs. 1EEE Trans. Comput. C-28 (1979), 728-736.
• 30: THOMPSON, J.R. Straight lines and graph plotters. Comput. J. 7 (1964), 227.
• 31: Xiaolin Wu , Jon G. Rokne, Double-step incremental generation of lines and circles, Computer Vision, Graphics, and Image Processing, v.37 n.3, p.331-344, March 1987 [doi>10.1016/0734-189X(87)90041-7]
• 32: Xiaolin Wu , Jon G. Rokne, Double-Step Generation of Ellipses, IEEE Computer Graphics and Applications, v.9 n.3, p.56-69, May 1989 [doi>10.1109/38.28111]
• 33: X. Wu , J. Rokne, On Properties of Discretized Convex Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.217-223, February 1989 [doi>10.1109/34.16719]

INDEX TERMS

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

General Terms:
Algorithms, Design