Using Program Transformations to Derive Line-Drawing Algorithms

摘要

A wide variety of line-drawing algorithms can be derived by applying program transformations to a simple, obviously correct algorithm. The transformations increase the algorithm's performance and eliminate the need for floating-point computations. Two familiar algorithms are derived in this way: Bresenham's algorithm and the digital differential analyzer (DDA). The transformations are then used to derive several highly parallel 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. Moreover, the transformations derive Bresenham's algorithm without recourse to complex geometric arguments. (Author)