Given a collection of non-intersecting simple polygons possibly with holes and with a total of n edges in three-dimensional space; parallel algorithms are given for the problems called hidden-line and hidden-surface removal in computer graphics. More precisely, algorithms are proposed to find the portions of the edges visible from (0, 0, ∞) and to find the upper envelope (i.e., the pointwise maximum) of the polygons. The proposed solution for the hidden-line problem is the parallelization of the optimal sequential algorithm given by Devai in 1986. As the optimal sequential algorithm for the hidden-surface problem given by McKenna in 1987 is rather involved, a new optimal sequential algorithm is proposed, which is amenable to parallelization and might also have practical significance in its own right. Both of the parallel hiddenline and hidden-surface algorithms take Θ(log n) time using n2/ log n CREW PRAM processors.
['Frank Dévai']
An optimal hidden-surface algorithm and its parallelization