計算機圖形學(xué)第二講直線和圓的生成.ppt

1、15歲覺得游泳難，放棄游泳，到18歲遇到一個你喜歡的人約你去游泳，你只好說“我不會耶”。18歲覺得英文難，放棄英文，28歲出現(xiàn)一個很棒但要會英文的工作，你只好說“我不會耶”。人生前期越嫌麻煩，越懶得學(xué)，后來就越可能錯過讓你動心的人和事，錯過新風(fēng)景。 蔡康勇給殘酷社會的善意短信,2020年8月2日10時9分,一、回答下列問題： 什么是計算機圖形學(xué)？ 請描述圖形與圖像的關(guān)系。 二、解釋下列術(shù)語： 像素、光柵掃描、刷新、分辨率、真色彩、RGB 三、計算： 當(dāng)一種顯示器有600 800像素的分辨率，每個像素能顯示65536種顏色，刷新率是每秒60次時，每秒鐘有多少比特傳送給顯示器？,2020年8月2日

2、10時9分,計算機圖形學(xué)研究的核心內(nèi)容包括：客觀現(xiàn)實對象的模型生成；模型在顯示設(shè)備上的顯示輸出。 圖形：以矢量形式儲存于計算機中； 圖像：以點陣形式儲存于計算機中；,像素：屏幕或圖像能夠顯示的最小單位 計算機顯示屏或數(shù)字圖像所能顯示的單位是有限的 分辨率：單位長度上像素或點的個數(shù) 分辨率越高，單位長度上像素的個數(shù)越多；同樣大?。ㄐ小⒘邢袼叵嗤┑臄?shù)字圖像，在分辨率高的顯示器上實際顯示的尺寸更小。 光柵掃描：電子束按照從左到右、從上到下的順序?qū)ο袼貣鸥襁M(jìn)行掃描（繪制）的過程 其本質(zhì)是進(jìn)行畫點操作 幀緩存器：光柵掃描完整完成一次所形成的圖像稱為幀，待掃描的幀圖像存放于幀緩存器中,掃描轉(zhuǎn)換： 對任一

3、想要在光柵掃描顯示器上顯示的圖形，在顯示屏幕上找到最接近該待畫圖形的各個像素，這一過程稱為掃描轉(zhuǎn)換。 任何圖形在送入幀緩沖器進(jìn)行顯示前，必須先要經(jīng)過掃描轉(zhuǎn)換這一步驟；又稱為圖形的生成。,A,教學(xué)基本要求： 1.1直線的生成算法； 1.2圓的生成算法； 1.3區(qū)域填充算法； 1.4裁剪算法；,2020年8月2日10時9分,教學(xué)基本要求： 1.1直線的生成算法； 1.2圓的生成算法； 1.3區(qū)域填充算法； 1.4裁剪算法；,2020年8月2日10時9分,2020年8月2日10時9分,在數(shù)學(xué)上，理想的直線是一條由無窮多個無限小的連續(xù)的點組成。,2020年8月2日10時9分,但在光柵顯示平面上，我們只

4、能用二維光柵網(wǎng)格上盡可能靠近這條直線的像素點的集合來表示它。每個像素具有一定的尺寸，是顯示平面上可被顯示的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說相鄰象素的坐標(biāo)值是階躍的而不是連續(xù)的。,直線的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線的那些像素的坐標(biāo)值；直線的掃描轉(zhuǎn)換算法就是計算這些坐標(biāo)值的方法；,常見算法： DDA算法 （Digital Differential Analyzer，數(shù)值微分法） Bresenham算法,直線的生成（掃描轉(zhuǎn)換）,2020年8月2日10時9分,兩種定義方法： 1）像素理想化為點2）像素有一定面積,2020年8月2日10時9分,倘若已知直線段兩端點的坐標(biāo)（x

5、1,y1）（x2,y2），如何求得屏幕上顯示的各點的坐標(biāo)？,直線DDA算法描述,設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點和終點坐標(biāo)，由直線的微分方程得,可通過計算由x方向的增量x引起y的改變來生成直線：,也可通過計算由y方向的增量y引起x的改變來生成直線：,直線DDA算法思想,選定x2x1和y2y1中較大者作為步進(jìn)方向(假設(shè)x2x1較大)，取該方向上的增量為一個象素單位(x=1)，然后利用公式計算另一個方向的增量(y=xm=m)。通過遞推公式，把每次計算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。,之所以取x2x1和y2y1中較大者作為步進(jìn)方向，是考慮

6、沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。 另外，算法實現(xiàn)中還應(yīng)注意直線的生成方向，以決定x及y是取正值還是負(fù)值。,直線DDA算法實現(xiàn),Void DDALine(int x1,int y1,int x2, int y2,int color) int x; float k,y=y1; k=1.0*(y2-y1)/(x2-x1); for(x=x1;x=x2;x+) putpixel(x, (int)(y+0.5),color); y=y+k; ,按照從(x1, y1)到(x2, y2)方向不同，分8個象限。對于方向在第1a象限內(nèi)的直線而言，取增量值x=1，y=m。對于方向在第1b象限內(nèi)的直線而

7、言，取增量值y=1，x=1/m。,直線方向的8個象限,8個象限中的坐標(biāo)增量值,直線DDA算法實現(xiàn),void ddaline(int x1,int y1,int x2,int y2) int i,length; float dx,dy,x=x1,y=y1; if (abs(x2-x1)=abs(y2-y1) length=abs(x2-x1); else length=abs(y2-y1); dx=1.0*(x2-x1)/length; dy=1.0*(y2-y1)/length; for(i=1;i=length;i+) putpixel(int)(x),(int)(y); x=x+dx; y

8、=y+dy; ,直線DDA算法完善,使用DDA算法，每生成一條直線做兩次除法，畫線中每一點都要經(jīng)過取整運算。x、y、dx、dy都必須用浮點數(shù)表示，這些都使得DDA算法的效率難以提高。,直線Bresenham算法描述,為了避免做費時的乘除運算和取整運算，Bresenham提出了一種更好的直線生成算法。其基本思想是借助一個決策變量來確定下一個像素點。 首先討論m=y/x，當(dāng)0m1且x1x2時（1a象限）的Bresenham算法。 假設(shè)直線上第i個象素點坐標(biāo)已經(jīng)確定，設(shè)為(xi，yi)，那么，直線上下一個象素點的可能位置是(xi+1，yi)或(xi+1，yi+1)。(注意m1）,直線Bresenha

9、m算法描述,由圖中可以知道：在x=xi+1處，直線上點的y值是y=m(xi+1)+b，該點離象素點(xi+1，yi)和象素點(xi+1，yi+1)的距離分別是d1和d2： d1=y-yi=m(xi+1)+b-yi d2=(yi+1)-y=(yi+1)-m(xi+1)-b 兩個距離差是 d1-d2=2m(xi+1)-2yi2b-1,直線Bresenham算法描述,我們來分析公式d1-d2=2m(xi+1)-2yi2b-1 (1)當(dāng)此值為正時，d1d2，說明直線上理論點離(xi+1，yi+1)象素較近，下一個象素點應(yīng)取(xi+1，yi+1)。 (2)當(dāng)此值為負(fù)時，d1d2，說明直線上理論點離(xi

10、+1，yi)象素較近，則下一個象素點應(yīng)取(xi+1，yi)。 (3)當(dāng)此值為零時，說明直線上理論點離上、下兩個象素點的距離相等，取哪個點都行，假設(shè)算法規(guī)定這種情況下取(xi+1，yi+1)作為下一個象素點。 因此只要利用(d1-d2)的符號就可以決定下一個象素點的選擇。,直線Bresenham算法描述,進(jìn)一步定義一個新的判別式（決策變量）： pi=x(d1-d2)=2yxi-2xyi+c（c=2 y+ x (2b-1)） x=(x2-x1)0，因此pi與(d1-d2)有相同的符號； 則此時pi的計算僅包含整數(shù)運算；c為常量，可在遞推運算中被消去； 經(jīng)過一系列誤差判別變量的遞推，得到如下算法表示

11、： 初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y 可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個端點坐標(biāo)分量差x和y有關(guān)，運算中只含有整數(shù)相加和乘2運算，而乘2可利用算術(shù)左移一位來完成，因此這個算法速度快并易于硬件實現(xiàn)。,直線Bresenham算法實現(xiàn),條件：0m1且x1=0) y=y+1；p=p+2(y-x)；else p=p+2y； ,Bresenham算法的優(yōu)點如下： 不必計算直線的斜率，因此不做除法。 不用浮點數(shù)，只用整數(shù)。

12、只做整數(shù)加減運算和乘2運算，而乘2運算可以用移位操作 實現(xiàn)。 Bresenham算法的運算速度很快，并適于用硬件實現(xiàn)。 討論：以上考慮的是 0yx 的情況，對于適用所有8個方向的直線的生成算法，則要考慮以判斷條件|dx|dy|為分支，并分別將2a、3a象限的直線和3b、4b象限的直線變換到1a、4a和2b、1b象限方向去，以實現(xiàn)程序處理的簡潔。,直線Bresenham算法完善,已知某一直線段的起點坐標(biāo)（1，2）和終點坐標(biāo)（7，5），用Bresenham算法生成該直線段，要求計算出各點的坐標(biāo)值并畫出示意圖。,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,

13、已知某一直線段的起點坐標(biāo)（1，2）和終點坐標(biāo)（7，5），用Bresenham算法生成該直線段，要求計算出各點的坐標(biāo)值并畫出示意圖。,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,已知某一直線段的起點坐標(biāo)（1，2）和終點坐標(biāo)（7，5），用Bresenham算法生成該直線段，要求計算出各點的坐標(biāo)值并畫出示意圖。,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p10，x2=x1+1=2，y2=y1+1=3，p2=p1+2y

14、-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p10，x2=x1+1=2，y2=y1+1=3，p2=p1+2y-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+

15、1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p10，x2=x1+1=2，y2=y1+1=3，p2=p1+2y-2x=-6； p20，x3=x2+1=3，y3=y2=3，p3=p2+2y =0；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, x

16、i+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p10，x2=x1+1=2，y2=y1+1=3，p2=p1+2y-2x=-6； p20，x3=x2+1=3，y3=y2=3，p3=p2+2y =0；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y

17、-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p20，x3=x2+1=3，y3=y2=3，p3=p2+2y =0； p30，x4=x3+1=4，y4=y3+1=4，p4=p3+2y-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p20，x3=x2+1=3，y3=

18、y2=3，p3=p2+2y =0； p30，x4=x3+1=4，y4=y3+1=4，p4=p3+2y-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p30，x4=x3+1=4，y4=y3+1=4，p4=p3+2y-2x=-6； p40，x5=x4+1=5，y5=y4=

19、4，p5=p4+2y =0；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p30，x4=x3+1=4，y4=y3+1=4，p4=p3+2y-2x=-6； p40，x5=x4+1=5，y5=y4=4，p5=p4+2y =0；,直線Bresenham算法舉例,0,0,1,2,3,4,

20、5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p40，x5=x4+1=5，y5=y4=4，p5=p4+2y =0； p50，x6=x5+1=6，y6=y5+1=5，p6=p5+2y-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1

21、, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p40，x5=x4+1=5，y5=y4=4，p5=p4+2y =0； p50，x6=x5+1=6，y6=y5+1=5，p6=p5+2y-2x=-6；,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi

22、+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1=1，y1=2，則有： p50，x6=x5+1=6，y6=y5+1=5，p6=p5+2y-2x=-6； p60，x7=x6+1=7，y7=y6=5,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,解：由已經(jīng)條件得：y=3，x=6，p1=2y-x=0； 設(shè)起點坐標(biāo)為x1

23、=1，y1=2，則有： p50，x6=x5+1=6，y6=y5+1=5，p6=p5+2y-2x=-6； p60，x7=x6+1=7，y7=y6=5,直線Bresenham算法舉例,0,0,1,2,3,4,5,6,7,1,2,3,4,5,初始 p1=2y-x 當(dāng)pi0時： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(y-x) 否則： yi+1=yi, xi+1=xi+1， pi+1=pi+2y,教學(xué)基本要求： 1.1直線的生成算法； 1.2圓的生成算法； 1.3區(qū)域填充算法； 1.4裁剪算法；,2020年8月2日10時9分,圓的生成算法,這里僅討論圓心位于坐標(biāo)原點的圓的掃描轉(zhuǎn)

24、換算法，對于圓心不在原點的圓，可先用平移變換，將它的圓心平移到原點，然后進(jìn)行掃描轉(zhuǎn)換，最后再平移到原來的位置。 有幾種較容易的方法可以得到圓的掃描轉(zhuǎn)換，但是效率都不高。例如：直角坐標(biāo)法和極坐標(biāo)法,圓的生成算法,直角坐標(biāo)法 圓的直角坐標(biāo)方程為 x2+y2=R2若取x作為自變量，解出y。讓自變量x從0到R以單位步長增加，在每一步時可解出y，然后調(diào)用畫點函數(shù)即可逐點畫出圓。但這樣做，由于有乘方和平方根運算，并且都是浮點運算，算法效率不高。而且當(dāng)x接近R值時(圓心在原點)，在圓周上的點（R，0）附近，由于圓的斜率趨于無窮大，使得圓周上有較大的間隙。 極坐標(biāo)法 假設(shè)圓周上一點P（x，y）處的半徑與x軸的夾角為，則圓的極坐標(biāo)方程為 x=Rcosy=Rsin 這個方法涉及三角函數(shù)計算和乘法運算，計算量較大。因此，也不是一種有效的方法。,圓的八分對稱性,圓心位于原點的圓有四條對稱軸x=0、y=0、x=y和x=y，見下圖。從而若已知圓弧上一點P(x，y)，就可以得到其關(guān)于四條對稱軸的七個對稱點，這種性質(zhì)稱為八分對稱性。因此只要能畫出八分之一的圓弧，就可以利用對稱性的原理得到整個圓弧。,void WholeCircle(int x,int y,int color); putpixel(x,y, color); putpixel(-x,