对称扫描四步增量画线算法

直线的生成方法一直是计算机图形学中的基本总是，为此提出一种四步增量算法，该算法中只用到了整数加法运算和左移位运算，大大降低了硬件实现的复杂度，同时有效地提高了速度，易于硬件实现，由于每次可同时画出4个像素，故其效率大约是Bresenham算法的3-4倍，另外，还可根据直线的对称性进行对称扫描变换，以进一步提高效率，在算法中，根据直线的几何特征而采用的二叉树搜索法，使其平均每点判断次数几乎与Bresenham算法相同，而其平均每点迭代次数去远小于Bresenham算法。

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.