Four-step Scan-symmetrical Incremental Generation of Lines
对称扫描四步增量画线算法

The generation of lines is elementary problem in computer graphics. A four-step incremental generation of lines is proposed. The algorithm firstly gives the choice standard of the pixel that the most closed to the straight line, and then converts it to integral variable form. So it develops and describes a new generation of lines, the four-step incremental generation of lines. The algorithm is easy to be implemented by hardware. It's only integer addition and left shift operation being used in the algorithm of incremental generation of lines. So the algorithm has lower complication in hardware and high speed. The four pixels being drew on the same time by using this algorithm. So the speed of the four-step incremental generation of lines is as three or four times as the speed of the Bresenham algorithm. Scan-symmetrical based on the symmetry of lines cause speed of the four-step incremental generation of lines increased as well. Binary search tree method based on geometrical characteristic of lines is used in the four-step algorithm. So almost the same times of decision per pixel between the four-step algorithm and the Bresenham algorithm, and the times of iterative per pixel of the four-step algorithm is much more less than the Bresenham algorithm.