几种直线画法的比较

几种画直线的方法比较

李琳(09号)

(唐山师范学院计算机科学系,河北省唐山市063000)

摘要:直线是生成各种图形的基本元素, 直线绘制是光栅图形学最基本的一个任务。直线扫描转换生成算法是计算机图形学、计算机辅助设计、科学计算可视化、虚拟现实、计算机动画等领域最基本、最重要的算法之一。

关键字:Bresenham ,DDA

Comparison of several drawing a straight line

Li Lin

(Schoolof Computer Science and Technology,Tangshan Normal College, Tangshan Hebei 063000,China)

Abstract :The line is the basic element in generating graphics. So line drawing is a fundamental task for raster graphics. The line scan conversion generating algorithm is a very important and fundamenatal algorithm in Computer Graphics (CG)and Computer Aided Design (CAD),Visualization in Scientific Computing (VISC),Virtual Reality and Computer Animation.

Keywords:Bresenham ,DDA

直线是生成各种图形的基本元素, 直线绘制是光栅图形学最基本的一个任务。直线扫描转换生成算法是计算机图形学、计算机辅助设计、科学计算可视化、虚拟现实、计算机动画等领域最基本、最重要的算法之一。直线生成算法的好坏直接影响图形生成与显示的效率。因此, 提高和加速传统直线绘制算法具有重要的实际意义。本文简单介绍几种直线的画法和它们之间的比较。

1. Bresenham 算法

Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间,该方法类似于中点法,由一个误差项符号决定下一个象素点。算法原理如下:过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列的所求象素。如设直线方程为y i+1=y i +k (x i+1-x i )+k 。假设列坐标象素已经确定为x i ,其行坐标为y i 。那么下一个象素的列坐标为x i +1,而行坐标要么为y i ,要么递增1为y i +1。是否增1取决于误差项d 的值。误差项d 的初值d 0=0,x 坐标每增加1,d 的值相应递增直线的斜率值k ,即d =d +k 。一旦d ≥1,就把它减去1,这样保证d 在0、1之间。当d ≥0.5时,直线与垂线x =x i +1交点最接近于当前象素(x i ,y i ) 的右上方象素(x i +1,y i +1) ;而当d

Bresenham 画线算法程序:

void Bresenhamline (intx0,int y0,int x1, int y1,int color)

{int x, y, dx, dy;

float k, e;

dx =x1-x0;dy=y1-y0;k=dy/dx;

e=-0.5;x=x0,;y=y0;

for (i=0;i

{drawpixel (x,y, color);

x=x+1;e=e+k;

if (e 0)

{y++;e=e-1;}

}

}

上述Bresenham 算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号,因此可作如下替换:2*e *dx 。

2. DDA 算法

DDA 称为数值微分画线算法,是直线生成算法中最简单的一种。原理相当简单,就是最直观的根据斜率的偏移程度,决定是以x 为步进方向还是以y 为步进方向。然后在相应的步进方向上,步进变量每次增加一个像素,而另一个相关坐标变量则为Yk_1=Yk+m(以x 为步进变量为例,m 为斜率)。

DDA 画线算法程序:

void DDALine(floatx1,float y1,float x2,float y2,int color,HDC hdc)

{

float m; float dx,dy; float x,y;

x1=(int)(x1+0.5);

y1=(int)(y1+0.5);

x=x1;

dx=x2-x1;

else

while(x

{

SetPixel(hdc,x,y,color);

if(fabs(dx)>=dy)

{

else

{x=x+m;y++;}y=y+m;x++;}y=y1;dy=y2-y1;m=dy/dx;m=dx/dy;if(fabs(dx)>=fabs(dy))

}

}

3. 对称式八步增量算法

在分析直线生成模式与直线斜率之间的关系的基础上, 提出了一种对称式八步增量算法。该算法一次能画四个象素, 结合直线的对称性, 在一次循环中可以画八个象素。该算法只用到了整数加法运算、减法运算和左移位运算, 大大降低了硬件实现的复杂度, 同时有效地提高了速度, 易于硬件实现。与Bresenham 算法相比, 平均每点判断次数只相当于Bresenham 算法的30%,平均迭代次数相当于Bresenham 算法的25%。

此外还有四步画直线算法,五步直线扫描转换生成算法,六步直线生成算法等算法。其中Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法,DDA 算法是直线生成算法中最简单的一种,直线绘制速度最快的是对称式八步增量算法。

参考文献:

1. 作者欧阳开翠, 曾令华, 谭渊, 白宝钢,期刊计算机科学COMPUTER SCIENCE 2008年第

03期。

2. 王朝网络www.wangchao.net.com

3. 程序员开发网www.pudn.com


相关内容

  • 第四章 基本平面图形

    第四章 基本平面图形 §4.1线段.射线.直线 教学目标: 1.在现实情境中理解线段.射线.直线等简单图形 2.会说出线段.射线.直线的特征; 会用字母表示线段.射线.直线 3.通过操作活动,了解两点确定一条直线等事实,积累操作活动的经验, ...


  • 垂线的画法及应用

    <垂线的画法及应用>教学设计 单位:稼轩小学 姓名:王净 [教学内容]义务教育课程标准实验教科书 人教版数学四年级上册第五单元第二课时<垂线的画法及应用>. [教学分析]<垂线的画法及应用>是现行人教版义 ...


  • 机械制图教案 第三版 王幼龙

    绪论 一. 知识与技能 1. 了解本课程的任务.特点.主要内容和学习方法: 2. 了解图样在生产中的作用和地位,提高对课程重要性的认识,激发学习兴趣: 二. 学习方法和素质养成 1. 引导学生注重理论联系实际,勤于动手,反复实践,耐心细致, ...


  • 高中数学必修1-2知识框架

    高一数学知识框架 第一章 集合与函数概念 第二章 基本初等函数(I ) 必修二 立体几何 第一章 空间几何体 知识结构如下 画三视图的原则:长对齐.高对齐.宽相等 直观图:斜二测画法 斜二测画法的步骤: (1). 平行于坐标轴的线依然平行于 ...


  • 第3课时 平行线.垂线的画法 市中冯晨晨

    平行线.垂线的画法 教学内容:青岛版四年级上册58页 教学目标: 1掌握垂线和平行线的画法,并能灵活运用. 2 学会用直尺和三角板画平行线.垂线. 3在学习探索的过程中,培养学生的动手作图能力和良好的作图习惯. 4体会用联系的观点看问题. ...


  • [画垂线]说课稿

    <画垂线>说课稿 教学内容:人教版<义务教育课程标准实验教科书>小学数学四教材分析:<垂线的画法>位于小学数学四年级数学上册第四单年级上册第66-67页例2. 元<平行四边形和梯形>的第二课时 ...


  • 只用圆规所以精彩

    作者:顾香才 中学数学杂志 2007年12期 南京市2007年初中毕业学业考试数学最后一题,出其不意,以构图压轴,规定只用圆规,不用直尺.不过,考生的奇思妙想,精彩纷呈,本人有幸参与此题批阅,现摘其奇葩,与同仁分享,同时,将自己的思考奉上与 ...


  • 垂直的画法教案

    第二课时: 垂线的画法 教学内容:学习画垂线,书上第58页的例2. 教学目标: 知识与技能: 掌握垂线的画法, 会正确地画出已知直线的垂线. 过程与方法:经历画垂线的过程,体验类比和推理的方法. 情感态度与价值观:在学习活动中,培养学生的动 ...


  • 动漫人物画法(图 文)

    动漫人物画法(文+图) [脸][头发][面部表情][口.鼻][眼睛(男/女)][手] 1)不同角度脸部的基本画法 1. 首先画一个大的圆形,将其水平三等分 , 再用一条垂直线把它对半分开.水平线的间距不一定要十分准确,其 比例取决于你所想画 ...