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

【Abstract】 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.更多还原