計算機圖形學(xué) 第五章_Arc

1、Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系計計 算算 機機 圖圖 形形 學(xué)學(xué) Computer GraphicsComputer Graphics翟瑞芳翟瑞芳Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系解決的問題：解決的問題：繪出圓心在原點，半徑為繪出圓心在原點，半徑為整數(shù)整數(shù)R的圓的圓x2+y2=R2。Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)八分法畫圓八分法畫圓Designed by Ruifang

2、ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系解決問題：解決問題： 只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個圓只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個圓弧的象素集弧的象素集1/8圓弧圓弧Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系 解決方法解決方法中點畫圓中點畫圓Bresenhem算法算法Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系 X2 + Y2 = R2Y = Round（Sqrt(R2 - X2)）在一定范圍內(nèi)，每給定一在一定范圍內(nèi)，每給定一X值，可得一值，可得一Y值。值。當當X取整數(shù)時，取整數(shù)時，Y須取整。須取整。缺點：浮點運

3、算，開方，缺點：浮點運算，開方，取整，不均勻。取整，不均勻。yx算法原理算法原理：利用其函數(shù)方程，直接離散計算。利用其函數(shù)方程，直接離散計算。Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系圓的圓的極坐標方程極坐標方程為：為： sincosRyRx)sin( )cos()( 11111iiiiiiRroundyRroundx為一固定角度步長Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系簡單方程產(chǎn)生圓弧的方法計算復(fù)雜，簡單方程產(chǎn)生圓弧的方法計算復(fù)雜，效率極低。效率極低。Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機

4、科學(xué)與技術(shù)系構(gòu)造函數(shù)構(gòu)造函數(shù)F(x,y)=x2+y2-R2。 對于圓上的點，有對于圓上的點，有F(x,y)=0； 對于圓外的點，對于圓外的點， F(x,y)0； 而對于圓內(nèi)的點，而對于圓內(nèi)的點，F(xiàn)(x,y)0時，下一點取時，下一點取 Pd(xi +1,yi-1)。構(gòu)造判別式：構(gòu)造判別式：222)5 . 0() 1()5 . 0, 1(),(RyxyxFyxFdiiiiMMDesigned by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系誤差項的遞推（誤差項的遞推（d0） 2222)5 . 0()2( )5 . 0, 2(RyxyxFdiiii32)5 . 0(32) 1()5 .

5、0() 11(12222222iiiiiixdRyxxRyxdd0的情況的情況Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系2222)5 . 1()2( )5 . 1, 2(RyxyxFdiiii5)(25)(2)5 . 0() 1(1)5 . 0(2)5 . 0(32) 1() 15 . 0() 11(1222222222iiiiiiiiiiiiyxdyxyxRyyxxRyxd誤差項的遞推（誤差項的遞推（d0） d0的情況的情況Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系判別式的初始值判別式的初始值RRRRFyxFd25. 1

6、 )5 . 0(1 )5 . 0, 1 ()5 . 0, 1(22000Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系改進：改進：用用d-0.25d-0.25代替代替d d，此時有：，此時有：Rddyxdddxddiii125. 05)(225. 0320025. 0025. 0ddddDesigned by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系算法步驟：算法步驟：1. 輸入圓的半徑輸入圓的半徑R。2. 計算初始值計算初始值d=1.25-R、x=0、y=R。3. 繪制點繪制點(x,y)及其在八分圓中的另外七個對稱點。及其在八分圓中的另外七個對稱

7、點。4.判斷判斷d的符號。若的符號。若d0，則先將，則先將d更新為更新為d+2x+3， 再將再將(x,y)更更新為新為(x+1,y)；否則先將；否則先將d更新為更新為d+2(x-y)+5，再將，再將(x,y)更新更新為為(x+1,y-1)。5. 當當xy時，重復(fù)步驟時，重復(fù)步驟3和和4。否則結(jié)束。否則結(jié)束。Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(

8、d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系算法步驟算法步驟1.輸入圓的半徑輸入圓的半徑R。2.計算初始值計算初始值d=1-R、x=0、y=R。3.繪制點繪制點(x,y)及其在八分圓中的另外七個對稱點。及其在八分圓中的另外七個對稱點。4.判斷判斷d的符號。的符號。若若d0，則先將則先將d更新為更新為d+2x+3，再將再將(x,y)更新為更新為(x+1,y)；否則先將否則先將d更新為更新為d+2(x-y)+5，再將再將(x,y)更新為更新為(x+1,y-1)。5.當當

9、x F(xi,yi) 向右向右- 向圓外向圓外Pi在圓外時在圓外時- F(xi,yi)0 - 向下向下- 向圓內(nèi)向圓內(nèi)Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系即求得即求得Pi點后選擇下一個象素點點后選擇下一個象素點Pi+1的規(guī)則為：的規(guī)則為：當當F(xi,yi) 0 取取xi+1 = xi+1，yi+1 = yi;當當F(xi,yi) 0 取取xi+1 = xi， yi+1 = yi - 1;這樣用于表示圓弧的點均在圓弧附近，且使這樣用于表示圓弧的點均在圓弧附近，且使F(xi,yi) 時正時負，故稱正負法。時正時負，故稱正負法。 快速計算的關(guān)鍵是快速計算的

10、關(guān)鍵是F(xi,yi) 的計算，能否采用增的計算，能否采用增量算法？量算法？Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系若若F(xi,yi) 已知，計算已知，計算F(xi+1,yi+1) 可分可分兩種情況：兩種情況：1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +12、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,yi+1)= (xi+1 )

11、2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +13、初始值：略初始值：略Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系1. 橢圓的特征橢圓的特征bax xy y圖 5-14 長 半 軸 為 a， 短 半 軸 為 b的 標 準 橢 圓( (x x, ,y y) )( (x x, ,- -y y) )( (- -x x, ,- -y y) )( (- -x x, ,y y) )Designed by Ruifang ZHAI華中農(nóng)

12、業(yè)大學(xué)計算機科學(xué)與技術(shù)系0),(222222bayaxbyxF 對于橢圓上的點，有對于橢圓上的點，有F(x,y)=0F(x,y)=0； 對于橢圓外的點，對于橢圓外的點，F(xiàn)(x,y)0F(x,y)0； 對于橢圓內(nèi)的點，對于橢圓內(nèi)的點，F(xiàn)(x,y)0F(x,y)00，取，取P Pd d(x(xi i+1,y+1,yi i-1)-1)p p( (x xi i, ,y yi i) )p pu u( (x xi i+ +1 1, ,y yi i) )p pd d( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +1 1, ,y yi i- -0 0. .5 5

13、) ) 上上半半部部分分橢橢圓圓弧弧的的繪繪制制原原理理Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系誤差項的遞推誤差項的遞推 d10：)x(bd )x(bba).(ya)(xb ba).(ya)(xb).,yF(xdiiiiiiii32325015025022122222222222221Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系) 22() 32 ( ) 22() 32 () 5 . 0() 1( ) 5 . 1() 2() 5 . 1, 2(221222222222222221iiiiiiiiiiyaxbdyaxbbay

14、axbbayaxbyxFd誤差項的遞推誤差項的遞推 d10：Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系判別式的初始值判別式的初始值 )25. 0( )5 . 0()5 . 0, 1 (22222220babbababbFdDesigned by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系p p( (x xi i, ,y yi i) )p pl l( (x xi i, ,y yi i- -1 1) )p pr r( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +1 1, ,y yi i- -0 0. .

15、5 5) )5-19 下半部分橢圓弧的繪制原理再來推導(dǎo)橢圓弧下半部分的繪制公式再來推導(dǎo)橢圓弧下半部分的繪制公式Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系判別式判別式 2222222) 1() 5 . 0() 1, 5 . 0(bayaxbyxFdiiii 若若d20，取，取Pl(xi,yi-1) 若若d20，取，取Pr(xi+1,yi-1)p p( (x xi i, ,y yi i) )p pl l( (x xi i, ,y yi i- -1 1) )p pr r( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +

16、1 1, ,y yi i- -0 0. .5 5) )5-19 下半部分橢圓弧的繪制原理Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系誤差項的遞推誤差項的遞推 d20：)y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF(xdiiiiiiii323215 . 025 . 025 . 0 2222222222222222Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系d20： ) 32() 22( ) 32() 22() 1() 5 . 0( ) 2() 5 . 1() 2, 5 . 1(22222222222222

17、2222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( (b b) ) d d = =0 0的的情情況況P Px xi ix xi i+ +2 2x xi i+ +1 1y yi i- -1 1y yi iy yi i- -2 2Designed by Ruifang ZHAI華中農(nóng)業(yè)大學(xué)計算機科學(xué)與技術(shù)系注意：注意： 上半部分的終止判別上半部分的終止判別 下半部分誤差項的初值下半部分誤差項的初值 算法步驟：算法步驟：1. 輸入橢圓的長半軸輸入橢圓的長半軸a和短半軸和短半軸b。2. 計算初始值計算初始值d=b2+a2(-b+0.25)、x=0、y=b。3. 繪制點繪制點(x,y)及其在四分象限上的另外三個對稱點。及其在四分象限上的另外三個對稱點。Des