•  
  •  
 

Journal of Undergraduate Research

Keywords

polygon scan-conversion problem, algorithm, raster graphics

College

Physical and Mathematical Sciences

Department

Computer Science

Abstract

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.

Download

Share

COinS