計算機圖形學(xué)2.2-2.3.

1、2.2.1 基礎(chǔ)知識基礎(chǔ)知識 給出圓心坐標給出圓心坐標( (x xc c, , y yc c) )和半徑和半徑r r，逐點畫出一個圓周的公式有下逐點畫出一個圓周的公式有下列兩種：列兩種： 直角坐標法直角坐標法( (x x x xc c) )2 2 + ( + (y y y yc c) )2 2 = = r r2 2由上式導(dǎo)出：由上式導(dǎo)出：cc22()yyrxx 當當x x x xc c從從 r r到到r r作加作加1 1遞增時，就可遞增時，就可以求出對應(yīng)的圓周點的以求出對應(yīng)的圓周點的y y坐標。坐標。 但是這樣求出的圓周上的點是不均但是這樣求出的圓周上的點是不均勻的，勻的， x x x xc

2、c越大，對應(yīng)生成圓周點之間越大，對應(yīng)生成圓周點之間的圓周距離也就越長。因此，所生成的的圓周距離也就越長。因此，所生成的圓不美觀。圓不美觀。2.2.1 基礎(chǔ)知識基礎(chǔ)知識( (續(xù)）續(xù)） 極坐標法極坐標法x x = = x xc c + + r r coscos，y y = = y yc c + + r r sin sin當當從從0 0到到作遞增時，由此式便可求出圓周上均勻分布的作遞增時，由此式便可求出圓周上均勻分布的360360個個點的點的( (x x, , y y) )坐標。坐標。 利用圓周坐標的對稱性，此利用圓周坐標的對稱性，此算法還可以簡化。將圓周分為算法還可以簡化。將圓周分為8 8個象限個

3、象限( (圖圖2.3)2.3)，只要將第，只要將第1 1a a象象限中的圓周光柵點求出，其余限中的圓周光柵點求出，其余7 7部分圓周就可以通過對稱法則部分圓周就可以通過對稱法則計算出來。計算出來。圖2.3 圓心在(0, 0)點圓周生成時的對稱變換2.2.2 圓的圓的Bresenham算法算法 設(shè)圓的半徑為設(shè)圓的半徑為r r。先考慮圓心在先考慮圓心在(0, 0)(0, 0)，并從，并從x x=0=0、y y= =r r開始的開始的順時針方向的順時針方向的1/81/8圓周的生成過程。在這種情況下，圓周的生成過程。在這種情況下，x x每步增加每步增加1 1，從從x x=0=0開始，到開始，到x x=

4、 =y y結(jié)束。即有結(jié)束。即有x xi i+1+1 = = xixi + 1 + 1y yi i+1+1 = = yiyi或者或者y yi i+1+1 = = yiyi 1 1 選擇的原則是考察精確值選擇的原則是考察精確值y y是靠近是靠近y yi i還是還是靠近靠近y yi i 1(1(圖圖2.4)2.4)，計算式為計算式為y y2 2 = = r r2 2 ( (x xi i+1)+1)2 2d d1 1 = = y yi i2 2 y y2 2 = = y yi i2 2 r r2 2+(+(x xi i+1)+1)2 2d d2 2 = = y y2 2 ( (y yi i 1)1)2

5、 2 = = r r2 2 ( (x xi i+1)+1)2 2 ( (y yi i 1)1)2 2圖2.4 y的位置 令令p pi i= =d d1 1 d d2 2，并代入并代入d d1 1、d d2 2，則有則有 p pi i = 2( = 2(x xi i+1)+1)2 2 + + y yi i2 2 + ( + (y yi i 1)1)2 2 2 2r r2 2 (2.6)(2.6)p pi i稱為誤差。如果稱為誤差。如果p pi i00則則y yi i+1+1= =y yi i，否則否則y yi i+1+1= =y yi i 1 1。p pi i的遞歸式為的遞歸式為 p pi i+

6、1+1 = = p pi i + 4 + 4x xi i +6+2(+6+2(y yi i2 2+1+1 y yi i2 2) ) 2(2(y yi i+1+1 y yi i) ) (2.7) (2.7)p pi i的初值由式的初值由式(2.6)(2.6)代入代入x xi i=0=0，y yi i= =r r而得而得 p1 = 3p1 = 3 2r2r (2.8)(2.8)根據(jù)上面的推導(dǎo)，圓周生成根據(jù)上面的推導(dǎo)，圓周生成算法思想算法思想如下：如下： 求誤差初值，求誤差初值，p p1 1=3=3 2 2r r，i i=1=1，畫點畫點(0, (0, r r) )； 求下一個光柵位置，其中求下一個

7、光柵位置，其中x xi i+1+1= =x xi i+1+1，如果如果p pi i00則則y yi i+1+1= =y yi i，否則否則y yi i+1+1= =y yi i 1 1； 畫點畫點( (x xi i+1+1, , y yi i+1+1) )； 計算下一個誤差，如果計算下一個誤差，如果p pi i00則則p pi i+1+1= =p pi i+4+4x xi i+6+6，否則否則p pi i+1+1= =p pi i+4(+4(x xi i y yi i)+10)+10； i i= =i i+1+1，如果如果x x= =y y則結(jié)束，否則返回步驟則結(jié)束，否則返回步驟2 2。圓的圓

8、的BresenhamBresenham算法的程序?qū)崿F(xiàn)如下：算法的程序?qū)崿F(xiàn)如下：circle(circle(xcxc, , ycyc, radius, c), radius, c)int xcint xc, , ycyc, radius, c;, radius, c; intint x, y, p; x, y, p; x=0;x=0; y=radius;y=radius; p=3p=3 2 2* *radiusradius；while(xy)while(xy)plot_circle_points(plot_circle_points(xcxc, ,ycyc,x,y,c);,x,y,c);if(p

9、0) p=p+4if(p0) p=p+4* *x+6;x+6;elseelsep=p+4p=p+4* *(x(x y)+10;y)+10;y y =1;=1; x+=1;x+=1; if(x=y)if(x=y)plot_circle_points(plot_circle_points(xcxc, ,ycyc,x,y,c);,x,y,c); plot_circle_points(plot_circle_points(xcxc, , ycyc, x, y, c), x, y, c)int xcint xc, , ycyc, x, y, c;, x, y, c; set_pixel(set_pixe

10、l(xcxc+x, +x, ycyc+y, c);+y, c);set_pixel(set_pixel(xcxc x, x, ycyc+y, c);+y, c);set_pixel(set_pixel(xcxc+x, +x, ycyc y, c);y, c);set_pixel(set_pixel(xcxc x, x, ycyc y, c);y, c);set_pixel(set_pixel(xcxc+y, +y, ycyc+x, c);+x, c);set_pixel(set_pixel(xcxc y, y, ycyc+x, c);+x, c);set_pixel(set_pixel(xcx

11、c+y, +y, ycyc x, c);x, c);set_pixel(set_pixel(xcxc y, y, ycyc x, c);x, c); 2.3.1 基礎(chǔ)知識基礎(chǔ)知識 區(qū)域填充區(qū)域填充即給出一個區(qū)域的邊界，要求對邊界范圍內(nèi)的所有像素即給出一個區(qū)域的邊界，要求對邊界范圍內(nèi)的所有像素單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色。單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色。多邊形的表示方法多邊形的表示方法頂點表示頂點表示點陣表示點陣表示圖2.5 掃描線與多邊形相交 圖2.6 光柵化后直線變成離散點 多邊形填色一個首要的問題，是判斷一個像素是在多邊形內(nèi)還是多多邊形填色

12、一個首要的問題，是判斷一個像素是在多邊形內(nèi)還是多邊形外。數(shù)學(xué)上提供的方法是邊形外。數(shù)學(xué)上提供的方法是“掃描交點的掃描交點的奇偶數(shù)判斷法奇偶數(shù)判斷法”。( (掃描線掃描線與邊界相交奇數(shù)次后進入該多邊形，相交偶數(shù)次后走出該多邊形。）與邊界相交奇數(shù)次后進入該多邊形，相交偶數(shù)次后走出該多邊形。） 2.3.1 基礎(chǔ)知識基礎(chǔ)知識( (續(xù)）續(xù)） 填色算法分為兩大類：填色算法分為兩大類： 掃描線填色掃描線填色( (Scan-Line Filling)Scan-Line Filling)算法。算法。這類算法建立這類算法建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于

13、程序填色，也可用于交互填色。用于交互填色。 種子填色種子填色( (Seed Filling)Seed Filling)算法。算法。這類算法建立在多邊這類算法建立在多邊形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界內(nèi)一點形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界內(nèi)一點的坐標。所以，它一般只能用于人機交互填色，而難以用于的坐標。所以，它一般只能用于人機交互填色，而難以用于程序填色。程序填色。2.3.2 掃描線填色算法掃描線填色算法 算法的基本思想：算法的基本思想：多邊形以多邊形以n n、x_arrayx_array、y_arrayy_array的形式給出，其中，的形式給出，其中，x_array

14、x_array、y_arrayy_array中存放著多邊形的中存放著多邊形的n n個頂點的個頂點的x x，y y坐標。坐標。 用水平掃描線從上到下掃描由點用水平掃描線從上到下掃描由點線段構(gòu)成的多段定義成的多邊形。每線段構(gòu)成的多段定義成的多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交根掃描線與多邊形各邊產(chǎn)生一系列交點。這些交點按照點。這些交點按照x x坐標進行分類，將坐標進行分類，將分類后的交點成對取出，作為兩個端分類后的交點成對取出，作為兩個端點，以所需要填的色彩畫水平直線。點，以所需要填的色彩畫水平直線。多邊形被掃描完畢后，填色也就完成。多邊形被掃描完畢后，填色也就完成。2.3.2 掃描線填色算

15、法掃描線填色算法( (續(xù)）續(xù)） 需要解決或改進的問題： 左、右頂點處理左、右頂點處理。左頂點左頂點2 2：y y1 1 y y2 2 y y2 2 y y3 3其中其中y y1 1、y y2 2、y y3 3是是3 3個相鄰的頂點的個相鄰的頂點的y y坐標。坐標。 當掃描線與多邊形的每個頂點相交時，當掃描線與多邊形的每個頂點相交時，會同時產(chǎn)生會同時產(chǎn)生2 2個交點。這時，填色就會因掃描個交點。這時，填色就會因掃描交點的奇偶計數(shù)出錯而出現(xiàn)錯誤。交點的奇偶計數(shù)出錯而出現(xiàn)錯誤。圖2.7 多邊形的頂點 對所有左、右頂點作如下處理：對所有左、右頂點作如下處理：v左、右頂點的入邊左、右頂點的入邊( (以該

16、頂點為終點的那條邊，即以該頂點為終點的那條邊，即1212邊邊) )之終點刪去。之終點刪去。對于左頂點，入邊端點對于左頂點，入邊端點( (x1, y1)x1, y1)、(x2, y2)(x2, y2)修改為修改為( (x1, y1)x1, y1)、( (, y2, y2 1)1)；對于右頂點，入邊端點對于右頂點，入邊端點( (x1, y1)x1, y1)、(x2, y2)(x2, y2)修改為修改為( (x1, y1)x1, y1)、( (, y2+1), y2+1)；21xm21xm2.3.2 掃描線填色算法掃描線填色算法( (續(xù)）續(xù)） 水平邊處理水平邊處理。水平邊水平邊(y1=y2)與水平掃

17、描線重合無法求交點。因此，將與水平掃描線重合無法求交點。因此，將水平邊畫出后刪去，不參加求交點及求交點以后的操作。水平邊畫出后刪去，不參加求交點及求交點以后的操作。 掃描線與邊的求交點方法采用遞歸算法掃描線與邊的求交點方法采用遞歸算法。以以( (x1, y1)x1, y1)、(x2, y2)(x2, y2)為端點的邊與第為端點的邊與第i+1i+1條掃描線的交點為條掃描線的交點為1211211iiiiyyxxxxyy此式表示交點不為此式表示交點不為( (x1, y1)x1, y1)。否則，交點為否則，交點為( (x1, y1)x1, y1)。 減少求交計算量，采用活性邊表。減少求交計算量，采用活

18、性邊表。對于一根掃描線而言，與之相對于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分交的邊只占多邊形全部邊的一部分, ,每根掃描線與多邊形所有邊求交的操作每根掃描線與多邊形所有邊求交的操作是一種浪費，需要加以改進。是一種浪費，需要加以改進。 活性邊表活性邊表( (Active List of Side)Active List of Side)的采用將多邊形的邊分成的采用將多邊形的邊分成兩個子集：與當前掃描線相交的邊的集合，以及與當前掃描線兩個子集：與當前掃描線相交的邊的集合，以及與當前掃描線不相交的邊的集合。對后者不必進行求交運算，這樣就提高了不相交的邊的集合。對后者不必進行求交運算，這

19、樣就提高了算法的效率。算法的效率。圖2.8 活性邊表及其指針的表示 v在上述線性表上加入兩個指針在上述線性表上加入兩個指針first和和last，形成活性邊表。形成活性邊表。v活性邊表中每個元素的內(nèi)容包括以下四項：活性邊表中每個元素的內(nèi)容包括以下四項：邊的邊的maxy值；值；與當前掃描線相交的點的與當前掃描線相交的點的x坐標值；坐標值；邊的邊的y方向當前總長方向當前總長y2-y1；邊的斜率的倒數(shù)邊的斜率的倒數(shù)1/m。v活性邊表在每根掃描線掃描之后刷新?；钚赃叡碓诿扛鶔呙杈€掃描之后刷新。調(diào)整調(diào)整first和和last指針之間的參加求交運算的邊元素的值；指針之間的參加求交運算的邊元素的值；調(diào)整調(diào)整

20、first和和last指針，以便使新邊進入激活范圍。指針，以便使新邊進入激活范圍。活性邊表構(gòu)成方法如下：活性邊表構(gòu)成方法如下：v將經(jīng)過左、右頂點處理并剔除水平邊后的多邊形各邊按照將經(jīng)過左、右頂點處理并剔除水平邊后的多邊形各邊按照maxymaxy值排序，值排序，存入一個線性表中。存入一個線性表中。程序結(jié)構(gòu)見課本32頁。掃描線填色算法優(yōu)、缺點：掃描線填色算法優(yōu)、缺點：優(yōu)點優(yōu)點：對于每個象素只訪問一次，輸入輸出的要求可降為最少；：對于每個象素只訪問一次，輸入輸出的要求可降為最少；缺點缺點：對于各種表的維持和排序的耗費大。：對于各種表的維持和排序的耗費大。掃描線（y=4）： 6 2 3 0 5 7.5

21、 4 0.5 ymax x y 1/m掃描線（y=3）： 3 2 2 -2 5 7 4 0.5 p3p4 p2p3 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1p1p2p3p4p5p4p5p2p3邊填充算法（區(qū)域掃描轉(zhuǎn)換算法）邊填充算法（區(qū)域掃描轉(zhuǎn)換算法）基本思想：對每條掃描線和多邊形邊的交點，將該掃描線上交點右方基本思想：對每條掃描線和多邊形邊的交點，將該掃描線上交點右方的所有像素取補。（對每條邊作處理的順序隨意）的所有像素取補。（對每條邊作處理的順序隨意）p1p2p3p4p5算法優(yōu)、缺點：算法優(yōu)、缺點：優(yōu)點優(yōu)點：簡單，適用于具有禎緩存的圖形系統(tǒng)；：簡單，適用于具有禎緩存的

22、圖形系統(tǒng)；缺點缺點：每個象素可能被訪問多次，輸入輸出的量大。：每個象素可能被訪問多次，輸入輸出的量大。柵欄填充算法柵欄填充算法對于每條掃描線與多邊形邊的交點，將交點與柵欄之間的像素取補。對于每條掃描線與多邊形邊的交點，將交點與柵欄之間的像素取補。柵欄線柵欄線優(yōu)點優(yōu)點：減少了訪問次數(shù)：減少了訪問次數(shù)種子填色又稱邊界填色種子填色又稱邊界填色( (Boundary Filling)Boundary Filling)。它的功能是，它的功能是，給出多邊形光柵化后的邊界位置及邊界色代碼給出多邊形光柵化后的邊界位置及邊界色代碼boundary_colorboundary_color，以及多邊形內(nèi)的一點以及多邊形內(nèi)的一點( (x, y)x, y)位置，要求將顏色位置，要求將顏色fill_colorfill_color填滿填滿多邊形。多邊形。2.3.3 2.3.3 種子填色算法種子填色算法 算法要求區(qū)域是連通的算法要求區(qū)域是連通的連通性連通性 4連通、8連通4連通：連通：從區(qū)域內(nèi)任意一點出發(fā)，可通過從區(qū)域內(nèi)任意一點出發(fā)，可通過上