A nearly output sensitive parallel hidden surface removal algorithm in object space

We present a new method for solving the hidden surface removal (HSR) problem in parallel on a crew pram using a combination of new observations and known methods for solving related geometric problems. The new algorithm obtains the bounds of O (log2 n) time and O (n long n + 1) processors, where n is the amount of given endpoints of the input and l is the number of intersections in the viewing plane. In contrast to most known algorithms solving the HSR problem in object space, this method is able to process input scenes where penetrations of line segments and polygonal areas are allowed. The ability to process such an input has enormous advantage for integrating three dimensional curves c ∩ IR3, which have been approximated by segments. Since a penetration of two polygonal areas will be detected during run time, this algorithm could also be used for testing given scenes for intersections of polygonal areas. In this case the algorithm is able to solve the hidden line removal problem in the same bounds. For practical purposes this algorithm allows also non convex (but simple and planar) polygons as input. You do not have to have triangulated scenes. According to the constraints of object space HSR algorithms, we will construct the visibility graph of the given scene as a planar graph in the viewing plane. Although the number of processors depends on the number of intersections in the viewing plane, in most given scenes this method will work like an output sensitive algorithm. Typical examples like "one big rectangle is covering all intersections" will be detected and these intersections are not computed