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 hidden-line and hidden-surface algorithms take θ(log n) time using n~2/logn CREW PRAM processors.
展开▼
