Vector and raster hidden surface removal using parallel connected stripes

A list priority algorithm for the removal of the hidden surfaces from a three-dimensional scene is presented. The general lines of the solution proposed are similar to those of the c1assical list priority algorithms (determination of the depth relations between the faces of the solids of the scene, construction of a priority list, removal of the hidden parts), but a new sorting procedure and the use of an efficient data structure to represent the faces of the solids (the Parallel Connected Stripes data structure) make the algorithm interesting. The PCS data structure allows the algorithm to work on several faces at a time, to solve cyclic overlaps, to remove hidden parts efficiently and to make low memory requirements. The algorithm produces both vectorial output (the boundaries of the faces and the holes) and raster output (similarly to a scan line algorithm) without any rasterization process.