Arie Kaufman
ABSTRACT
An 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 that are studied here include three-dimensional lines, polygons (optionally filled), polyhedra (optionally filled), cubic parametric curves, bicubic parametric surface patches, circles (optionally filled), and quadratic objects (optionally filled) like those used in constructive solid geometry: cylinders, cones, and spheres.
All algorithms presented here do scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. All algorithms are incremental and use only additions, subtractions, tests and simpler operations inside the inner algorithm loops. Since the algorithms are basically sequential, the temporal complexity is also linear. However, the polyhedron-fill and sphere-fill algorithms have less than linear temporal complexity, as they use a mechanism for writing a voxel run into the CFB. The temporal complexity would then be linear with the number of pixels in the object's 2D projection. All algorithms have been implemented as part of the CUBE Architecture, which is a voxel-based system for 3D graphics. The CUBE architecture is also presented.
- 1.Badler, N. I., "Disk Generators for a Raster Display Device", Computer Graphics and Image Processing, 6, 4 (August 1977), 589-593.Google Scholar
Cross Ref
- 2.Bezier, P., "Mathematical and Practical Possibilities of UNISURF", in Computer Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, (eds.), Academic, New York, 1974, 127-152.Google Scholar
- 3.Bezier, P., Numerical Control- Mathematics and Applications, A. R. Forrest (Trans.), Wiley, London, 1972.Google Scholar
- 4.Bresenham, J. E., "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4, 1 (1965), 25-30.Google ScholarDigital Library
- 5.Bresenham, J. E., "Incremental Line Compaction", Computer Journal, 25, 1 (February 1982), 116-120.Google ScholarCross Ref
- 6.Bresenham, J. E., "A Linear Algorithm for Incremental Digital Display of Circular Arcs", Commun. A CM, 20, 2 (February 1977), 100-106. Google ScholarDigital Library
- 7.Cederberg, R. L. T., "A New Method for Vector Generation", Computer Graphics and Image Processing, 9, 2 (February 1979), 183-195.Google ScholarCross Ref
- 8.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
- 9.Danielsson, P. E., "Incremental Curve Generation", IEEE Trans. on Computers, C-19, (1970), 783-793.Google ScholarDigital Library
- 10.Doros, M., "Algorithms for Generation of Discrete Circles, Rings, and Disks", Computer Graphics and Image Processing, 10, 4 (August 1979), 366-371.Google ScholarCross Ref
- 11.Earnshaw, R. A., "Line Tracking for Incremental Plotters", Computer Journal, 23, 1 (February 1980), 46-52.Google ScholarCross Ref
- 12.Foley, J. D. and van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, MA, 1982. Google ScholarDigital Library
- 13.Goldwasser, S. M., "A Generalized Object Display Processor Architecture", IEEE Computer Graphics ~ Applications, 4, 10 (October 1984), 43-55.Google ScholarCross Ref
- 14.Guibas, L. J. and Stolfi, J., "A Language for Bitmap Manipulation", A CM Trans. on Graphics, 1, 3 (July 1982), 191-214. Google ScholarDigital Library
- 15.Hersch, R. D., "Descriptive Contour Fill of Partly Degenerated Shapes", IEEE Computer Graphics ~ Applications, 6, 7 (July 1986), 61-70.Google Scholar
- 16.Horn, B. K. P., "Circle Generators for Display Devices", Computer Graphics and Image Processing, 5, (June 1976), 280-288.Google ScholarCross Ref
- 17.Jackel, D., "The Graphics PARCUM System: A 3D Memory Based Computer Architecture for Processing and Display of Solid Models", Computer Graphics Forum, 4, (1985), 21-32.Google ScholarCross Ref
- 18.Jordan, B. W., Lennon, W. J. and Holm, B. D., "An Improved Algorithm for the Generation of Nonparametric Curves", IEEE Trans. on Computers, C-22, 12 (December 1973), 1052-1060.Google ScholarDigital Library
- 19.Kaufman, A. and Bakalash, R., "Memory and Processing Architecture for 3-D Voxel-Based Imagery", submitted for publication, 1986.Google Scholar
- 20.Kaufman, A. and Bakalash, R., "A 3-D Cellular Frame Buffer", Proc. EUROGRAPHICS'85, Nice, France, September 1985, 215-220.Google Scholar
- 21.Kaufman, A., "Voxel-Based Architectures for Three-Dimensional Graphics" Proc. IFIP'86, Dublin, Ireland, September 1986, 361-366.Google Scholar
- 22.Kaufman, A., "Memory Organization for a Cubic Frame Buffer", Proc. EUROGRAPHICS'86, Lisbon, Portugal, August 1986, 93-100. Google ScholarDigital Library
- 23.McIlroy, M. D., "Best Approximate Circles on Integer Grids", A CM Trans. on Graphics, 2, 4 (October 1983), 237-263. Google ScholarDigital Library
- 24.Newman, W. M. and Sproull, R. F., Principles of Interactive Computer Graphics, (2nd ed.), McGraw Hill, New York, 1979. Google ScholarDigital Library
- 25.Ohashi, T., Uchiki, T. and Tokoro, M., "A Three-Dimensional Shaded Display Method for Voxel-Based Representation", Proc. EUROGRAPHICS'85, Nice, France, September 1985, 221-232.Google Scholar
- 26.Pavlidis, T., Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, MD, 1982. Google ScholarDigital Library
- 27.Pavlidis, T., "Scan Conversion of Regions Bounded by Parabolic Splines", IEEE Computer Graphics ~ Applications, 5, 6 (June 1985), 47-53.Google Scholar
- 28.Pitteway, M. L. V., "Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter", Computer Journal, 10, 3 (November 1967), 282-289.Google ScholarCross Ref
- 29.Pitteway, M. L. V. and Green, A. J. R., "Bresenham's Algorithm with Run Line Coding Shortcut", Computer Journal, 25, 1 (February 1982), 114-115.Google ScholarCross Ref
- 30.Roberge, J., "A Data Reduction Algorithm for Planar Curves", Computer Vision, Graphics, and Image processing, 29, (1985), 168-195.Google ScholarCross Ref
- 31.Rosenfeld, A., "Three-Dimensional Digital Topology", Computer Science Center, Univ. of Maryland, Tech. Rep.-936, 1980.Google Scholar
- 32.Sproull, R. F., "Using Program Transformations to Derive Line-Drawing Algorithms", A CM Trans. on Graphics, 1, 4 (1982), 259-273. Google ScholarDigital Library
- 33.Srihari, S. N., "Representation of Three-Dimensional Digital Images", A CM Computing Surveys, 13, 4 (December 1981), 399-424. Google ScholarDigital Library
- 34.Suenaga, Y., Kamae, T. and Kobayashi, T., "A High-Speed Algorithm for the Generation of Straight Lines and Circular Arcs", IEEE Trans. on Computers, TC-28, 10 (October 1979), 728-736.Google ScholarDigital Library
- 35.Van Aken, J. R. and Novak, M., "Curve-Drawing Algorithms for Raster Displays", A CM Trans. on Graphics, 4, 2 (April 1985), 147-169. Google ScholarDigital Library
- 36.Van Aken, J. R., "An Efficient Ellipse-Drawing Algorithm", IEEE Computer Graphics ~ Applications, 4, 9 (September 1984), 24-35.Google Scholar
- 37.Van Wyk, C. J., "Clipping to the Boundary of a Circular-Arc Polygon", Computer Vision, Graphics, and Image Processing, 25, (1984), 383-392.Google ScholarCross Ref
Index Terms
- 3D scan-conversion algorithms for voxel-based graphics
Recommendations
Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes
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 ...
Interactive indirect illumination using voxel-based cone tracing: an insight
SIGGRAPH '11: ACM SIGGRAPH 2011 TalksIndirect illumination is an important element for realistic image synthesis, but its computation is expensive and highly dependent on the complexity of the scene and of the BRDF of the surfaces involved. While off-line computation and pre-baking can be ...
Voxel-based global illumination
I3D '11: Symposium on Interactive 3D Graphics and GamesComputing a global illumination solution in real-time is still an open problem. We introduce Voxel-based Global Illumination (VGI), a scalable technique that ranges from real-time near-field illumination to interactive global illumination solutions. To ...
Comments