Minglei Xua and Dr. Robert P. Burton, Computer Science

The filling of general polygons, the so-called polygon scan-conversion problem, shows up in many areas of computer graphics, especially in hidden surface removal and ray tracing. The classical polygon scanconversion algorithm, the scan line algorithm, is characterized by two data structures commonly called the Edge Table (ET) and the Active Edge Table (AET). A recent technique, the critical points method, discards the edge table and retains the active edge table. In addition, a table of sorted polygon vertices that are local minima with respect to the y coordinates, or the critical points, is used. The complexities of both algorithms are 0(hn), where h is the number of scan lines, or the height of the polygon. Both algorithms are image space dependent since h is involved in the complexities. An image space dependent polygon scan-conversion algorithm is highly undesirable for parallel processing when h >> n, that is, the given polygon is geometrically huge, yet topologically simple. Several parallel polygon scan-conversion algorithms have been proposed. However, they are based on the scan line algorithm and use an image space dependent number of processors, which is quite impractical.

The major contribution of this research is a new parallel polygon scan-conversion algorithm that uses an object space dependent (vs. image space dependent) number of processors. The algorithm starts with a plane-sweep preprocessing and divides the polygon into several regions, which are later assigned to a set of processors.

Consider the polygon in Figure 1. In the plane-sweep preprocessing, polygon vertices and pair wise self intersections are categorized as start, end, bend, and cross. Each start and convex vertex, such as V , signifies the birth of a 1 new region; each end and convex vertex, such as V2, signifies the death of a region. Each start and concave vertex, such as V3, signifies that two new regions are spawned from an old region; each end and concave vertex, such as V4, signifies that two old adjacent regions are merged into a new region. Crosses and bends have no effects on regions. For example, the polygon in Fig. 1 is decomposed into seven regions.

Intuitively, the polygon decomposition can be accomplished if a horizontal line is drawn from each local extremum and concave vertex of the polygon. Once a set of regions is obtained, parallel scan-conversion starts. Some polygon information, such as selfintersection coordinates, has to be put in a shared memory to facilitate the scan-conversion. The resulting algorithm uses reasonable resources and is very fast.

Theoretically, it is easy to show that the number of processors used is indeed O(n) since the number of vertices of a given polygon is O(n). Also, it can be proved that the computational overhead of the planesweep preprocessing is O((n + K) log n), where K is the number of pairwise self-intersections of a given polygon. (K is zero when the polygon is simple.) More interestingly, the computational overhead of this algorithm can be shown to be optimal. This conclusion is based on the fact that the lower bound for the twodimensional line segment intersection problem is O((n + K) log n), which is a fundamental theorem in computational geometry. In that sense, this algorithm could be the ultimate parallel polygon scan-conversion algorithm for raster graphics.

References

1. W. Newman and R. Sproull. (1979). Principles of Interactive Graphics, 2nd Ed, McGraw-Hill. 1
2. D. Gordon et al. (1994). Fast Polygon Scan Conversion with Medical Applications. IEEE Comput. Graphics Applic., II, 20 – 27. 2
3. D. Ghosal and L. Patnaik. (1986). Parallel Polygon Scan Conversion Algorithms: Performance Evaluation on a Shared Bus Architecture. Comput. & Graphics 10.1: 7-25.
4. J. Nievergelt and F. Preparata. (1982). Plane-sweep Algorithms for Intersecting Geometric Figures. Commun. ACM 25.10: 739-747.
5. B. Chazelle and H. Edelsbrunne. (1992). Optimal Algorithm for Intersecting Line Segments. Joumal of ACM39. 1: 1-54.