Using program transformations to derive line-drawing algorithms
Robert F. Sproull · ACM Transactions on Graphics · 1982
DeriveA wide variety of line-drawing algorithms can be derived by applying program transformations to a simple, obviously correct algorithm.The transformations increase the speed of the algorithm and eliminate the need for floating-point computations.We show how Bresenham's algorithm can be derived in this way.The transformations are then used to derive several variants of Bresenham's algorithm, designed for use on displays that can generate more than one pixel at a time.The treatment shows a complete, extended example of the practical use of program transformations.
Cited by 61 works. doi:10.1145/357311.357312 Open-access PDF
Authors
References
- Principles of Compiler Design
- Structured Programming with go to Statements
- Algorithm for computer control of a digital plotter
- Alto: A personal computer
- Principles of Compiler Design (Addison-Wesley series in computer science and information processing)
- A system which automatically improves programs
- Writing Efficient Programs
- Algorithms minimizing mean flow time: schedule-length properties
- Digital Computer Transformations for Irregular Line Drawings
- Incremental Line Compaction