Raster Set Representations with Efficient JOIN Operator

Some 3D computer graphics algorithms are using front-to-back scene traversal (for example hiddenline removal algorithms or fast form-factor computation) . In such methods each pixel has to be processed at most once. For this purpose various raster set representations can be used. This paper gives a survey of selected data structures for raster set representation. Some new nonsymmetrical methods useful for scanline processing of 2D objects are described. Efficiency of DIFFERENCE and UNION operators (and compound JOIN operator) in typical rendering environment is our key point of view. Quantitative results measured in different computer architectures are included. 1 Motivation There are several computer graphics algorithms where compact and efficient raster set representation is wanted. We can point out methods using front-to-back traversals of 3D scene in the case that multiple processing of a single pixel cannot be accepted or shape algebras used in window systems and graphics libr..