基于模式分解的快速直线生成算法  

A Fast Line Rasterization Algorithm Based on Pattern Decomposition

作　　者：牛连强[1] 邵中[1] 

机构地区：[1]沈阳工业大学软件学院,沈阳110023

出　　处：《计算机辅助设计与图形学学报》2010年第8期1286-1292,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：辽宁省科学技术计划项目(2007410003)

摘　　要：直线是图形系统中的基本元素,为了提高其生成效率,提出一种快速的直线绘制算法.该算法将直线视为由更大的模式而非像素组成,利用每个模式的最终误差代替Bresenham算法中的每次步进时候选像素点的y坐标差,在保持仅使用整数运算的前提下,每次运算和判定能够生成由一个或多个像素行组成的大模式,从而减少了运算次数和输出操作.此外,考虑了直线光栅化的弱对称性,并指出多种类型直线可不经中间运算而直接绘制的特殊性,有利于简化算法的设计复杂性并提高生成速度.理论分析和计算结果表明,文中算法比Bresenham算法的平均误差判定和累计次数减少10倍以上,平均生成速度提高了2.7倍.Straight line is the fundamental element in all graphics systems. A fast line rasterization algorithm is presented in this paper. A straight line is considered as composed of large patterns instead of individual pixels. The proposed algorithm ensures the accuracy of the generated line by checking the ultimate error of each pattern instead of the y coordinate difference at each candidate pixel. Since it generates a pattern consisting of one or more segments at each step, the times of operation and output involved in line drawing is reduced significantly. Besides, due to the weak symmetry between the raster compositions of various types of straight lines, some lines can be drawn directly without the intermediate operations, which simplifies the algorithm design and accelerates the line generation further. Theoretical analysis and implementation results show that the average computation for error judgment involved in this algorithm is 10 times less than that in Bresenham algorithm, and the average generation speed is increased by 2.7 times.

关 键 词：直线生成 整数运算 多点绘制 图形算法 模式 弱对称性 

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