“Rendering cubic curves and surfaces with integer adaptive forward differencing” by Chang, Rocchetti and Shantz

For most compute environments, adaptive forward differencing is much more efficient when performed using integer arithmetic than when using floating point. Previously low precision integer methods suffered from serious precision problems due to the error accumulation inherent to forward differencing techniques. This paper proposes several different techniques for implementing adaptive forward differencing using integer arithmetic, and provides an error analysis of forward differencing which is useful as a guide for integer AFD implementation. The proposed technique using 32 bit integer values is capable of rendering curves having more than 4K forward steps with an accumulated error of less than one pixel and no overflow problems. A hybrid algorithm employing integer AFD is proposed for rendering antialiased, texture-mapped bicubic surfaces.

1. Salim Abi-Ezzi, ‘~The Graphical Processing of NURB Surfaces,” Industrial Associate Review Summary, November 1988. Rensselaer Design Research Center, Rensselaer Polytechnic Institute
2. Jerry Van Aken and Mark Novak, “Curve-Drawing Algorithms for Raster Displays,” ACM Transactions on Graphics, vol. 4, no. 2, pp. 147-169, April 1985.
3. Richard Barrels, John Beatty, and Brian Barsky, An Introduction to Splines for use in Computer Graphics & Geometric Modeling, pp. 400-406, Morgan Kaufmann Publishers, 1987.
4. Edwin Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, Thesis in Computer Science, of Utah, UTEC-CSc-74-133, 1974.
5. George M. Chaikin, “An Algorithm for High Speed Curve Generation,” Computer Graphics and Image Processing, vol. 3, pp. 346-349, 1974.
6. Robert Cook, Patch Work, Tech. Memo 118, Computer Div., Lucasfilm Ltd., June 1985.
7. Robert Cook, Loren Carpenter, and Edwin Catmull, “The Reyes Image Rendering Architecture,” Proceedings of SIGGRAPH ’87, Computer Graphics, vol. 21, 1987.
8. James Foley and Andries Van Dam, “Fundamentals of Interactive Computer Graphics,” Addison-Wesley Publishers, p. 533, 1982.
9. Victor Klassen, “Drawing Antialiased Cubic Spline Curves Using Adaptive Forward Differencing,” ACM Transactions on Graphics, under revision, 1989.
10. Victor Klassen, “Integer Forward Differencing of Cubic Polynomials: Analysis and Algorithms,” ACM Transactions on Graphics, under revision, 1989.
11. Jeffrey M. Lane and Richard F. Riesenfeld, “A Theoretical Development for the Computer Generation of Piecewise Polynomial Surfaces,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-2, pp. 35-46, 1980.
12. Sheue-Ling Lien, Michael Shantz, and Vaughan Pratt, “Adaptive Forward Differencing for Rendering Curves and Surfaces,” Proceedings of SIGGRAPH ’87, Computer Graphics, vol. 21, 1987.
13. M.L.V. Pitteway, “Algorithm for drawing ellipses or hyperbolae with a digital plotter,” Computer Journal, vol. 10, no. 3, pp. 282-289, Nov. 1967.
14. Vaughan Pratt, “Techniques for Conic Splines,” Proceedings of SIGGRAPH ’87, Computer Graphics, vol. 19, 1985.
15. Alyn Rockwood, A Generalized Scanning Technique for Display of Parametrically Defined Surfaces, 7, IEEE Computer Graphics and Applications, August 1987.
16. Michael Shantz and Sheue-Ling Lien, “Shading Bicubic Patches,” Proceedings of SIGGRAPH ’87, Computer Graphics, vol. 21, 1987.
17. Michael Shamz and Sheue-Ling Chang, “Rendering Trimmed NURBS with Adaptive Forward Differencing,” Proceedings of SIGGRAPH ’88, Computer Graphics, vol. 22, 1988.