計(jì)算機(jī)圖形學(xué)222的知識(shí)

2.2圓的生成算法2.2.1基礎(chǔ)知識(shí)

給出圓心坐標(biāo)(xc,yc)r，逐點(diǎn)畫出一個(gè)圓周的公式有下列兩種：⒈直角坐標(biāo)法

(xxc)2+(yyc)2=r2由上式導(dǎo)出：

當(dāng)xxc從r到r作加1遞增時(shí)，就可以求出對應(yīng)的圓周點(diǎn)的y坐標(biāo)。但是這樣求出的圓周上的點(diǎn)是不均勻的，xxc越大，對應(yīng)生成圓周點(diǎn)之間的圓周距離也就越長。因此，所生成的圓不美觀。12.2圓的生成算法2.2.1基礎(chǔ)知識(shí)(續(xù)）

⒉極坐標(biāo)法

x=xc+r·cosθ，y=yc+r·sinθ

當(dāng)θ從0到π作遞增時(shí)，由此式便可求出圓周上均勻分布的360個(gè)點(diǎn)的(x,y)坐標(biāo)。利用圓周坐標(biāo)的對稱性，此算法還可以簡化。將圓周分為8個(gè)象限(圖2.3)，只要將第1a象限中的圓周光柵點(diǎn)求出，其余7部分圓周就可以通過對稱法則計(jì)算出來。

圖2.3圓心在(0,0)點(diǎn)圓周生成時(shí)的對稱變換22.2圓的生成算法2.2.2圓的Bresenham算法

設(shè)圓的半徑為r。先考慮圓心在(0,0)，并從x=0、y=r開始的順時(shí)針方向的1/8圓周的生成過程。在這種情況下，x每步增加1，從x=0開始，到x=y結(jié)束。即有

xi+1=xi+1

yi+1=yi或者yi+1=yi1選擇的原則是考察精確值y是靠近yi還是靠近yi1(圖2.4)，計(jì)算式為y2=r2(xi+1)2d1=yi2y2=yi2r2+(xi+1)2d2=y2(yi1)2=r2(xi+1)2(yi1)2圖2.4y的位置

32.2圓的生成算法令pi=d1d2，并代入d1、d2，則有

pi=2(xi+1)2+yi2+(yi1)22r2(2.6)pi稱為誤差。如果pi<0則yi+1=yi，否則yi+1=yi1。pi的遞歸式為

pi+1=pi+4xi

+6+2(yi2+1yi2)2(yi+1yi)(2.7)pi的初值由式(2.6)代入xi=0，yi=r而得

p1=32r(2.8)根據(jù)上面的推導(dǎo)，圓周生成算法思想如下：⒈求誤差初值，p1=32r，i=1，畫點(diǎn)(0,r)；⒉求下一個(gè)光柵位置，其中xi+1=xi+1，如果pi<0則yi+1=yi，否則yi+1=yi1；⒊畫點(diǎn)(xi+1,yi+1)；⒋計(jì)算下一個(gè)誤差，如果pi<0則pi+1=pi+4xi+6，否則pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y則結(jié)束，否則返回步驟2。42.2圓的生成算法

圓的Bresenham算法的程序?qū)崿F(xiàn)如下：

circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=32*radius；

while(x<y){plot_circle_points(xc,yc,x,y,c);if(p<0)p=p+4*x+6;else{p=p+4*(xy)+10;y=1;}x+=1;}

52.2圓的生成算法if(x==y)plot_circle_points(xc,yc,x,y,c);}plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{set_pixel(xc+x,yc+y,c);set_pixel(xcx,yc+y,c);set_pixel(xc+x,ycy,c);set_pixel(xcx,ycy,c);set_pixel(xc+y,yc+x,c);

set_pixel(xcy,yc+x,c);set_pixel(xc+y,ycx,c);set_pixel(xcy,ycx,c);}62.3區(qū)域填充算法2.3.1基礎(chǔ)知識(shí)

區(qū)域填充即給出一個(gè)區(qū)域的邊界，要求對邊界范圍內(nèi)的所有像素單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色。

多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示7圖2.5掃描線與多邊形相交

圖2.6光柵化后直線變成離散點(diǎn)

多邊形填色一個(gè)首要的問題，是判斷一個(gè)像素是在多邊形內(nèi)還是多邊形外。數(shù)學(xué)上提供的方法是“掃描交點(diǎn)的奇偶數(shù)判斷法”。(掃描線與邊界相交奇數(shù)次后進(jìn)入該多邊形，相交偶數(shù)次后走出該多邊形。）

2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(shí)(續(xù)）

82.3區(qū)域填充算法填色算法分為兩大類：

⒈掃描線填色(Scan-LineFilling)算法。這類算法建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可用于交互填色。⒉種子填色(SeedFilling)算法。這類算法建立在多邊形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界內(nèi)一點(diǎn)的坐標(biāo)。所以，它一般只能用于人機(jī)交互填色，而難以用于程序填色。92.3區(qū)域填充算法2.3.2掃描線填色算法

算法的基本思想：多邊形以n、x_array、y_array的形式給出，其中，x_array、y_array中存放著多邊形的n個(gè)頂點(diǎn)的x，y坐標(biāo)。用水平掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多段定義成的多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。這些交點(diǎn)按照x坐標(biāo)進(jìn)行分類，將分類后的交點(diǎn)成對取出，作為兩個(gè)端點(diǎn)，以所需要填的色彩畫水平直線。多邊形被掃描完畢后，填色也就完成。102.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

需要解決或改進(jìn)的問題：⒈左、右頂點(diǎn)處理。左頂點(diǎn)2：y1<y2<y3

右頂點(diǎn)2：y1>y2>y3其中y1、y2、y3是3個(gè)相鄰的頂點(diǎn)的y坐標(biāo)。當(dāng)掃描線與多邊形的每個(gè)頂點(diǎn)相交時(shí)，會(huì)同時(shí)產(chǎn)生2個(gè)交點(diǎn)。這時(shí)，填色就會(huì)因掃描交點(diǎn)的奇偶計(jì)數(shù)出錯(cuò)而出現(xiàn)錯(cuò)誤。圖2.7多邊形的頂點(diǎn)

對所有左、右頂點(diǎn)作如下處理：左、右頂點(diǎn)的入邊(以該頂點(diǎn)為終點(diǎn)的那條邊，即1–2邊)之終點(diǎn)刪去。對于左頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(,y21)；對于右頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(,y2+1)；112.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

⒉

水平邊處理。水平邊(y1=y2)與水平掃描線重合無法求交點(diǎn)。因此，將水平邊畫出后刪去，不參加求交點(diǎn)及求交點(diǎn)以后的操作。

⒊掃描線與邊的求交點(diǎn)方法采用遞歸算法。以(x1,y1)、(x2,y2)為端點(diǎn)的邊與第i+1條掃描線的交點(diǎn)為此式表示交點(diǎn)不為(x1,y1)。否則，交點(diǎn)為(x1,y1)。⒋

減少求交計(jì)算量，采用活性邊表。對于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費(fèi)，需要加以改進(jìn)。122.3區(qū)域填充算法

活性邊表(ActiveListofSide)的采用將多邊形的邊分成兩個(gè)子集：與當(dāng)前掃描線相交的邊的集合，以及與當(dāng)前掃描線不相交的邊的集合。對后者不必進(jìn)行求交運(yùn)算，這樣就提高了算法的效率。圖2.8活性邊表及其指針的表示

132.3區(qū)域填充算法在上述線性表上加入兩個(gè)指針first和last，形成活性邊表。活性邊表中每個(gè)元素的內(nèi)容包括以下四項(xiàng)：邊的maxy值；與當(dāng)前掃描線相交的點(diǎn)的x坐標(biāo)值；邊的y方向當(dāng)前總長y2-y1；邊的斜率的倒數(shù)1/m?；钚赃叡碓诿扛鶔呙杈€掃描之后刷新。調(diào)整first和last指針之間的參加求交運(yùn)算的邊元素的值；調(diào)整first和last指針，以便使新邊進(jìn)入激活范圍?；钚赃叡順?gòu)成方法如下：將經(jīng)過左、右頂點(diǎn)處理并剔除水平邊后的多邊形各邊按照maxy值排序，存入一個(gè)線性表中。14程序結(jié)構(gòu)見課本32頁。掃描線填色算法優(yōu)、缺點(diǎn)：優(yōu)點(diǎn)：對于每個(gè)象素只訪問一次，輸入輸出的要求可降為最少；缺點(diǎn)：對于各種表的維持和排序的耗費(fèi)大。掃描線（y=4）：623057.540.5

ymaxxΔy1/m掃描線（y=3）：322-25740.5

p3p4

p2p3012345678

7654321p1p2p3p4p5p4p5p2p315邊填充算法（區(qū)域掃描轉(zhuǎn)換算法）基本思想：對每條掃描線和多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。（對每條邊作處理的順序隨意）p1p2p3p4p5算法優(yōu)、缺點(diǎn)：優(yōu)點(diǎn)：簡單，適用于具有禎緩存的圖形系統(tǒng)；缺點(diǎn)：每個(gè)象素可能被訪問多次，輸入輸出的量大。16柵欄填充算法對于每條掃描線與多邊形邊的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)。柵欄線優(yōu)點(diǎn)：減少了訪問次數(shù)172.3區(qū)域填充算法

種子填色又稱邊界填色(BoundaryFilling)。它的功能是，給出多邊形光柵化后的邊界位