计算机图形学ppt课件

能否采用增量算法呢？
P2 Q
P=(xp,yp) P1
.
分两种情形考虑再下一个像素的判定：
P2
若d≥0，中点M在直线上方，取正右方像素P1 (Xp+1,Yp)
M
– 再下一个像素的判别式为：
P1
d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c
= d+a d的增量为a
基本思想 假定直线的起点、终点分别为：（x0,y0), (x1,y1)， 且都为整数。 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L(P0,P1); 直线斜率为 k y1 y0 x1 x0 按照y=kx+b计算相应的y坐标。
.
数值微分(DDA)法
设步长为x，有xi+1 =xi + x
因(X0,Y0)在直线上， 所以F(X0,Y0)=0
= a(x0 +1)+b(y0 +0.5)+c
= F(x0, y0)+a+0.5b
= a+0.5b
由于只用d 的符号作判断，为了只包含整数运算,
可以用2d代替d来摆脱小数，提高效率。
优点：
– 只有整数运算，不含乘除法
– 可用硬件实现
.
中点画线法
y=y+k;
.
• 例：画直线段P0(0,0)--P1(5,2)
x
y+0.5
int(y+0.5 )
0
0+0.5
0
1
0.4+0.5
0
2
0.8+0.5
1
3
1.2+0.5
1
4
1.6+0.5
2
5
2.0+0.5
2
注意：网格点表示像素
Line: P0(0, 0)-- P1(5, 2) 3 2 1
算法特点:
0 12 3 4 5
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);
问题：现需判断距离理想直线最 近的下一个像素点。
.
算法原理
– 当M在Q的下方-> P2离直线更近更近->取P2 。 – M在Q的上方-> P1离直线更近更近->取P1 – M与Q重合， P1、P2任取一点。
如何判断M点在Q点上方还是在Q点下方？
ห้องสมุดไป่ตู้P2
Q
P=(xp,yp) P1
.
中点画线法
已知：线段两端点(x0,y0)，(x1,y1) 直线方程为： F(x,y)=ax+by+c=0
其中a=y0-y1, b=x1-x0, c=x0y1-x1y0
∴欲判断M点是在Q点上方还是在Q点下方， 只需把M代入F(x,y),并检查它的符号。
Fx, y0 Fx, y0 Fx, y0
点在直线上面 点在直线上方 点在直线下方
P2
Q M
P=(xp,yp) P1 .
中点画线法
构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d<0，M在直线(Q点)下方，取右上方P2； 当d>0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1；
优点：在同一坐标上,不可能连续停留两次。
缺点： 在此算法中，y、k必须是float，且每一步都必 须对y进行舍入取整，不利于硬件实现。
数值微分(DDA)法
增量算法：在一个迭代算法中，如果每一步的x、 y值是用前一步的值加上一个增量来获得，则称 为增量算法。DDA算法就是一个增量算法。
缺点
– 注意上述分析的算法仅适用于k ≤1的情形。在这种情 况下，x每增加1,y最多增加1。当 k 1时，必须把x， y地位互换，y每增加1，x相应增加1/k。
第二章 光栅图形学
2.1
直线段的扫描转换算法
2.2
圆弧的扫描转换算法
2.3
多边形的扫描转换与区域填充
2.4
字符
2.5
裁剪
2.6
反走样
2.7
消隐
.
2.1 直线段的扫描转换算法
• 数值微分法（DDA算法） • 中点画线法 • Bresenham画线算法
.
数值微分法（Digital Differential Analyzer ）
while (x<x1)
{ if (d<0) {x++; y++; d+=d2; }
else
{x++; d+=d1;}
drawpixel (x, y, color);
} /* while */
} /* mid PointLine */
.
• 例：用中点画线法P0(0,0) P1(5,2)
a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6
则yi+1= kxi+1+b= kxi+kx+b= yi+kx
因为光栅点的单位是1，对每一个x方向的增量x =1时; 有
yi+1 = yi+k 。即：当x每递增1，y递增k(即直线斜率)。
经过round()函数处理得到显示的光栅点(x,round(y))坐标。
。
xi+1 =xi+1
。。
yi+1= yi+k
(X i , Yi)
。
(X i+1 ,Yi + k)
(X i , Int(Yi +0.5))
栅格交点表示像素点位置
.
数值微分(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; xx1; x++) drawpixel (x, int(y+0.5), color);
若d＜0，中点M在直线下方，取右上方像素P2 (Xp+1,Yp+1) P2
– 再下一个像素的判别式为：
d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c
M
=d+a+b d的增量为a+b
P1
.
中点画线法
画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)
– 在此算法中，y、k必须是float，且每一步都必须对y进 行舍入取整，有浮点数取整运算,不利于硬件实现。
– 效率低
.
中点画线法
原理：
P2 Q
P=(xp,yp) P1
假定直线斜率0<K<1，且已确定 点像素点P（Xp ,Yp ）,则下一个 与直线最接近的像素只能是P1点 或P2点。设M为中点，Q为交点