“A parallel processor system for three-dimensional color graphics” by Niimi, Imai, Murakami, Tomita and Hagiwara

This paper describes the hardware architecture and the employed algorithm of a parallel processor system for three-dimensional color graphics. The design goal of the system is to generate realistic images of three-dimensional environments on a raster-scan video display in real-time. In order to achieve this goal, the system is constructed as a two-level hierarchical multi-processor system which is particularly suited to incorporate scan-line algorithm for hidden surface elimination. The system consists of several Scan-Line Processors (SLPs), each of which controls several slave PiXel Processors (PXPs). The SLP prepares the specific data structure relevant to each scan line, while the PXP manipulates every pixel data in its own territory. Internal hardware structures of the SLP and the PXP are quite different, being designed for their dedicated tasks. This system architecture can easily execute scan-line algorithm in parallel by partitioning the entire image space and allotting one processor element to each partition. The specific partition scheme and some new data structures are introduced to exploit as much parallelism as possible. In addition, the scan-line algorithm is extended to include smooth-shading and anti-aliasing with the aim of rendering more realistic images. These two operations are performed on a per-scan-line basis so as to preserve scan-line and span coherence. Performance estimation of the system shows that a typical system consisting of 8 SLPs and 8×8 PXPs can generate, in every 1/15th of a second, the shadowed image of a three-dimensional scene containing about 200 polygons.

1. Crow, F.C.: “A Comparison of Anti-Aliasing Techniques,” IEEE Computer Graphics and applications, Vol.1, No.1 (Jan. 1981), pp.40-48.
2. Kaplan, M., and Greenberg, D.P.: “Parallel Processing Technique for Hidden Surface Removal,” ACM Computer Graphics, Vol.13, No.2 (Aug. 1979), pp.300-307.
3. Fiume, E., Fournier, A., and Rudolph, L.: “A Parallel Scan Conversion Algorithm with Anti-Aliasing for a General-Purpose Ultracomputer,” ACM Computer Graphics, Vol.17, No.3 (Jul. 1983), pp.141-150.
4. Fuchs, H., and Johnson, B.W.: “An Expandable Multiprocessor Architecture for Video Graphics(Preliminary Report),” IEEE 6th Conf. on Computer Architecture (1979), pp.58-67.
5. Gouraud, H.: “Continuous Shading of Curved Surfaces,” IEEE Trans. on Computers, Vol.C-20, No.6 (Jun. 1971), pp.623-629.
6. Newmann, W.M., and Sproull, R.F.: “Principles of Interactive Computer Graphics,” 2nd Ed. McGraw-Hill, 1979.
7. Parke, F.I.: “Simulation and Expected Performance Analysis of Multiple Processor Z- Buffer Systems,” ACM Computer Graphics (Jul.1980), pp.48-56.
8. Schachter, B.J. (Ed.): “Computer Image Generation,” Wiley-Interscience, New York, 1983.
9. Sutherland, I. E., Sproull, R. F., and Schumacker, R.A.: “A Characterization of Ten Hidden-Surface Algorithms,” ACM Computing Surveys (Mar. 1974), pp.1-55.
10. Tomita, S., Shibayama, K., Kitamura, T., Nakata, T., and Hagiwara, H.: “A User-microprogrammable, Local Host Computer with Low-level Parallelism,” Proc. 10th Annu. Int’l Symp. on Computer Architecture (Jun. 1983), pp.151-157.