“A contour display generation algorithm for VLSI implementation” by Zyda

  • ©Michael J. Zyda

Conference:


Type:


Title:

    A contour display generation algorithm for VLSI implementation

Presenter(s)/Author(s):



Abstract:


    Recent articles have discussed the current trend towards designing raster graphics algorithms into VLSI chips. The purpose of these design efforts is to capture some of the real-time animation capability found in vector graphics systems. Currently, real-time vector graphics animation is limited primarily to operations involving coordinate transformations. In order to enhance this animation capability, frequently encountered vector graphics algorithms that require the high speed, parallel computation capability of VLSI must be identified. Real-time contour display generation from grid data is one such algorithm. This paper describes the specifics of a contour display generation algorithm, the architectural framework of a processor that performs this algorithm and the architectural requirements of such a processor. The contouring algorithm is based on a data structure, the contouring tree, whose regularity and amenability for parallel computation make it an ideal candidate for VLSI. The architectural framework for a contouring processor chip that performs this algorithm for the real-time environment of interactive graphics is discussed, particularly the issues of memory size and data distribution. A model of the contouring process is created in order to determine the necessary physical parameters of the contouring processor in this architectural framework. Conclusions are drawn concerning the feasibility of producing a VLSI chip that performs this contouring algorithm.

References:


    1. Aho, Alfred V., Hopcroft, John E., and Ullman, Jeffrey D. The Design and Analysis of Computer Algorithms. Reading, Massachusetts: Addison-Wesley Publishing Company, 1974, Chapters 1-5.
    2. Barry, C.D. and Sucher, J. A. “Interactive Real-Time Contouring of Density Maps,” ACA Winter Meeting, Honolulu, March 1979, Poster Session.
    3. Clark, James H. “A System Design Revolution,” Computer Graphics: A Quarterly Report of SIGGRAPH-ACM, Volume 15, Number 3 (August 1981), pp. 79-80.
    4. Dammkoehler, R.A. Personal communication. October 1981.
    5. Mead, Carver and Conway, Lynn, Introduction to VLSI Systems, Reading, Massachusetts: Addison-Wesley Publishing Company, 1980, Chapter 8.
    6. Myers, Ware “Algorithms, Ergonomics, and Solid Modeling Highlight SIGGRAPH ’81,” Computer, Volume 14, Number 10 (October 1981), pp. 126-127.
    7. Newman, William H. and Sproull, Robert F. Principles of Interactive Computer Graphics. Second Edition. New York: McGraw-Hill, 1979, Chapter 1.
    8. Sproull, Robert “Custom VLSI Chips for Graphics,” Computer Graphics: A Quarterly Report of SIGGRAPH-ACM, Volume 15, Number 3 (August 1981), p. 79.
    9. Stritter, Edward and Gunter, Tom “A Microprocessor Architecture for a Changing World: The Motorola 68000,” Computer, Vol. 12, No. 2 (February 1979).
    10. Wright, Thomas and Humbrecht, John “ISOSRF—An Algorithm for Plotting Iso-Valued Surfaces of a Function of Three Variables,” Computer Graphics: A Quarterly Report of SIGGRAPH-ACM, Volume 13, Number 2 (August 1979), pp. 182-189.
    11. Zyda, Michael J. “Multiprocessor Considerations in the Design of a Real-Time Contour Display Generator,” Technical Memorandum 42, St. Louis: Department of Computer Science, Washington University, October 1981.
    12. Zyda, Michael J. “Joystick Driven Display Rotation and Control Console Management,” Technical Memorandum 24, St. Louis: Department of Computer Science, Washington University, November 1980.


ACM Digital Library Publication: