Using Program Transformations to Derive Line-Drawing Algorithms

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1981
Accession Number
ADA104873

Entities

People

  • Robert F. Sproull

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Analytic Geometry
  • Analyzers
  • Arithmetic
  • Character Generators
  • Computations
  • Computer Graphics
  • Computer Programming
  • Computers
  • Design Criteria
  • Differential Analyzers
  • Geometry
  • Interactive Graphics
  • Iterations
  • Personality
  • Programming Languages
  • Simulations

Fields of Study

  • Engineering

Readers

  • Calculus or Mathematical Analysis
  • Computer Engineering
  • Parallel and Distributed Computing.