Arie Kaufman
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.
- 1 Bezier, P., "UNISURF System: Principles, Program, Language", in Computer Languages for Numerical Control, J. Hatvany, (ed.), North-Holland, Amsterdam- London, 1972, 417-426.Google Scholar
- 2 Bezier, P., Numerical Control Mathematics and Applications, A. R. Forrest (Trans.), Wiley,-London, 1972.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 5 Bresenham, J. E., "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4, 1 (1965), 25- 30.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 7 Coons, S. A., "Surfaces for Computer-Aided Design of Space Forms", MIT Project MAC Teeh. Rep.-41, June 1967. Google ScholarDigital Library
- 8 deBoor, C., "On Uniform Approximation with Splines", Journal of Approximation Theory, 1, (1968), 249-274.Google Scholar
- 9 Foley, J. D. and van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, MA, 1982. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 11 Goldwasser, S. M., "A Generalized Object Display Processor Architecture", IEEE Computer Graphics and Applications, 4, 10 (October 1984), 43-55.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 14 Kaufman, A. and Bakatash, R., "A 3-D Cellular Frame Buffer", Proc. EUROGRAPHICS'85, Nice, France, September 1985, 215-220.Google Scholar
- 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.Google Scholar
- 16 Kaufman, A., "An Algorithm for 3D Scan-Conversion of Polygons", Proc. EUROGRAPHICS'87, Amsterdam, Netherlands, August 1987.Google Scholar
- 17 Kaufman, A., "Voxel-Based Architectures for Three- Dimensional Graphics", Proc. IFIP'S6, Dublin, Ireland, September 1986, 361-366.Google Scholar
- 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. Google ScholarDigital Library
- 19 Kim, C. E., "Three-Dimensional Digital Planes", IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-$, 5 (September 1984), 639-645.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 22 Pavlidis, T., Algorithms }or Graphics and Image Processing, Computer Science Press, Rockvilte, MD, 1982. Google ScholarDigital Library
- 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.Google Scholar
- 24 Rosenfeld, A., "Three-Dimensional Digital Topology", Computer Science Center, Univ. of Maryland, Teeh. Rep.-936, 1980.Google Scholar
- 25 Srihari, S. N., "Representation of Three-Dimensional Digital Images", Computing Surveys, 4, 13 (December 1981), 399-424. Google ScholarDigital Library
Index Terms
- Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes
Recommendations
Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes
SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniquesThree-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 ...
3D scan-conversion algorithms for voxel-based graphics
I3D '86: Proceedings of the 1986 workshop on Interactive 3D graphicsAn assortment of algorithms, termed three-dimensional (3D) scan-conversion algorithms, is presented. These algorithms scan-convert 3D geometric objects into their discrete voxel-map representation within a Cubic Frame Buffer (CFB). The geometric objects ...
Comments