Parallel Machines for Computer Graphics
Creators: name: Ullner, Michael K.
Publisher: name: California Institute of Technology
Year: 1983

description: Computer graphics provides some ideal applications for the kind of highly parallel implementations made possible by advances in integrated circuit technology. Specifically, hidden line and hidden surface algorithms, while easily defined and
simple in concept, entail a substantial amount of computation. This requirement fits
the characteristics of integrated circuit technology, where modular designs involving
regular communication between many concurrent operations are rewarded with high
performance at an acceptable cost.
Ray tracing is a very flexible technique that can be used to produce some of
the most realistic of all computer generated images by simulating the interactions
of light rays with surfaces in a modeled scene. Because light rays are mutually independent, many may be processed simultaneously, and the potential for concurrency
is great. One architecture for expediting a ray tracing algorithm consists of a conventional computer equipped with a special purpose peripheral device for locating
the intersections of ray8 and surfaces. This intersection computation is the most
time consuming aspect of a ray tracing algorithm. Although the attached processor
configuration can produce images more quickly than an unaided computer, its per-
formance is limited. Alternatively, a pipeline of surface processors can replace the
peripheral device. Each processor computes the intersections of its stored surface
with rays that flow through the pipe. Such a machine machine can be quite fast,
and its performance can be increased by lengthening the pipeline, but the component
processors are not very effectively utilized. A third approach combines the advantages
of the prior two machines by using an array of processors, each simulating a distinct
subvolume of the modeled world by treating light rays traveling through space as
messages flowing between processors. Local communication is sufficient because light
rays travel continuously through space.
In real time computer graphics, successive images must be produced in times that
are imperceptible to a viewer. Although the ray tracing machines fall short of this
performance, it is possible to compromise image quality in order to produce a highly
parallel machine capable of real time operation. The processors in such a machine
are organized to form a binary tree. Leaf processors scan-convert surfaces, producing
a sequence of segments, where a segment is the portion of a surface that appears on
a single scan line of the display. Processors towards the root of the tree accept two
such segment sequences and produce a third in which all segment overlap has been
resolved. The final image is available at the root of the tree. The communication
bottleneck that would otherwise occur at the root can be eliminated by breaking out parallel roots, and the resulting tree may be extended to scenes of almost arbitrary
complexity merely by increasing the supply of available processors.
Massive parallelism can also be applied to the problem of removing hidden edges
from line drawings. A suitable architecture takes the form of a pipeline in which each
processor is dedicated to the handling of a single polygon edge. These processors
successively clip line segments passing through the pipeline to eliminate portions
hidden behind surfaces. Each edge processor can be constructed out of little more
than three serial multipliers.
The machines described here are varied in organization, and each functions differently, but their treatment of sorting is one ingredient common to all. Sorting is a key
component of hidden surface algorithms running on conventional computers, but its
extensive communication requirements make it costly for use in a highly integrated
design. Consequently, the highly parallel machines described here operate largely
without sorting. Instead, they maintain information in sorted order or make use of
already sorted information to limit communication requirements.