基于未加权区域采样的直线反走样算法

毛峡; 刘运龙; 薛雨丽

基于未加权区域采样的直线反走样算法

北京航空航天大学电子信息工程学院, 北京 100191

基金项目: 国家自然科学基金资助项目(61103097); 中央高校基本科研业务费专项资金资助项目(YWF-12-LZGF-054)

详细信息

中图分类号: TP391.72
计量
- 文章访问数: 2380
- HTML全文浏览量: 282
- PDF下载量: 1387
- 被引次数: 0
出版历程
- 收稿日期: 2012-07-09
- 网络出版日期: 2013-06-30

New anti-aliasing straight line drawing algorithm based on unweighted area sampling

School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

摘要

摘要: 直线作为组成图形的基本元素,其生成方法一直是计算机图形学研究的基础内容之一.针对非垂直且非水平直线在光栅图形显示器存在的走样现象,结合经典的Bresenham算法和未加权区域采样思想,提出一种新的反走样直线生成算法.相比于传统的未加权区域采样以及Wu算法,该算法主要利用整数加减运算完成直线的反走样,计算简单,利于FPGA(Field Programmable Gate Array)硬件实现.仿真结果表明:新算法的仿真速度约为传统未加权区域采样的3倍,与Wu算法仿真速度相当;利用Wu算法生成的直线平滑性较好,但是沿着直线方向的某些相邻像素灰度值相差较大,而新算法生成的直线不但平滑效果好,而且沿直线方向相邻像素灰度值相差不大,因此,相比于Wu算法,新算法反走样效果更佳.
- 反走样 /
- Bresenham算法 /
- 未加权区域采样 /
- FPGA
Abstract: Line is a basic element of graphics. Its drawing algorithm is always one of the basic content of computer graphics research. In order to solve the aliasing phenomenon generated when drawing a non-vertical and non-horizontal straight line on a raster graphics monitor, based on Bresenham algorithm and the thought of the traditional unweighted area sampling algorithm, a new anti-aliasing straight line drawing algorithm was put forward. Compared to the traditional algorithm and the well-known Wu algorithm, the new algorithm principally used integer addition and subtraction to draw anti-aliasing straight lines. The calculation of the new algorithm was simple and the new algorithm could be easily implemented in FPGA hardware platform. Experimental results show that the simulation speed obtained by the new algorithm when drawing lines is nearly three times as fast as that obtained by the traditional algorithm and is almost equivalent to that obtained by Wu algorithm. Although the straight line generated by Wu algorithm has good smooth effect, along the straight line direction adjacent pixels- grey values sometimes have large difference. However, the new algorithm not only has good smooth effect, but also can find a good solution to solve the problem Wu algorithm has. Therefore, compared with Wu algorithm, the new algorithm-s anti-aliasing effect is much better.
- anti-aliasing /
- Bresenham algorithm /
- unweighted area sampling /
- field programmable gate array(FPGA)

HTML全文

参考文献(18)

[1]	Bresenham J E.Algorithms for computer control of a digital plotter[J].IBM Systems Journal,1965,4(1):25-30
[2]	李震霄,何援军.任意宽度直线的绘制与反走样[J].武汉大学学报,2006,39(4):130-133 Li Zhenxiao,He Yuanjun.Arbitrary width line generation and anti-aliasing[J].Journal of Wuhan University,2006,39(4):130-133(in Chinese)
[3]	孙家广,杨长贵.计算机图形学[M].北京:清华大学出版社,1998 Sun Jiaguang,Yang Changgui.Computer graphics[M].Beijing:Tsinghua University Press,1998(in Chinese)
[4]	牛连强,张丹,陶峰.直线的光栅转换算法与快速反走样绘制技术[J].沈阳工业大学学报,2012,34(1):73-78 Niu Lianqiang,Zhang Dan,Tao Feng.Raster-conversion algorithm and fast anti-aliased drawing technique for line[J].Journal of Shenyang University of Technology,2012,34(1):73-78(in Chinese)
[5]	沈强,张波,陈淑珍,等.计算机图形学反走样技术及实现[J].武汉大学学报,1997,43(1):113-118 Shen Qiang,Zhang Bo,Chen Shuzhen,et al.Antialiasing technique and applications in computer graphics[J].Journal of Wuhan University,1997,43(1):113-118(in Chinese)
[6]	杭后俊,付勇. 一种基于加权区域采样的直线反走样生成算法[J].计算机技术与发展,2009,19(6):138-141 Hang Houjun,Fu Yong.One antialiasing algorithm based on weighting region sampling[J].Computer Technology and Development,2009,19(6):138-141(in Chinese)
[7]	Wu Xiaolin,Rokne J G.Double-step incremental generation of lines and circles[J].Computer Vision,Graphics and Image Processing,1987,37( 3):331-344
[8]	Wu X.An efficient anti-aliasing technique [J].Computer Graphics,1991,25(4):143-152
[9]	孔令德.基于面积加权反走样算法的研究[J].工程图学学报,2009,4:49-54 Kong Lingde.Research on area-weighted antialiasing algorithm[J].Journal of Engineering Graphics,2009,4:49-54(in Chinese)
[10]	娄剑涛,王秀和.基于对称的反走样直线生成算法[J].计算机工程与应用,2011,47(1):173-175 Lou Jiantao,Wang Xiuhe.Anti-aliasing line drawing algorithm based on symmetry[J].Computer Engineering and Applications,2011,47(1):173-175(in Chinese)
[11]	袁一鸣,段凤阳,李赞平.罗盘仪表绘制中快速反走样算法的研究[J].舰船电子工程,2011,31(9):60-62 Yuan Yiming,Duan Fengyang,Li Zanping.Research on fast anti-aliasing algorithm in compass display[J].Ship Electronic Engineering,2011,31(9):60-62(in Chinese)
[12]	张鹏,王良.嵌入式图像系统的改进Bresenham反走样算法的应用[J].电子设计工程,2011,19(4):117-119 Zhang Peng,Wang Liang.Application of improved Bresenham anti-aliasing algorithm based on embedded image system[J].Electronic Design Engineering,2011,19(4):117-119(in Chinese)
[13]	薛斌党,姜志国,周孝宽.共聚焦三维数据表面重建的一种反走样方法[J].北京航空航天大学学报,2005,31(10):1054-1057 Xue Bindang,Jiang Zhiguo,Zhou Xiaokuan.Anti-aliasing technique for surface reconstruction of confocal data[J].Journal of Beijing University of Aeronautics and Astronautics,2005,31(10):1054-1057(in Chinese)
[14]	梅洋,李霖,贺彪.基于边界反走样算法的地图可视化研究[J].武汉大学学报,2008,33(7):759-761 Mei Yang,Li Lin,He Biao.Cartographic visualization based on boundary anti-aliasing[J].Journal of Wuhan University,2008,33(7):759-761(in Chinese)
[15]	邓术军,郭建星.一种适合于地图出版符号的反走样算法研究[J].武汉大学学报,2005,30(12):1120-1123 Deng Shujun,Guo Jianxing.An anti-aliasing algorithm suitable to map publishing symbol[J].Journal of Wuhan University,2005,30(12):1120-1123(in Chinese)
[16]	Foley J D.计算机图形学导论[M].北京:机械工业出版社,2004 Foley J D.Introduction to computer graphics[M].Beijing:China Machine Press,2004(in Chinese)
[17]	Li Xiang,Shao Xiaoyan.Fast line drawing algorithm by circular subtraction based on Bresenham[J].Proceeding of SPIE,2012,83490L:1-6
[18]	Norbert Spie,Michael Zapf,Nicole V Ruiter.Evaluation of the Bresenham algorithm for image reconstruction with ultrasound computer tomography[J].Proceeding of SPIE,2011,796803:1-9