圓的掃描轉(zhuǎn)換

圓與橢圓的生成第六講知識回顧掃描轉(zhuǎn)換將連續(xù)圖形以最小誤差近似于光柵網(wǎng)格點(diǎn)（離散化）的過程必要性要求直線的掃描轉(zhuǎn)換DDA算法Bresenham算法DDA算法直線方程y=kx+b增量思想xi+1=xi+1yi+1=yi+ky值是浮點(diǎn)數(shù)四舍五入運(yùn)算(xi+1

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

,yi+k)k算法改進(jìn)選點(diǎn)規(guī)則Bresenham算法——距離差——符號增量思想ENEdlowerP(xp,yp)Pnew(xp+1,yp+1)NEEdlowerdupperdupper內(nèi)容提要圓的掃描轉(zhuǎn)換中點(diǎn)圓算法Bresenham算法橢圓的掃描轉(zhuǎn)換中點(diǎn)橢圓算法問題圓的掃描轉(zhuǎn)換圓給定圓心位置和半徑圓的方程考慮圓心在原點(diǎn)的圓x2+y2=R2

圓的參數(shù)方程

一個像素寬x+x0,y+y0O(x0,y0)O(0,0)直接的掃描轉(zhuǎn)換方法利用圓的參數(shù)方程SetPixel(Round(x),Round(y),color)存在的問題需要調(diào)用三角函數(shù),涉及浮點(diǎn)運(yùn)算使用較小的能避免縫隙,但對不同的半徑難于確定不同的.直接的掃描轉(zhuǎn)換方法直接利用圓的方程四分之一圓x按單位步長變化

存在問題需要乘法、平方根及四舍五入運(yùn)算點(diǎn)間距不均勻，存在較大縫隙圓的八方向?qū)ΨQ性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)圓的八方向?qū)ΨQ性考慮45°圓弧(八分之一圓弧)半徑R為整數(shù)Fromx=0to?while(y>=x)45°圓的掃描轉(zhuǎn)換間距問題對稱性乘法、平方根及四舍五入運(yùn)算？乘法、平方根用于求y四舍五入用于確定y增0或-1直線的掃描轉(zhuǎn)換中點(diǎn)畫線法、Bresenham算法有兩個像素待選位置相對固定ENEPQM圓的掃描轉(zhuǎn)換算法最接近圓的像素序列x每次增1E、NE哪點(diǎn)離圓更近？中點(diǎn)算法Bresenham算法P(xp,yp)ESE45°中點(diǎn)圓算法標(biāo)記參照點(diǎn)——中點(diǎn)M候選像素E、SE位置判定P(xp,yp)ESEMMEMSE剛選中的像素選擇當(dāng)前像素選擇下一個像素中點(diǎn)圓算法判定標(biāo)準(zhǔn)中點(diǎn)M位于圓的哪一側(cè)M在圓內(nèi)取E點(diǎn)M在圓外取SE點(diǎn)M在圓上取SE點(diǎn)P(xp,yp)ESEMMSEME中點(diǎn)圓算法問題如何判定中點(diǎn)M與圓的位置關(guān)系？位置關(guān)系判別方法圓的隱式函數(shù)F(x,y)=x2+y2-R2=0

點(diǎn)和圓的位置判定F(x,y)=0——點(diǎn)在圓上F(x,y)>0——點(diǎn)在圓外F(x,y)<0——點(diǎn)在圓內(nèi)xon,yonxin,yinxout,yout判別方法判定變量d=F(M)=F(xp+1,yp-1/2)

d>0

M在圓外——取SE

d<0

M在圓內(nèi)——取E

d=0

M在圓上——E、NE均可取SEP(xp,yp)ESEMMSEME判定變量的變化d<0,取E點(diǎn)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點(diǎn)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循環(huán)初始化初始點(diǎn)P(0,R)中點(diǎn)M(1,R-1/2)判定變量dstart=F(M)=F(1,R-1/2)=5/4-R修正判定變量——整數(shù)運(yùn)算

h=d-1/4——d=h+1/4h=1-Rd<0——h<1/4——h<0M中點(diǎn)圓算法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); }}中點(diǎn)圓算法畫任意圓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); }}圓的八方向?qū)ΨQ性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);}算法演示中點(diǎn)畫圓算法演示Bresenham算法選點(diǎn)規(guī)則距離差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點(diǎn)——y不增d>0取SE點(diǎn)——y增-1d=0約定取SE點(diǎn)——y增-1P(xp,yp)ESEd1d2橢圓的掃描轉(zhuǎn)換如何生成橢圓？橢圓：圓心、長軸、短軸x2/a2+y2/b2=1橢圓的掃描轉(zhuǎn)換參照圓的掃描轉(zhuǎn)換算法相同之處中點(diǎn)技術(shù)不同之處八方向?qū)ΨQ性——四方向?qū)ΨQ性八分之一圓弧——四分之一橢圓弧分區(qū)域討論中點(diǎn)技術(shù)適用范圍兩個待選點(diǎn)位置相對固定兩個區(qū)域區(qū)域1：斜率在[-1，0]之間的部分|dy|≤|dx|：x每次走單位步長下一個像素點(diǎn)出現(xiàn)在對應(yīng)的E或SE的位置區(qū)域2：斜率小于-1的部分|dy|>|dx|：y每次走單位步長下一個像素點(diǎn)出現(xiàn)在對應(yīng)的S或SE的位置E區(qū)域1區(qū)域2SESES切線斜率=-1xy橢圓的掃描轉(zhuǎn)換如何確定分界點(diǎn)？x2/a2+y2/b2=1F(x,y)=b2x2+a2y2-a2b2=0If(2b2x≥2a2y)進(jìn)入?yún)^(qū)域2循環(huán)while(2b2x<2a2y)x++While(y>0)y++E區(qū)域1區(qū)域2SESES切線斜率=-1xy選點(diǎn)規(guī)則F(x,y)=b2x2+a2y2-a2b2=0M1M2構(gòu)造判定變量——區(qū)域1區(qū)域1當(dāng)前已選定點(diǎn)：P(xp,yp)x+1對應(yīng)中點(diǎn):M(xp+1,yp-1/2)判定變量d=F(M)d>0：取SE、y-1d=0：約定取SE、y-1d<0：取E、y不增M1M2ESE區(qū)域1問題增量法更新判定變量去浮點(diǎn)運(yùn)算增量法更新判定變量——區(qū)域1取E點(diǎn)當(dāng)前點(diǎn)P(xp,yp)M(xp+1,yp-1/2)d=(xp+1)2b2+(yp-1/2)2a2-a2b2取E點(diǎn)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區(qū)域1增量法更新判定變量——區(qū)域1取SE點(diǎn)當(dāng)前點(diǎn)P(xp,yp)M(xp+1,yp-1/2)d=(xp+1)2b2+(yp-1/2)2a2-a2b2取SE點(diǎn)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區(qū)域1判定變量初始化——區(qū)域1初始點(diǎn)P(0,b)M(1,b-1/2)d=b2+a2(-b+1/4)M1M2SSE構(gòu)造判定變量——區(qū)域2區(qū)域2當(dāng)前已選定點(diǎn)：P(xp,yp)y-1對應(yīng)中點(diǎn):M(xp+1/2,yp-1)判定變量d=F(M)d>0：取S、x不增d=0：約定取SE、x+1d<0：取SE、x+1M1M2SSE增量法更新判定變量——區(qū)域2取S點(diǎn)incrS=a2(