Incremental linear interpolation

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.

REFERENCES

• 1: BRESENHAM, J.E. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1 (1965), 25-30.
• 2: BRESENHAM, J.E. Incremental line compaction. Comput. j. 25, 1 (Feb. 1982), 116-120.
• 3: GOURARD, H. Continuous shading of curved surfaces. IEEE Trans. Comput. C-20, 6 (June 1971), 623-629.
• 4: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 5: Bui Tuong Phong, Illumination for computer generated pictures, Communications of the ACM, v.18 n.6, p.311-317, June 1975 [doi>10.1145/360825.360839]
• 6: SIZER, T.R.H. The Digital Dif{erential Analyser. Chapman and Hall Ltd., London. 1968.
• 7: R. F. Sproull, Using program transformations to derive line-drawing algorithms, ACM Transactions on Graphics (TOG), v.1 n.4, p.259-273, Oct. 1982 [doi>10.1145/357311.357312]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

General Terms:
Algorithms