AN EFFICIENT PARALLEL ALGORITHM FOR VISIBLE-SURFACE DETECTION IN 3D GRAPHICS DISPLAY

A major concern in generation of realistic graphics displays is how to identify those parts of a scene that are visible from a chosen viewin g position. There have been various algorithms for identification of v isible objects on both sequential and parallel computation models, all with different time and space requirements, depending on the properti es of the underlying machine architectures and types of the objects. I n this paper, we propose an efficient parallel algorithm for implement ation of the popular depth-buffer method on the general PRAM model tha t detects visible surfaces by projecting pixels on all surfaces to a 2 D view plane and removing all hidden surfaces. For a total of n pixels on the surfaces of an object, our algorithm runs cost-optimally in O( (n/p) + log p) time in the average case, and in O((n/p)log p) time in the worst case, using p processors on the EREW PRAM. We analyze the sc alability of the algorithm and show that it is highly scalable in the average case.