A Fast Line Rasterization Algorithm Based on Pattern Decomposition

Straight line is the fundamental element in all graphics systems. A fast line rasterization algorithm is presented in this paper. A straight line is considered as composed of large patterns instead of individual pixels. The proposed algorithm ensures the accuracy of the generated line by checking the ultimate error of each pattern instead of the y coordinate difference at each candidate pixel. Since it generates a pattern consisting of one or more segments at each step, the times of operation and output involved in line drawing is reduced significantly. Besides, due to the weak symmetry between the raster compositions of various types of straight lines, some lines can be drawn directly without the intermediate operations, which simplifies the algorithm design and accelerates the line generation further. Theoretical analysis and implementation results show that the average computation for error judgment involved in this algorithm is 10 times less than that in Bresenham algorithm, and the average generation speed is increased by 2.7 times.