“Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes” by Kaufman

Three-dimensional (3D) scan-conversion algorithms, that scan-convert 3D parametric objects into their discrete voxelmap representation within a Cubic Frame Buffer (CFB), are presented. The parametric objects that are studied include Bezier form of cubic parametric curves, bicubic parametric surface patches, and tricubic parametric volumes. The converted objects in discrete 3D space maintain pre-defined application-dependent connectivity and fidelity requirements.The algorithms introduced here emply third-order forward difference techniques. Efficient versions of the algorithms based on first-order decision mechanisms, which employ only integer arithmetic, are also discussed. All algorithms are incremental and use only simple operations inside the inner algorithm loops. They perform scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All the algorithms have been implemented as part of the CUBE Architecture, which is a voxel-based system for 3D graphics.

1. Bezier, P., “UNISURF System: Principles, Program, Language”, in Computer Languages for Numerical Control, J. Hatvany, (ed.), North-Holland, Amsterdam- London, 1972, 417-426.
2. Bezier, P., Numerical Control Mathematics and Applications, A. R. Forrest (Trans.), Wiley,-London, 1972.
3. Bezier, P., “Mathematical and Practical Possibilities of UNISURF”, in Computer Aided Geometric Design, R. E. Barnhitl and R. F. Riesenfeld, (eds.), Academic, New York, 1974, 127-152.
4. Blinn, J. F., Carpenter, L., Lane, J. and Whirred, T., “Scan Line Methods for Displaying Parametrically Defined Surfaces”, Communications of the ACM, 23, 1 (January 1980), 23-34.
5. Bresenham, J. E., “Algorithm for Computer Control of a Digital Plotter”, IBM Systems Journal, 4, 1 (1965), 25- 30.
6. Clark, J. H., “Parametric Curves, Surfaces, and Volumes in Computer Graphics and Computer-Aided Geometric Design”, Technical Report 221, Computer Systems Laboratory, Stanford University, Stanford, CA, November 1981.
7. Coons, S. A., “Surfaces for Computer-Aided Design of Space Forms”, MIT Project MAC Teeh. Rep.-41, June 1967.
8. deBoor, C., “On Uniform Approximation with Splines”, Journal of Approximation Theory, 1, (1968), 249-274.
9. Foley, J. D. and van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, MA, 1982.
10. Forrest, A. R., “On Coons and Other Methods for the Representation of Curved Surfaces”, Computer Graphics and Image Processing, 1, 4 (December 1972), 341-354.
11. Goldwasser, S. M., “A Generalized Object Display Processor Architecture”, IEEE Computer Graphics and Applications, 4, 10 (October 1984), 43-55.
12. Jackel, D., “The Graphics PARCUM System: A 3D Memory Based Computer Architecture for Processing and Display of Solid Models”, Computer Graphics Forum, 1985, 21-32.
13. Kaufman, A. and Bakalash, R., “CUBE An Architecture Based on a 3-D Voxel Map”, in Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, (ed.), Springer-Verlag, 1987.
14. Kaufman, A. and Bakatash, R., “A 3-D Cellular Frame Buffer”, Proc. EUROGRAPHICS’85, Nice, France, September 1985, 215-220.
15. Kaufman, A. and Bakalash, R., “Memory and Processing Architecture for 3-D Voxel-Based Imagery”, Technical Report 87/06, Department of Computer Science, SUNY at Stony Brook, February 1987.
16. Kaufman, A., “An Algorithm for 3D Scan-Conversion of Polygons”, Proc. EUROGRAPHICS’87, Amsterdam, Netherlands, August 1987.
17. Kaufman, A., “Voxel-Based Architectures for Three- Dimensional Graphics”, Proc. IFIP’S6, Dublin, Ireland, September 1986, 361-366.
18. Kaufman, A. and Shimony, E., “3D Scan-Conversion Algorithms for Voxel-Based Graphics”, Proc. AGM Workshop on Interactive 3D Graphics, Chapel Hill, NC, October 1986.
19. Kim, C. E., “Three-Dimensional Digital Planes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-$, 5 (September 1984), 639-645.
20. Lane, J. M. and Riesenfeld, R. F., “A Theoretical Development for the Computer Generation and Display of Pieeewise Polynomial Surfaces”, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2, 1 (January 1980), 35-46.
21. Ohashi, T., Uchiki, T. and Tokoro, M., “A Three- Dimensional Shaded Display Method for Voxel-Based Representation”, Proe. EUROGRAPHICS’85, Nice, France, September 1985, 221-232.
22. Pavlidis, T., Algorithms }or Graphics and Image Processing, Computer Science Press, Rockvilte, MD, 1982.
23. Riesen feld, R. F., “Applications of B-spline Approximation to Geometric Problems of Computer Aided Design”, University of Utah UTEC-CSc-73-126, March 1973.
24. Rosenfeld, A., “Three-Dimensional Digital Topology”, Computer Science Center, Univ. of Maryland, Teeh. Rep.-936, 1980.
25. Srihari, S. N., “Representation of Three-Dimensional Digital Images”, Computing Surveys, 4, 13 (December 1981), 399-424.