New methods for line scan-conversion, polygon filling, antialiasing, line/polygon clipping and hidden line/surface removal

Line scan-conversion, polygon filling, antialiasing, clipping and hidden line/surface removal are several important primitive operations in computer graphics. Efficiently performing these operations will benefit the whole graphics research and application area.; In this dissertation, I present a new approximate method, the Slope Table method, for significantly improving the multiple-segment property of lines in a raster plane. This new method can save the pixel patterns of all GRLs (Group Representative Line) and the distances from the pixels to the corresponding GRLs for efficiently scan-converting lines and filling polygons. In particular, this method can be used to implement line and polygon edge antialiasing efficiently. The memory amount of the Slope Table in this method can be easily acceptable for current hardware implementation. Using the saved pixel distances to implement line and edge antialiasing is a novel creative work.; Second, based on the Slope Table method, I present a new multiple-segment line scan-conversion algorithm to scan-convert lines in a raster plane. With software simulation and analysis in drawing the randomly generated lines, this new algorithm is, on average, about twice as fast as Bresenham's line scan-conversion algorithm. In scan-converting lines with antialiasing, the algorithm is about eight times as fast as Gupta-Sproull's line antialiasing algorithm. Even when considering the line distribution in general graphics applications, the Slope Table method still has approximately twice the speed of the existing Gupta-Sproull's line antialiasing algorithm. The design of the hardware implementation of my new line scan-conversion algorithm is drawn here.; Third, based on the pixel patterns saved in the Slope Table, I present a new algorithm to generate the span extrema for polygon filling. This span extrema generating algorithm is about twice as fast as Dan Field's interpolation algorithm. I also demonstrate the way that uses my new line antialiasing algorithm to implement the polygon edge antialiasing. Again, I provide a hardware implementation design for this polygon filling method.; Fourth, based on the general graphics applications I collected, I provide statistics on the distribution of line lengths and directions and polygon sizes. The statistics show that most lines (87%) drawn in real graphics applications are fewer than 17 pixels in length, that almost 50% lines drawn are horizontal, vertical or diagonal, and that most polygons (88%) drawn have the edges shorter than 17 pixels in size. This statistical work has not been compiled previously by others. The data obtained from this work will provide concrete line and polygon distribution results to guide the graphics hardware and software designs.; Finally, I present new methods to speed up the line/polygon clipping and hidden line/surface removal operations in the graphics pipeline. These new methods focus on efficiently dealing with the short lines and small polygons. The analyses show that the new line/polygon clipping methods are at least twice/three times as fast as the existing line/polygon clipping methods, and that the new hidden line/surface removal methods can reach about twice/five times the speed of the z-buffer hidden surface removal method.