計(jì)算機(jī)圖形學(xué)(圓弧的掃描轉(zhuǎn)換II)

1、計(jì)算機(jī)圖形學(xué)第3章 基本光柵圖形算法圓弧的掃描轉(zhuǎn)換正負(fù)法正負(fù)法中點(diǎn)法中點(diǎn)法Bresenham算法算法多邊形迫近法多邊形迫近法圓與橢圓圓與橢圓22014-2015-1:CG:SCUECDDA法法v 基本原理基本原理 設(shè)與當(dāng)前圓周最近的像素設(shè)與當(dāng)前圓周最近的像素點(diǎn)是點(diǎn)是Pi-1(xi-1,yi-1) 下一個(gè)與圓周最近的像素下一個(gè)與圓周最近的像素點(diǎn)只能是正右方的點(diǎn)點(diǎn)只能是正右方的點(diǎn) Hi(xi-1+1,yi-1)或者是右下方或者是右下方的點(diǎn)的點(diǎn)Li(xi-1+1,yi-1-1)3生成圓弧之Bresenham算法 記記D(Hi) = (xi-1+1)2+yi-12-R2, D(Li) = (xi-1+

2、1)2+(yi-1-1)2-R2 令判別式令判別式Di = |D(Hi)| - |D(Li)| ，然后根據(jù)，然后根據(jù)Di的正負(fù)來(lái)的正負(fù)來(lái) 判斷下一個(gè)像素點(diǎn)是取判斷下一個(gè)像素點(diǎn)是取Hi 點(diǎn)還是點(diǎn)還是Li 點(diǎn)點(diǎn) 若若Di0, D(Li) 0，D(Li) 0，有，有 Di = | D(Hi) |-| D(Li) | = D(Hi) + D(Li) = div 考察圓穿越不同區(qū)域時(shí)考察圓穿越不同區(qū)域時(shí)di的符號(hào)與的符號(hào)與Di的符號(hào)是否一致的符號(hào)是否一致 圓穿越圓穿越區(qū)域時(shí)，區(qū)域時(shí)，D(Hi) 0，D(Li) 0，有，有 Di = | D(Hi) |-| D(Li) | 0，di= D(Hi) + D(

3、Li) 0，D(Li) 0，有，有 Di = | D(Hi) |-| D(Li) | 0，di= D(Hi) + D(Li) 0 圓穿越圓穿越區(qū)域時(shí)，區(qū)域時(shí)，D(Hi) = 0，D(Li) 0，D(Li) = 0，有，有 Di = | D(Hi) |-| D(Li) | = D(Hi) = div 結(jié)論：結(jié)論： di的符號(hào)與的符號(hào)與Di的符號(hào)是一致的的符號(hào)是一致的62014-2015-1:CG:SCUECv 若若di 0，表示表示Hi點(diǎn)更接近圓點(diǎn)更接近圓周周，點(diǎn)亮，點(diǎn)亮Hi(xi-1+1,yi-1)，下一，下一個(gè)像素是取個(gè)像素是取Hi+1還是還是Li+1，應(yīng)，應(yīng)計(jì)算如下的判別式計(jì)算如下的判別式

4、:7v di = D(Hi)+D(Li) = (xi-1+1)2+yi-12-R2+(xi-1+1)2+(yi-1-1)2-R2判別式di的增量計(jì)算di+1 = D(Hi+1)+D(Li+1) = (xi-1+1+1)2+yi-12-R2+(xi-1+1+1)2+(yi-1-1)2-R2 = D(Hi)+2xi-1+3+D(Li)+2xi-1+3 = di+4xi-1+62014-2015-1:CG:SCUECv 若若di 0，表示表示Li點(diǎn)更接近圓點(diǎn)更接近圓周周，點(diǎn)亮，點(diǎn)亮Li(xi-1+1,yi-1-1)，下，下一個(gè)像素是取一個(gè)像素是取Hi+1還是還是Li+1，應(yīng)計(jì)算如下的判別式應(yīng)計(jì)算如下

5、的判別式:判別式di的增量計(jì)算8v di = D(Hi)+D(Li) = (xi-1+1)2+yi-12-R2+(xi-1+1)2+(yi-1-1)2-R2di+1 = D(Hi+1)+D(Li+1) = (xi-1+1+1)2+(yi-1-1)2-R2+(xi-1+1+1)2+(yi-1-1-1)2-R2 = D(Hi)+2(xi-1-yi-1)+4+D(Li)+2(xi-1-yi-1)+6 = di+4(xi-1-yi-1)+102014-2015-1:CG:SCUECv判別式判別式di的初始值的初始值=? 911122222200002222D(H )D(L )(1)R (1)(1)R

6、1RR 1(R1)R 32Rdxyxy判別式di的增量計(jì)算2014-2015-1:CG:SCUEC x0=0, y0=R d1 =32*R 當(dāng)當(dāng)di 0時(shí)時(shí) xi= xi-1+1 di+1=di+ 4xi-1+6 當(dāng)當(dāng)di0時(shí)時(shí) xi= xi-1+1，yi= yi-1-1 di+1=di+4(xi-1-yi-1)+10void bresenham_arc(int R, int color)int x,y,d;x=0; y=R;d=3-2*R;while(xy)DrawPixel(x,y,color);if (d0點(diǎn)亮點(diǎn)(x3,y3)=(3,4)按45 線對(duì)稱翻轉(zhuǎn)按X軸對(duì)稱翻轉(zhuǎn)按Y軸對(duì)稱翻轉(zhuǎn) B

7、resenham算法畫(huà)圓舉例112014-2015-1:CG:SCUEC正負(fù)法與Bresenham算法比較 v正負(fù)法主要用于筆式繪圖儀中，以迎合繪圖正負(fù)法主要用于筆式繪圖儀中，以迎合繪圖 儀只有水平和垂直方向的運(yùn)動(dòng)。每次選出的儀只有水平和垂直方向的運(yùn)動(dòng)。每次選出的下一個(gè)像素并不一定是離圓弧最近的像素點(diǎn)下一個(gè)像素并不一定是離圓弧最近的像素點(diǎn)vBresenham算法在候選的兩個(gè)像素中，總是算法在候選的兩個(gè)像素中，總是選定離圓弧最近的像素為圓弧的一個(gè)近似點(diǎn)，選定離圓弧最近的像素為圓弧的一個(gè)近似點(diǎn)，因此，因此，Bresenham算法比正負(fù)法決定的像素算法比正負(fù)法決定的像素更合理更合理122014-20

8、15-1:CG:SCUEC基本思想基本思想按一定方式計(jì)算給定圓弧軌跡上的一系列頂點(diǎn)，按一定方式計(jì)算給定圓弧軌跡上的一系列頂點(diǎn)，然后用連接相鄰點(diǎn)的一系列直線段來(lái)逼近圓弧。然后用連接相鄰點(diǎn)的一系列直線段來(lái)逼近圓弧。用正多邊形迫近圓弧法用正多邊形迫近圓弧法 設(shè)圓弧所在圓的半徑為設(shè)圓弧所在圓的半徑為R，圓弧的起始角和終止角分別為，圓弧的起始角和終止角分別為 和和 ，把圓弧分割成把圓弧分割成 份，則相鄰兩個(gè)頂點(diǎn)之間的夾角為份，則相鄰兩個(gè)頂點(diǎn)之間的夾角為 。設(shè)頂點(diǎn)序列的第設(shè)頂點(diǎn)序列的第 個(gè)點(diǎn)為個(gè)點(diǎn)為 ， 為該點(diǎn)的為該點(diǎn)的幅角。則下一個(gè)頂點(diǎn)幅角。則下一個(gè)頂點(diǎn) 的坐標(biāo)為的坐標(biāo)為 01nna/ )(01i)si

9、n,cos(),(iiiiiRRyxPi1iPcossin)sin(sincos)cos(11iiiiiiiiyxRyyxRx或表示為矩陣形式或表示為矩陣形式iiiiyxyxcossinsincos 11圓的多邊形迫近法132014-2015-1:CG:SCUEC多邊形迫近法的優(yōu)化v已知已知點(diǎn)點(diǎn)Pi，計(jì)算點(diǎn)，計(jì)算點(diǎn)Pi+1需要作四次乘法，再采需要作四次乘法，再采用畫(huà)直線方法畫(huà)用畫(huà)直線方法畫(huà)PiPi+1v為降低計(jì)算量，采用為降低計(jì)算量，采用cos 1, sin v或或cos 1- 2/2, sin ，取，取 = 2-k，則乘，則乘法可用移位和加減法實(shí)現(xiàn)法可用移位和加減法實(shí)現(xiàn)v不能精確求出圓的內(nèi)接

10、多邊形頂點(diǎn)，不能精確求出圓的內(nèi)接多邊形頂點(diǎn)， 取得取得越小，誤差越小越小，誤差越小142014-2015-1:CG:SCUEC多邊形迫近法的改進(jìn)v 設(shè)圓心在坐標(biāo)原點(diǎn)設(shè)圓心在坐標(biāo)原點(diǎn)O(0,0)，內(nèi)接正，內(nèi)接正多邊形的三個(gè)相鄰點(diǎn)為多邊形的三個(gè)相鄰點(diǎn)為Pi-1, Pi, Pi+1，如圖所示。如圖所示。 Pi-1A平行平行OPi+1， Pi+1A平行平行OPi-1112cosiiiOAOPOPOP OPi+1PiPi-1A112cosiiiOPOPOP 或：或：v設(shè)設(shè)Pi點(diǎn)的坐標(biāo)為點(diǎn)的坐標(biāo)為(xi, yi)，則，則11112cosiiiiiixxxyyy有：有：v 只需兩次乘法，但須知道圓上兩個(gè)相鄰

11、內(nèi)接多邊形的頂點(diǎn)只需兩次乘法，但須知道圓上兩個(gè)相鄰內(nèi)接多邊形的頂點(diǎn)152014-2015-1:CG:SCUEC橢圓弧橢圓弧的生成的生成設(shè)橢圓的中心在原點(diǎn)，長(zhǎng)短軸分別為設(shè)橢圓的中心在原點(diǎn)，長(zhǎng)短軸分別為a 和和b，且平行于坐標(biāo)柚，則該橢圓的參數(shù)方，且平行于坐標(biāo)柚，則該橢圓的參數(shù)方程為程為 cosax sinby ，設(shè)頂點(diǎn)序列的第設(shè)頂點(diǎn)序列的第i個(gè)頂點(diǎn)為個(gè)頂點(diǎn)為 ,則則下一個(gè)頂點(diǎn)下一個(gè)頂點(diǎn) 的坐標(biāo)應(yīng)滿足的坐標(biāo)應(yīng)滿足 )sin,cos(),(iiiiibayxP),(111iiiyxP)cos(1iiax)sin(1iiby , , 由此可得由此可得iiiiyxMyx11其中其中cossinsinco

12、sabbaM橢圓的多邊形迫近法162014-2015-1:CG:SCUEC 上半部分，斜率的絕對(duì)值上半部分，斜率的絕對(duì)值1,單位步長(zhǎng)應(yīng)為單位步長(zhǎng)應(yīng)為Y方向方向F(x,y)0說(shuō)明說(shuō)明(x，y)在橢圓內(nèi)在橢圓內(nèi)說(shuō)明說(shuō)明(x，y)在橢圓上在橢圓上說(shuō)明說(shuō)明(x，y)在橢圓外在橢圓外17生成橢圓之中點(diǎn)法v已知橢圓中心在已知橢圓中心在(0,0), 長(zhǎng)短半軸分別長(zhǎng)短半軸分別 為為a,b, 則橢圓方程為：則橢圓方程為：22221xyab2222220F( , )b xa ya bx yv 只需要討論第一象限橢圓弧的生成只需要討論第一象限橢圓弧的生成, 在生成這段橢圓弧時(shí)，在生成這段橢圓弧時(shí)，要分兩部分完成要分

13、兩部分完成2014-2015-1:CG:SCUEC 構(gòu)造判別式：構(gòu)造判別式：d1i=F(xM, yM)=b2(xi+1)2+a2(yi-0.5)2-a2b2 如果如果d1i 0,中點(diǎn)在橢圓外中點(diǎn)在橢圓外，應(yīng)取右下方像素應(yīng)取右下方像素Pd(xi+1,yi-1)判別式更新為判別式更新為：d1(i+1)=F(xi+2,yi-1.5)=d1i+b2(2xi+3)+2a2(-yi+1)18橢圓上半部分的生成v 設(shè)與當(dāng)前橢圓弧最近的像素點(diǎn)是設(shè)與當(dāng)前橢圓弧最近的像素點(diǎn)是P(xi,yi)v 下一個(gè)候選像素點(diǎn)只能是正右方的點(diǎn)下一個(gè)候選像素點(diǎn)只能是正右方的點(diǎn)Pu(xi+1,yi)或者是右下方的或者是右下方的Pd(

14、xi+1,yi-1)v 設(shè)設(shè)M(xi+1, yi-0.5)為為Pu與與Pd的中點(diǎn)的中點(diǎn)P(xi,yi)M(xi+1,yi-0.5)Pu(xi+1,yi)Pd(xi+1,yi-1) 如果如果d1i 0,中點(diǎn)在橢圓內(nèi)中點(diǎn)在橢圓內(nèi)，應(yīng)取正右方像素應(yīng)取正右方像素Pu(xi+1,yi)判別式更新為：判別式更新為：d1(i+1)=F(xi+2,yi-0.5)=d1i+b2(2xi+3) 判別式初值為：判別式初值為：d10=F(1,b-0.5)=b2+a2(-b+0.25)2014-2015-1:CG:SCUECdy/dx=2b2x/(2a2y)2b2(xi+1)2/2a2(yi0.5) 1 19橢圓上半部

15、分的終止條件v橢圓上任意一點(diǎn)橢圓上任意一點(diǎn)P(x,y)的切線斜率為：的切線斜率為：v上半部分每一點(diǎn)的切線斜率都大于上半部分每一點(diǎn)的切線斜率都大于1，故上半部分終止的條件為：下一個(gè)中點(diǎn)故上半部分終止的條件為：下一個(gè)中點(diǎn)(xi+1, yi-0.5)的切線斜率小于等于的切線斜率小于等于1，即，即b2(xi+1) a2(yi0.5) 2014-2015-1:CG:SCUEC 構(gòu)造判別式：構(gòu)造判別式：d2i=F(xM, yM)=b2(xi+0.5)2+a2(yi-1)2-a2b2 如果如果d2i 0,中點(diǎn)在橢圓外中點(diǎn)在橢圓外，應(yīng)取正下方像素應(yīng)取正下方像素Pl(xi,yi-1)判別式更新為判別式更新為：d2(i+1)=F(xi+0.5,yi-2)=d2i+a2(-2yi+3)20橢圓下半部分的生成v 設(shè)與當(dāng)前橢圓弧最近的像素點(diǎn)是設(shè)與當(dāng)前橢圓弧最近的像素點(diǎn)是P(xi,yi)v 下一個(gè)候選像素點(diǎn)只能是正下方的點(diǎn)下一個(gè)候選像素點(diǎn)只能是正下方的點(diǎn)Pl(xi,yi-1)或者是右下方的或者是右下方的Pr(xi+1,yi-1)v 設(shè)設(shè)M(xi+0.5, yi-1)為為Pl與與Pr的中點(diǎn)的中點(diǎn) 如果如果d2i 0,中點(diǎn)在橢圓內(nèi)中點(diǎn)在