3D scan-conversion algorithms for voxel-based graphics

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.

REFERENCES

• 1: Badler, N. I., "Disk Generators for a Raster Display Device", Computer Graphics and Image Processing, 6, 4 (August 1977), 589-593.
• 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.
• 3: Bezier, P., Numerical Control- Mathematics and Applications, A. R. Forrest (Trans.), Wiley, London, 1972.
• 4: Bresenham, J. E., "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4, 1 (1965), 25-30.
• 5: Bresenham, J. E., "Incremental Line Compaction", Computer Journal, 25, 1 (February 1982), 116-120.
• 6: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 7: Cederberg, R. L. T., "A New Method for Vector Generation", Computer Graphics and Image Processing, 9, 2 (February 1979), 183-195.
• 8: James H. Clark, Parametric curves, surfaces and volumes in computer graphics and computer-aided geometric design, Stanford University, Stanford, CA, 1981
• 9: Danielsson, P. E., "Incremental Curve Generation", IEEE Trans. on Computers, C-19, (1970), 783-793.
• 10: Doros, M., "Algorithms for Generation of Discrete Circles, Rings, and Disks", Computer Graphics and Image Processing, 10, 4 (August 1979), 366-371.
• 11: Earnshaw, R. A., "Line Tracking for Incremental Plotters", Computer Journal, 23, 1 (February 1980), 46-52.
• 12: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 13: Goldwasser, S. M., "A Generalized Object Display Processor Architecture", IEEE Computer Graphics ~ Applications, 4, 10 (October 1984), 43-55.
• 14: L. J. Guibas , J. Stolfi, A language for bitmap manipulation, ACM Transactions on Graphics (TOG), v.1 n.3, p.191-214, July 1982 [doi>10.1145/357306.357308]
• 15: Hersch, R. D., "Descriptive Contour Fill of Partly Degenerated Shapes", IEEE Computer Graphics ~ Applications, 6, 7 (July 1986), 61-70.
• 16: Horn, B. K. P., "Circle Generators for Display Devices", Computer Graphics and Image Processing, 5, (June 1976), 280-288.
• 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.
• 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.
• 19: Kaufman, A. and Bakalash, R., "Memory and Processing Architecture for 3-D Voxel-Based Imagery", submitted for publication, 1986.
• 20: Kaufman, A. and Bakalash, R., "A 3-D Cellular Frame Buffer", Proc. EUROGRAPHICS'85, Nice, France, September 1985, 215-220.
• 21: Kaufman, A., "Voxel-Based Architectures for Three-Dimensional Graphics" Proc. IFIP'86, Dublin, Ireland, September 1986, 361-366.
• 22: Arie E. Kaufman, A Two-Dimensional Frame Buffer Processor, Advances in Computer Graphics Hardware II (Eurographics'87 Workshop), p.93-109, January 1988
• 23: M. D. McIlroy, Best approximate circles on integer grids, ACM Transactions on Graphics (TOG), v.2 n.4, p.237-263, October 1983 [doi>10.1145/245.246]
• 24: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 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.
• 26: Theo Pavlidis, Algorithms for Graphics and Imag, W. H. Freeman & Co., New York, NY, 1983
• 27: Pavlidis, T., "Scan Conversion of Regions Bounded by Parabolic Splines", IEEE Computer Graphics ~ Applications, 5, 6 (June 1985), 47-53.
• 28: Pitteway, M. L. V., "Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter", Computer Journal, 10, 3 (November 1967), 282-289.
• 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.
• 30: Roberge, J., "A Data Reduction Algorithm for Planar Curves", Computer Vision, Graphics, and Image processing, 29, (1985), 168-195.
• 31: Rosenfeld, A., "Three-Dimensional Digital Topology", Computer Science Center, Univ. of Maryland, Tech. Rep.-936, 1980.
• 32: R. F. Sproull, Using program transformations to derive line-drawing algorithms, ACM Transactions on Graphics (TOG), v.1 n.4, p.259-273, Oct. 1982 [doi>10.1145/357311.357312]
• 33: 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]
• 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.
• 35: Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985 [doi>10.1145/282918.282943]
• 36: Van Aken, J. R., "An Efficient Ellipse-Drawing Algorithm", IEEE Computer Graphics ~ Applications, 4, 9 (September 1984), 24-35.
• 37: Van Wyk, C. J., "Clipping to the Boundary of a Circular-Arc Polygon", Computer Vision, Graphics, and Image Processing, 25, (1984), 383-392.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Raster display devices
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Design, Measurement, Performance, Theory