The Slope Table Method for Line Scan-Conversion and Polygon Filling

Abstract

In a raster area, a line may include multiple identical segments. The multiple
segment property of a line can be used to speed up line scan-conversion. However, in
an N(N raster area, the percentage of multiple segment lines is less than 40%. The
advantage of the multiple segment property is limited. With the Slope Table method,
the percentage of multiple segment lines can be increased to 99%. Such a big change
on the multiple segment property can bring improvements for line scan-conversion. In
software implementation for line scan-conversion with antialiasing, this method is on
average more than 6 times faster than Gupta's antialiasing line algorithm.

On the other hand, the Slope Table method only uses N GRLs (Group Representative
Lines) to represent all the N(N+1)/2 lines. This property makes it possible to save
the pixel patterns of the first segments of N GRLs into memory (Slope Table). With
the saved GRL's pixel patterns, we will never need to calculate the pixel positions
of a line during scan-conversion. Instead, we can directly obtain the pixel positions
from the saved pixel patterns. This can further speed up line scan-conversion.

To fill polygon, the existing methods need to calculate the span extrema between two
edges. Actually, the span extrema are determined by the pixel positions of the edges.
In the Slope Table, the saved pixel patterns can also be used to determine the span
extrema. Compared with calculating the span extrema each step, directly determining
the span extrema from the pixel patterns is much faster. So the Slope Table method
can also be used to fill polygons efficiently.

============================================================

Xusheng Wang is a doctoral student in Information Technology at George Mason
University (GMU). His major is on Computer Graphics. His Ph.D. research focuses on
developing a new method to speed up polygon filling and line scan-conversion in
computer graphics. As part of his dissertation, he is finishing a comprehensive VR
software tool that runs on many different computer systems, including Mac computers
which are common in middle schools but currently have no 3D VR tools.

Xusheng also participated in two Virtual Reality (VR) projects at GMU. In
ScienceSpace project, he wrote the source codes of the Newton World for SGI/O2
system, and also integrated the 3D sound system and haptic devices with the Maxwell
World on SGI/ONYX system. In DEVISE project, he implemented all the VR applications
with Sense8's WorldUp VR tool.

Since joined George Mason University in 1997, he has also been serving as a system
administrator for the SGI workstations in the Graphics lab and the Virtual Reality
lab.

Before joined GMU, his work was focused on developing various management information
systems. He developed several MIS systems with Oracle7 and taught Oracle7 in China.
In addition to Computer Graphics, he also has a strong theory and practice background
in Database.

As a Ph.D. student on Computer Graphics, he is interested in Primitive Algorithms in
Computer Graphics, Virtual Reality, Real-Time Simulation and Information
Visualization.

Xusheng got his Master's degree and Bachelor's degree in Computer Science from
Southwest Jiaotong University in China in 1986 and 1983.