Incremental linear interpolation

2 January 1985

journal article
Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics

Vol. 4 (1) , 1-11
https://doi.org/10.1145/3973.3976

Abstract

Two incremental linear interpolation algorithms are derived and analyzed for speed and accuracy. The first is a version of a “simple” digital differential analyzer (DDA) employing fixed-point arithmetic, whereas the second is a new algorithm that uses only integral arithmetic and is a generalization of Bresenham's line-drawing algorithm. The new algorithm is shown to achieve perfect accuracy and, depending on the underlying processor, may be faster than the fixed-point algorithm.

Keywords

ADDITIONAL KEY WORDS AND PHRASES: BRESENHAM'S ALGORITHM
PERFECT ACCURACY
INTEGRAL ARITHMETIC
SCAN CONVERSION
FIXED-POINT ARITHMETIC
LINE-DRAWING ALGORITHM
FIXED-POINT ALGORITHM
DIGITAL DIFFERENTIAL ANALYZER
NEW ALGORITHM
UNDERLYING PROCESSOR
INCREMENTAL LINEAR INTERPOLATION ALGORITHM

This publication has 3 references indexed in Scilit:

Using program transformations to derive line-drawing algorithms
ACM Transactions on Graphics, 1982
Editorial
The Computer Journal, 1982
Illumination for computer generated pictures
Communications of the ACM, 1975