光栅图形学试卷.ppt

包装计算机辅助设计
第三章光栅图形学
§ 直线的生成算法
一、数值微分法(DDA)

过起点Ps(xs , ys)和终点Pe(xe , ye)画一条直线段L,
直线的斜率为k,则:
从起点Ps开始,到Pe结束。x轴方向的步长为1个像
素,按y=kx+b计算相应的y坐标,并取像素点(x,round(y))
作为当前点的坐标。
§ 直线的生成算法

LineWithDDA(int xs, int ys, int xe, int ye, int color)
{
float x, y, delta_x, delta_y;
int dx, dy, steps, k;
dx = xe - xs;
dy = ye - ys;
if (fabs(dx) > fabs(dy))
steps = fabs(dx);
else
steps = fabs(dy);
§ 直线的生成算法
delta_x = (float)dx / (float)steps;
delta_y = (float)dy / (float)steps;
x=xs;
y=ys;
putpixel((int)x, (int)y, color);
for(k=0; k<steps; k++)
{ x + = delta_x;    y + = delta_y;    putpixel((int)(x + ), (int)(y + ), color);}
getch( );
}
§ 直线的生成算法

用DDA法扫描转换连接(0,0)和(5,2)两点的直线段。
x
(int)y1
y1 = y +
0
0
+
1
0
+
2
1
+
3
1
+
4
2
+
5
2
+
0
3
4
5
6
1
2
1
3
2
§ 直线的生成算法
二、中点画线法

当前像素点为P(xp,yp),则下一个像素点有两种选
择:P1(xp+1,yp)或P2(xp+1,yp+1)。M为P1与P2的中点,Q
为理想直线与x=xp+1的交点。
P1
P2
Q
M
P
P1
P2
M
P
Q
§ 直线的生成算法
当M在Q的上方时,应取P1为下一个像素点;当M在
Q的下方时,P2应为下一个像素点。当M与Q重合时,取
P1或P2为下一个像素点均可,约定取P2。
将起点为Ps(xs,ys)和终点Pe(xe,ye)的直线段L用如下
方程表示:F(x,y)= ax + by + c = 0。
其中,a = ys - ye,b = xe - xs ,c = xsye - xeys 。
F(M)= 0,M点在直线上,取P2 ;
F(M)> 0,M点在直线的上方,取P1 ;
F(M)< 0,M点在直线的下方,取P2 ;
§ 直线的生成算法
构造判别式:
d = F(M)= F(xp+1,yp+)= a(xp+1)+ b(yp+)+ c
若d>0 ,则取P1(xp+1,yp),判断下一个像素的位置
时,应计算d1=F(xp+2,yp+)=d+a,增量为a。
若d≤0 ,则取P2(xp+1,yp+1),判断下一个像素的位
置时,应计算d2=F(xp+2,yp+)=d+a+b,增量为a+b。
d的初值:
d0 = F(xs+1,ys+)= F(xs,ys)+ a + = a +
由于只用d的符号,且d的增量都是整数,可用2d来
代替d。
§ 直线的生成算法

LineWithMidPoint(int xs, int ys, int xe, int ye, int color)
{
int a, b, d1, d2, d, x, y;
a = ys - ye;
b = xe - xs;
d = 2*a + b;
d1 = 2*a;
d2 = 2*(a+b);
x=xs;
y=ys;
§ 直线的生成算法
putpixel(x, y, color);
while(x<xe)
{
if(d<0)
{
x=x+1;
y=y+1;
d=d+d2;
}
else
{
x=x+1;
d=d+d1;
}
putpixel(x, y, color);
}
getch( );
}