扫描转换圆弧 生成圆弧的中点算法 考虑对象:第二个八分圆, 第一象限的八分之一圆弧 (x,y) P PIE M x2+1,y1+1) P2 SE x=万2x=石2+ 北大计算机系多媒体与人机交互 16
北大计算机系多媒体与人机交互 16 扫描转换圆弧 • 生成圆弧的中点算法 – 考虑对象：第二个八分圆， 第一象限的八分之一圆弧 P P1 P2
(,x)P E 扫描转换圆弧x (x2+1,y1+) P2 X=万X=x 问题:与直线情形类似 圆弧的隐函数 :F(X,Y)=X2+Y2-R2=0 切线斜率min[-1,0 中点M=(Xp+1Yp0.5) 当F(M)<0时,M在圆内,说明P1距离圆弧更近,取P1 当F(M)>0时,P取P2 北大计算机系多媒体与人机交互 17
北大计算机系多媒体与人机交互 17 扫描转换圆弧 • 问题：与直线情形类似 • 圆弧的隐函数：F(X,Y)=X2+Y2 -R2=0 切线斜率m in [-1,0] • 中点 M=(Xp+1,Yp-0.5), 当F(M)＜0时，M在圆内，说明P1距离圆弧更近，取P1； 当F(M)＞0时，P取P2 P2 P P1
扫描转换圆弧 构造判别式 d=F(M)=F(Xp+1,Yp-0.5=(Xp+1)2+(Yp-0.5)2-R2 1)若d<0,取P1,再下一个象素的判别式为: dl=F(Xp+2,Yp-0.5)=d+2xp+3, 沿正右方向,d的增量为2Xp+3; 2)若d≥0,取P2,再下一个象素的判别式为 d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2) 沿右下方向,d的增量为2(Xp-Yp)+5 d的初始值(在第一个象素(0,R)处), d0=F(1,R05)=1.25-R 算法中有浮点数,用e=d-0.25代替 北大计算机系多媒体与人机交互 18
北大计算机系多媒体与人机交互 18 • 构造判别式 d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1) 2+(Yp-0.5) 2 -R2 1）若d＜0，取P1，再下一个象素的判别式为： d1=F(Xp+2,Yp-0.5)=d+2Xp+3， 沿正右方向，d的增量为2Xp+3； 2）若d≥0，取P2，再下一个象素的判别式为： d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2) 沿右下方向，d的增量为2(Xp-Yp)+5 • d的初始值(在第一个象素(0,R)处), d0=F(1, R-0.5)=1.25-R • 算法中有浮点数，用e=d-0.25代替 扫描转换圆弧
所以:初始化运算d0=1.25-R对应于e0=1-R 判别式d<0对应于e<-0.25 又因为:e的初值e0为整数,运算过程中的分量也为整数, 故e始终为整数 所以:e<-0.25等价于e<0 程序如下(完全用整数实现): while(x<y) Midpointcircle(r, color) f if(d<0 Intr. color d+=2*x+3,x++;} int x,y, d {d+=2*(Xy)+5; X+十 x=0,y=r;d=1-r; putpixcel (x,y, color) putpixcel(x, y, color) 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 19 所以：初始化运算d0 = 1.25 – R 对应于 e 0= 1- R 判别式 d < 0 对应于 e < -0.25 又因为：e的初值e0为整数，运算过程中的分量也为整数， 故e始终为整数 所以： e < -0.25 等价于 e < 0 程序如下（完全用整数实现）： MidpointCircle(r,color) Int r, color; { int x,y,d; x = 0; y = r; d = 1-r; putpixcel(x,y,color); while( x < y) { if (d <0) { d += 2*x+3; x++; } else { d += 2*(x-y)+5; x++ ; y--; } putpixcel(x,y,color); } }
椭圆的扫描转换 上部分 下部分N (x,y)=b2x2+a2y2-a2b2=0 椭圆的对称性,只考虑第一象限椭圆弧 生成,分上下两部分,以切线斜率为-1 的点作为分界点 椭圆上一点处的法向: N(x2y)=(F)xi+(F)’yj 2b2xi+ 2aly j 北大计算机系多媒体与人机交互 20
北大计算机系多媒体与人机交互 20 椭圆的扫描转换 • F(x,y)=b2x 2+a2y 2 -a 2b 2=0 • 椭圆的对称性，只考虑第一象限椭圆弧 生成，分上下两部分，以切线斜率为-1 的点作为分界点。 • 椭圆上一点处的法向： N(x,y) = (F)’x i + (F)’y j = 2b 2 x i + 2a 2 y j