Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes

ABSTRACT

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.

REFERENCES

• 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: Jeffrey M. Lane , Loren C. Carpenter , Turner Whitted , James F. Blinn, Scan line methods for displaying parametrically defined surfaces, Communications of the ACM, v.23 n.1, p.23-34, Jan. 1980 [doi>10.1145/358808.358815]
• 5: Bresenham, J. E., "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4, 1 (1965), 25- 30.
• 6: James H. Clark, Parametric curves, surfaces and volumes in computer graphics and computer-aided geometric design, Stanford University, Stanford, CA, 1981
• 7: S. A. Coons, SURFACES FOR COMPUTER-AIDED DESIGN OF SPACE FORMS, Massachusetts Institute of Technology, Cambridge, MA, 1967
• 8: deBoor, C., "On Uniform Approximation with Splines", Journal of Approximation Theory, 1, (1968), 249-274.
• 9: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, 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: Arie Kaufman , Eyal Shimony, 3D scan-conversion algorithms for voxel-based graphics, Proceedings of the 1986 workshop on Interactive 3D graphics, p.45-75, January 1987, Chapel Hill, North Carolina, United States [doi>10.1145/319120.319126]
• 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: Theo Pavlidis, Algorithms for Graphics and Imag, W. H. Freeman & Co., New York, NY, 1983
• 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: Sargur N. Srihari, Representation of Three-Dimensional Digital Images, ACM Computing Surveys (CSUR), v.13 n.4, p.399-424, Dec. 1981 [doi>10.1145/356859.356862]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Digitizing and scanning

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Theory