基于像素链排序的直线绘制算法  

Line drawing algorithm based on sorting piXel chains

作　　者：朱晓林[1] 蔡勇[1] 张建生[2] 

机构地区：[1]西南科技大学计算机科学与技术学院,四川绵阳621010 [2]西南科技大学制造科学与工程学院,四川绵阳621010

出　　处：《计算机应用研究》2012年第3期1175-1177,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(10576027)

摘　　要：针对直线生成算法在直线斜率大于0.5时的低效率问题,提出一种基于像素链排序的直线绘制算法。将直线看做是由许多条平行像素链或对角像素链拼接而成,利用逆向生成直线的类Bresenham算法求得各像素链的长度,通过Bresenham算法生成相应直线的位移码对各像素链进行排序,一次判断生成一条像素链。仿真实验表明,基于像素链排序的直线绘制算法生成的直线与Bresenham算法生成的直线精度一致,且计算量显著减少。该算法只有加法和乘法两种整数运算,适合硬件实现,其绘制速度是Bresenham算法的4倍。In order to increase the low efficiency of the line drawing algorithm when the slope of the line is at 0.5 - 1, this paper proposed a line drawing algorithm based on sorting pixel chains. It treated a straight line as an aggregation of several horizontal pixel chains or diagonal ones. The attribute of a line and an algorithm of line drawing in a reverse direction ,which was similar to the Bresenham algorithm, were used to calculate the length of all the pixel chains. The algorithm sorted the pixel chains by the codes generated by Bresenham algorithm. It generated one pixel chains by one judgment. Simulation results show that the accuracy of straight line generated by new algorithm is as same as that generated by the Bresenham algorithm, and the computation is greatly reduced. The new algorithm only has two integer arithmetic, addition and multiplication, so it is suitable for hardware implementation.

关 键 词：计算机图形学 直线绘制算法 BRESENHAM算法 逆向生成直线 像素链 排序 整数运算 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]