“Line generation for incremental and raster devices” by Earnshaw

The characteristics,properties and generative sequences of line generation algorithms for incremental and raster devices are summarized and the mappings from one into the other are discussed. Extensions to the basic algorithms to exploit a greater variety of possible operations in the basic hardware set of incremental devices and also to cater for various types of curve are summarized.A new method of partitioning based upon derived code sequences and code patterns is presented and is shown to lead to significant code sequence compression (more than 40%) in the majority of cases, and more importantly a significant overall reduction of between 20% and 43% in the total central processor usage. Algorithms for encoding the sequences are presented.

1. Boothroyd, J. Private Communication.
2. Boothroyd, J. and Hamilton, P. A. Exactly reversible plotter paths. Australian Computer Journal, Vol. 2, No. 1 (1970), 20-21.
3. Bresenham, J. E. Algorithm for computer control of a digital plotter. IBM Systems Journal, Vol. 4, No. 1 (1965), 25-30.
4. Dijkstra, E. W. A Discipline of Programming. Prentice-Hall, EnglewoodCliffs, 1976.
5. Earnshaw, R. A. Graph Plotting in Algol 68-R. Software-Practice and Experience, Vol. 6, No. 1 (1976), 51-60.
6. Knuth, D. E. The Art of Computer Programming-Vol. 2, SeminumericalAlgorithms, Addison Wesley Publishing Company, 1969, 293-338.
7. Pitteway, M. L. V. The impact of computer graphics. Nature, Vol. 235 (January 14, 1972), 83-85.
8. Pitteway, M. L. V. Algorithm for drawing ellipses or hyperbolae with a digital plotter. Computer Journal, Vol. 10 (1967), 282-289.
9. Stein, J. J. Comp. Phys., Vol. 1 (1967), 397-405.
10. Stockton, F. G. Algorithm 162, Comm. ACM 6, 4 (1963).
11. Thompson, J. R. Straight lines and graph plotters. Computer Journal, Vol. 4, No. 3 (1964), 227.