Systolic architectures for realistic 3-D graphics.

Abstract

Computer Graphics has come a long way from its humble beginning of lin£ drawing displays in the early sixties to the present day extremely realistic, synthetic, and photography quality pictures. As a result, interactive computer graphics system as a tool for man-machine interaction has gained wide applicability in many scientific and engineering areas. One of the exciting and potentially important areas in interactive computer graphics is the synthetic generation of realistic images of solid objects. In order to have a feedback on the solids modelled by an interactive designer, the generation of images and their display have to be carried cut in at least l/30th of a second. In this dissertation, we address mainly the high speed implementation of three important graphics tasks namely, removal of hidden surfaces in the display of 3-D objects represented by planar surfaces, generation of curves and surfaces, and evaluation of polynomial expressions using systolic architectures. Highly parallel implementations for the real-time display are made possible by the great strides made recently in Very Large Scale Integration (VLSI) technology. In this context the systolic model of computation has emerged as an important class of parallel computation. Systolic architectures have all the desirable properties one looks for in parallel architectures except that they are not general purpose computing systems. They are high speed arrays having high effective bandwidth and ideally suited for compute-bound problems and VLSI implementation. Another feature is that all these benefits are available at very low cost. These attractive features are exploited in our choice of systolic architecture as the parallel architecture-for graphics systems. A fundamental problem in the realistic display of modelled objects on a 2-D monitor screen is occulting hidden portions of objects. This problem is generally referred to as Hidden Surface Removal (HSR). The excessive lime required to execute the HSR algorithm for even moderately complex 3-D objects places a severe constraint on the real-time display system. We propose systolic linear arrays for the scan line-based hidden surface removal. Three paradigm. The first linear array is simulated and the performance results are presented. For the other two linear arrays, analytical expressions for the time and space requirements are derived. Frame buffers are universally used to store the picture that is displayed on the graphics monitor. Frame buffers can be made smart by providing them with simple computing capability. We present two organisations for frame buffers namely, the square grid*array using hexagonal interconnection and the linear array for evaluating polynomial expressions. The area and time complexities of the two organisations are compared. The power of the smart frame buffer is demonstrated by presenting sample algorithms for execution for realistic display of objects. While the display of solid objects modelled by polygons is widely used in practice, polygons are not suitable for modelling curved or smoothly varying objects. Bezier and B-Spline curves and surfaces have been widely used to model smoothly varying objects. The generation and display of Bezier and B-Spline curves and surfaces are compute-intensive processes. Triangular and trapezoidal systolic arrays are proposed for the curve generation. Systolic arrays for the derivatives of Bezier and B-Spline curves are also discussed. For the surface generation, pyramidal and prism type architectures are presented. Suggestions are made for the efficient VLSI layout for these systolic arrays. To gain practical experience with systolic arrays, a hardware systolic cell using the 8086 microprocessor chip is designed. The arrays made out of these cells are used for executing a few of the systolic algorithms. The performance in terms of speedup for the systolic arrays is plotted and the results are discussed. Finally we touch upon the subject of ray tracing and systolic arrays for miscellaneous graphics problems such as line and circle drawing. Two systolic architectures are presented for ray tracing. The first one is a systolic tree which computes the expensive ray-surface intersections in parallel and the second one is a systolic mesh of trees.