圆的扫描转换

圆与椭圆的生成第六讲知识回顾扫描转换将连续图形以最小误差近似于光栅网格点（离散化）的过程必要性要求直线的扫描转换DDA算法Bresenham算法DDA算法直线方程y=kx+b增量思想xi+1=xi+1yi+1=yi+ky值是浮点数四舍五入运算(xi+1

,round(yi+k))(xi,round(yi))(xi,yi)(xi+1

,yi+k)k算法改进选点规则Bresenham算法——距离差——符号增量思想ENEdlowerP(xp,yp)Pnew(xp+1,yp+1)NEEdlowerdupperdupper内容提要圆的扫描转换中点圆算法Bresenham算法椭圆的扫描转换中点椭圆算法问题圆的扫描转换圆给定圆心位置和半径圆的方程考虑圆心在原点的圆x2+y2=R2

圆的参数方程

一个像素宽x+x0,y+y0O(x0,y0)O(0,0)直接的扫描转换方法利用圆的参数方程SetPixel(Round(x),Round(y),color)存在的问题需要调用三角函数,涉及浮点运算使用较小的能避免缝隙,但对不同的半径难于确定不同的.直接的扫描转换方法直接利用圆的方程四分之一圆x按单位步长变化

存在问题需要乘法、平方根及四舍五入运算点间距不均匀，存在较大缝隙圆的八方向对称性voidCirclePoints(intx,inty,COLORREFcolor){ SetPixel(x,y,color); SetPixel(y,x,color);SetPixel(-y,x,color); SetPixel(x,-y,color); SetPixel(-x,-y,color); SetPixel(-y,-x,color); SetPixel(y,-x,color); SetPixel(-x,y,color);}(x,y)(-x,y)(y,x)(-y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)圆的八方向对称性考虑45°圆弧(八分之一圆弧)半径R为整数Fromx=0to?while(y>=x)45°圆的扫描转换间距问题对称性乘法、平方根及四舍五入运算？乘法、平方根用于求y四舍五入用于确定y增0或-1直线的扫描转换中点画线法、Bresenham算法有两个像素待选位置相对固定ENEPQM圆的扫描转换算法最接近圆的像素序列x每次增1E、NE哪点离圆更近？中点算法Bresenham算法P(xp,yp)ESE45°中点圆算法标记参照点——中点M候选像素E、SE位置判定P(xp,yp)ESEMMEMSE刚选中的像素选择当前像素选择下一个像素中点圆算法判定标准中点M位于圆的哪一侧M在圆内取E点M在圆外取SE点M在圆上取SE点P(xp,yp)ESEMMSEME中点圆算法问题如何判定中点M与圆的位置关系？位置关系判别方法圆的隐式函数F(x,y)=x2+y2-R2=0

点和圆的位置判定F(x,y)=0——点在圆上F(x,y)>0——点在圆外F(x,y)<0——点在圆内xon,yonxin,yinxout,yout判别方法判定变量d=F(M)=F(xp+1,yp-1/2)

d>0

M在圆外——取SE

d<0

M在圆内——取E

d=0

M在圆上——E、NE均可取SEP(xp,yp)ESEMMSEME判定变量的变化d<0,取E点dold=F(xp+1,yp-1/2)=(xp+1)2+(yp-1/2)2-R2Pnew(xp+1,yp)M(xp+2,yp-1/2)dnew=F(xp+2,yp-1/2)=(xp+2)2+(yp-1/2)2-R2dnew=dold+2xp+1+1

incrE=2xp+1+1MPold(xp,yp)ESEMPnew(xp+1,yp)ESE判定变量的变化

d≥0,取SE点dold=F(xp+1,yp-1/2)=(xp+1)2+(yp-1/2)2-R2Pnew(xp+1,yp-1)M(xp+2,yp-3/2)

dnew=F(xp+2,yp-3/2)=(xp+2)2+(yp-3/2)2-R2

dnew=

dold+2xp-2yp+5△SE=2xp+1-2yp+1+1P(xp,yp)ESEMMPnew(xp+1,yp-1)ESE循环初始化初始点P(0,R)中点M(1,R-1/2)判定变量dstart=F(M)=F(1,R-1/2)=5/4-R修正判定变量——整数运算

h=d-1/4——d=h+1/4h=1-Rd<0——h<1/4——h<0M中点圆算法VoidMidpointCircle(intradius,COLORREFcolor){ intx=0;y=radius;d=1-radius; CirclePoints(x,y,color); while(y>=x){ if(d<0)d+=2*x+3; /*选择E*/ else{ d+=2*(x-y)+5; /*选择SE*/ y--; } x++; CirclePoints(x,y,color); }}中点圆算法画任意圆VoidMidpointCircle(intxc,intyc,intradius,COLORREFcolor){ intx=0;y=radius;d=1-radius; CirclePoints(xc,yc,x,y,color); while(y>x){ if(d<0)d+=2*x+3; /*选择E*/ else{ d+=2*(x-y)+5; /*选择SE*/ y--; } x++; CirclePoints(xc,yc,x,y,color); }}圆的八方向对称性voidCirclePoints(intxc,intyc,intx,inty,COLORREFcolor){ SetPixel(xc+x,yc+y,color); SetPixel(xc+y,yc+x,color);SetPixel(xc-y,yc+x,color); SetPixel(xc+x,yc-y,color); SetPixel(xc-x,yc-y,color); SetPixel(xc-y,yc-x,color); SetPixel(xc+y,yc-x,color); SetPixel(xc-x,yc+y,color);}算法演示中点画圆算法演示Bresenham算法选点规则距离差d1=(xp+1)2+yp2-r2d2=r2-(xp+1)2-(yp-1)2d1

-d2=2(xp+1)2+yp2+(yp-1)2-2r2判定变量d=d1

-d2P(xp,yp)ESEd1d2Bresenham算法d<0取E点——y不增d>0取SE点——y增-1d=0约定取SE点——y增-1P(xp,yp)ESEd1d2椭圆的扫描转换如何生成椭圆？椭圆：圆心、长轴、短轴x2/a2+y2/b2=1椭圆的扫描转换参照圆的扫描转换算法相同之处中点技术不同之处八方向对称性——四方向对称性八分之一圆弧——四分之一椭圆弧分区域讨论中点技术适用范围两个待选点位置相对固定两个区域区域1：斜率在[-1，0]之间的部分|dy|≤|dx|：x每次走单位步长下一个像素点出现在对应的E或SE的位置区域2：斜率小于-1的部分|dy|>|dx|：y每次走单位步长下一个像素点出现在对应的S或SE的位置E区域1区域2SESES切线斜率=-1xy椭圆的扫描转换如何确定分界点？x2/a2+y2/b2=1F(x,y)=b2x2+a2y2-a2b2=0If(2b2x≥2a2y)进入区域2循环while(2b2x<2a2y)x++While(y>0)y++E区域1区域2SESES切线斜率=-1xy选点规则F(x,y)=b2x2+a2y2-a2b2=0M1M2构造判定变量——区域1区域1当前已选定点：P(xp,yp)x+1对应中点:M(xp+1,yp-1/2)判定变量d=F(M)d>0：取SE、y-1d=0：约定取SE、y-1d<0：取E、y不增M1M2ESE区域1问题增量法更新判定变量去浮点运算增量法更新判定变量——区域1取E点当前点P(xp,yp)M(xp+1,yp-1/2)d=(xp+1)2b2+(yp-1/2)2a2-a2b2取E点PE(xp+1,yp)ME(xp+2,yp-1/2)dE=(xp+2)2b2+(yp-1/2)2a2-a2b2incrE=dE-d=b2(2xp+3)M1M2ESE区域1增量法更新判定变量——区域1取SE点当前点P(xp,yp)M(xp+1,yp-1/2)d=(xp+1)2b2+(yp-1/2)2a2-a2b2取SE点PSE(xp+1,yp-1)MSE(xp+2,yp-3/2)dSE=(xp+2)2b2+(yp-3/2)2a2-a2b2incrSE=dSE-d=b2(2xp+3)-2a2(2yp-1)M1M2ESE区域1判定变量初始化——区域1初始点P(0,b)M(1,b-1/2)d=b2+a2(-b+1/4)M1M2SSE构造判定变量——区域2区域2当前已选定点：P(xp,yp)y-1对应中点:M(xp+1/2,yp-1)判定变量d=F(M)d>0：取S、x不增d=0：约定取SE、x+1d<0：取SE、x+1M1M2SSE增量法更新判定变量——区域2取S点incrS=a2(