当前位置:首页 >> >>

第03部分_计算机图形学_直线段扫描转换_060309

直线段的扫描转换
Ray
ray@mail.buct.edu.cn

2011-5-11

李辉 副教授

内容
光栅图形 直线的扫描转换
– 数值微分法(DDA) – 中点画线法 – Bresenham算法

2011-5-11

第3部分 直线段的扫描转换

第2页

光栅图形
光栅图形
– 光栅显示器上显示的图形,称之为光栅图形

光栅显示器
– 可以看作是一个象素矩阵,在光栅显示器上显示的任何一个 图形,实际上都是一些具有一种或多种颜色和灰度象素的集 合。 – 对一个具体的光栅显示器来说,象素个数是有限的,象素的 颜色和灰度等级也是有限的,象素是有大小的,所以光栅图 形只是近似的实际图形。 – 如何使光栅图形最完美地逼近实际图形,便是光栅图形学要 研究的内容。
2011-5-11 第3部分 直线段的扫描转换 第3页

图形的扫描转换
– 确定最佳逼近图形的象素集合,并用指定的颜色和 灰度设置象素的过程称为图形的扫描转换或光栅化。

光栅化问题
– 对于一维图形,在不考虑线宽时,用一个象素宽的 直线或曲线来显示图形。 – 二维图形的光栅化必须确定区域对应的象素集,将 各个象素设置成指定的颜色和灰度,也称之为区域 填充。
2011-5-11 第3部分 直线段的扫描转换 第4页

– 图形光栅化后,显示在屏幕上的一个窗口里,超出 窗口的部分不予显示。确定一个图形的哪些部分在 窗口内,必须显示;哪些部分落在窗口之外,不予 显示,这需要对图形进行裁剪。 – 在光栅图形中,非水平和垂直的直线用象素集合表 示时,会呈锯齿状,这种现象称之为走样;用于减 少或消除走样的技术称为反走样。

2011-5-11

第3部分 直线段的扫描转换

第5页

直线的扫描转换
直线
– 数学上的直线是没有宽度、由无数个点构成的集合。 – 光栅显示器只能近似地显示直线。

直线的扫描转换
– 当我们对直线进行光栅化时,需要在显示器有限个象素中, 确定最佳逼近该直线的一组象素,并且按扫描线顺序,对这 些象素进行写操作,这个过程称为直线的扫描转换。
? 数值微分法(DDA) ? 中点画线法 ? Bresenham算法

2011-5-11

第3部分 直线段的扫描转换

第6页

数值微分法(DDA)
分析
–设过端点P0(x0 ,y0)、P1(x1 ,y1)的直线段为 L(P0 ,P1), y1 ? y0 – 斜率
k = x1 ? x0

– L的起点P0的横坐标x0向L的终点P1的横坐标x1步进, 取步长=1(个象素),用L的直线方程y=kx+b计算相 应的y坐标,并取象素点(x,round(y))作为当前点的 坐标。
第3部分 直线段的扫描转换 第7页

2011-5-11

yi+1=kxi+1+b =kxi+b+k?x =yi+k?x –当?x =1时yi+1 = yi+k。 – 也就是说,当x每递增1,y递增k(即直线斜率)。

2011-5-11

第3部分 直线段的扫描转换

第8页

DDA画线算法程序
void DDALine(int x0,int y0,int x1,int y1,int color) { int x; float dx, dy, y, k; dx = x1-x0; dy=y1-y0; k=dy/dx;y=y0; for (x=x0;x< x1;x++) { drawpixel (x, int(y+0.5), color); y=y+k; }
2011-5-11 第3部分 直线段的扫描转换 第9页

举例
–连接两点P0(0,0)和P1(5,2)的直线段
x 0 1 2 3 4 int(y+0.5) 0 0 1 1 2 y+0.5 0 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5
0 1 2 3 4 5 3 2 1

2011-5-11

第3部分 直线段的扫描转换

第10页

算法分析
–上述分析的算法仅适用于|k| ≤1的情形。 –在这种情况下,x每增加1,y最多增加1。 –当 |k| > 1时,必须把x,y地位互换,y每增加1,x相 应增加1/k。 –在这个算法中,y与k必须用浮点数表示,而且每一 步都要对y进行四舍五入后取整,这使得它不利于硬 件实现。

2011-5-11

第3部分 直线段的扫描转换

第11页

中点画线法
分析
–假定直线斜率k在0~1之间,当前象素点为(xp,yp), 则下一个象素点有两种可选择点
? P1(xp+1,yp)或P2(xp+1,yp+1)。

–设P1与P2的中点(xp+1,yp+0.5)称为M,Q为直线 与x=xp+1垂线的交点。 –当M在Q的下方时, P2 则取P2应为下一个象素点; Q –当M在Q的上方时, M 则取P1为下一个象素点。 P=(xp,yp) P1
2011-5-11 第3部分 直线段的扫描转换 第12页

–过点(x0,y0)、(x1, y1)的直线段L的方程式为
? F(x, y)=ax+by+c=0 ? 其中,a=y0-y1, b=x1-x0, c=x0y1-x1y0,

–欲判断中点M在Q点的上方还是下方,只要把M代入 F(x,y),并判断它的符号即可。 –为此,我们构造判别式:
? ? ? ?
2011-5-11

d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 当d<0时,M在L(Q点)下方,取P2为下一个象素; 当d>0时,M在L(Q点)上方,取P1为下一个象素; 当d=0时,选P1或P2均可,约定取P1为下一个象素。
第3部分 直线段的扫描转换 第13页

– d是xp, yp的线性函数,可采用增量计算,提高运算 效率。 –若当前象素处于d>=0情况,则取正右方象素 P1(xp+1, yp),要判再下一个象素位置,应计算
? d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a ? 增量为a

–若d<0时,则取右上方象素P2(xp+1, yp+1)。要判断 再下一象素,则要计算
? d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ? 增量为a+b
2011-5-11 第3部分 直线段的扫描转换 第14页

–画线从(x0, y0)开始,d的初值
? d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b ? 因为 F(x0, y0)=0,所以d0=a+0.5b

–由于我们使用的只是d的符号,而且d的增量都是整 数,只是初始值包含小数。因此,可以用2d代替d 来摆脱小数。

2011-5-11

第3部分 直线段的扫描转换

第15页

中点画线法算法程序:
void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y; a=y0-y1; b=x1-x0;d=2*a+b; d1=2*a;d2=2* (a+b); x=x0;y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++;y++; d+=d2; } else {x++; d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */
2011-5-11 第3部分 直线段的扫描转换 第16页

举例
–用中点画线方法扫描转换连接两点P0(0,0)和P1 (5,2)的直线段。
3

x 0 1 2 3 4
2011-5-11

y 0 0 1 1 2

d 1 -3 3 -1 5
第3部分 直线段的扫描转换 第17页

2 1 0 1 2 3 4 5

Bresenham算法
分析
–设直线方程为
? yi+1=yi+k(xi+1-xi)+k
d d d d

–下一个象素的列坐标为xi+1,而行坐标要么为yi, 要么递增1为yi+1。 –误差项d的初值d0=0,x坐标每增加1,d的值相应递 增直线的斜率值k,即d=d+k。 –是否增1取决于误差项d的值。

2011-5-11

第3部分 直线段的扫描转换

第18页

–一旦d≥1,就把它减去1,这样保证d在0、1之间。 –当d≥0.5时,直线与垂线x=xi+1交点最接近于当前 象素(xi,yi)的右上方象素(xi+1,yi+1) –当d<0.5时,更接近于右方象素(xi+1,yi)。 –为方便计算,令e=d-0.5,e的初值为-0.5,增量 为k。当e≥0时,取当前象素(xi,yi)的右上方象素 (xi+1,yi+1);而当e<0时,取(xi,yi)右方象素(xi +1,yi)。

2011-5-11

第3部分 直线段的扫描转换

第19页

Bresenham画线算法程序:
void Bresenhamline (int x0,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<dx;i++) { drawpixel (x, y, color); x++;e+=k; if (e>=0) { y++; e=e-1;} } }
2011-5-11 第3部分 直线段的扫描转换 第20页

举例
–用Bresenham方法扫描转换连接两点P0(0,0)和 P1(5,2)的直线段。
x 0 1 2 3 4 5
2011-5-11

y 0 0 1 1 2 2

e -0.5 -0.1 -0.7 -0.3 -0.9 -0.5
第3部分 直线段的扫描转换 第21页

3 2 1 0 1 2 3 4 5

改进
– 前面的Bresenham算法在计算直线斜率与误差项时 用到小数与除法。 –可以改用整数以避免除法。 –由于算法中只用到误差项的符号,因此可将误差项 替换为:
2*e*dx

2011-5-11

第3部分 直线段的扫描转换

第22页

改进后的Bresenham算法程序
void InterBresenhamline (int x0,int y0,int x1, int y1,int color) { dx = x1-x0,;dy = y1- y0,;e=-dx; x=x0 x=x0; y=y0; for (i=0; i<dx; i++) {drawpixel (x, y, color); x++; e=e+2*dy; if (e>=0) { y++; e=e-2*dx;} } }

2011-5-11

第3部分 直线段的扫描转换

第23页


更多相关标签: