第3章基本圖形生成算法

第三章基本圖形生成算法提出問(wèn)題

如何在指定的輸出設(shè)備上根據(jù)坐標(biāo)描述構(gòu)造基本二維幾何圖形（點(diǎn)、直線(xiàn)、圓、橢圓、多邊形域、字符串及其相關(guān)屬性等）。圖形生成算法基礎(chǔ)只有畫(huà)水平線(xiàn),垂直線(xiàn),及正方形對(duì)角線(xiàn)時(shí),象素點(diǎn)集的位置才是準(zhǔn)確的。在光柵顯示器上顯示一條直線(xiàn),實(shí)際上是用最靠近這條直線(xiàn)的象素點(diǎn)集來(lái)近似地表示這條直線(xiàn)。特點(diǎn)：畫(huà)點(diǎn)設(shè)備有限象素的矩陣光柵顯示器:

緩沖存儲(chǔ)器，顯示控制器，數(shù)/模轉(zhuǎn)換器，陰級(jí)射線(xiàn)管（CRT）。

A(x1,y1)、B(x2,y2)、圖形的生成：是在指定的輸出設(shè)備上，根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形。圖形的掃描轉(zhuǎn)換：在光柵顯示器等設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過(guò)程。

用一系列的象素點(diǎn)來(lái)逼近直線(xiàn)圖形的掃描轉(zhuǎn)換是完成圖形的參數(shù)表示形式(由圖形軟件包的使用者指定)到點(diǎn)陣表示形式(光柵顯示器刷新時(shí)所需要的表示形式)的轉(zhuǎn)換。

對(duì)圖形的掃描轉(zhuǎn)換一般分為兩個(gè)步驟：先確定有關(guān)像素，再用圖形的顏色或其他屬性對(duì)像素進(jìn)行某種寫(xiě)操作。研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字生成直線(xiàn)的一般要求：4.最后直線(xiàn)的生成速度要快；

1.象素是均勻分布的；

2.所畫(huà)的線(xiàn)應(yīng)是直的，且有精確的起點(diǎn)和終點(diǎn)；

3.所顯示的亮度應(yīng)沿直線(xiàn)不變，且與直線(xiàn)的長(zhǎng)度和方向無(wú)關(guān)；3.1

直線(xiàn)的掃描轉(zhuǎn)換數(shù)學(xué)上理想直線(xiàn)的特點(diǎn)：1.直線(xiàn)沒(méi)有寬度2.有無(wú)數(shù)個(gè)點(diǎn)構(gòu)成的集合DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)算法5.要求直線(xiàn)具有不同的色澤、亮度、線(xiàn)型等。已知端點(diǎn)A(x0,y0)、B(x1,y1),直線(xiàn)的微分方程：dy/dx=(y1-

y0)/(x1-x0)=k=常數(shù)

=k*xi+B+k*Δx

yi=k*xi+BΔx(x,round(y))yi+1=k*xi+1+B=k*(xi+Δx)+B光柵中Δx=1直線(xiàn)的遞推公式

yi+1＝y(tǒng)i+(y1-y0)/(x1-x0)xi+1＝xi+1yi+1＝y(tǒng)i+k*Δx3.1.1

DDA畫(huà)線(xiàn)算法程序(|k|≤1)通過(guò)同時(shí)對(duì)x,y各增加一個(gè)小的增量,計(jì)算下一步的x,y值。在一個(gè)迭代算法中,如果每一步的x,y值是用前一步的值加上一個(gè)增量來(lái)獲得,那么這種算法稱(chēng)為增量算法。DDA（DigitalDifferentialAnalyzer）畫(huà)線(xiàn)算法也稱(chēng)數(shù)值微分法，它的算法實(shí)質(zhì)是用數(shù)值方法解微分方程，通過(guò)同時(shí)對(duì)x和y各增加一個(gè)小增量，計(jì)算下一步的x、y值。例子討論:oxy|k|≤1yi+1=yi+1xi+1=xi+1/k(xi,yi)(xi+1,yi+1)oxy|k|>1(xi,yi)(xi+1,yi+1)造成隔行顯示xi+1=xi+1yi+1=yi+k結(jié)論：直線(xiàn)DDA算法：(round(xi+1),yi+1)yi+1=yi+1xi+1=xi+1/k|k|>1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+k|k|≤1逼近直線(xiàn)的象素點(diǎn)的坐標(biāo)直線(xiàn)上點(diǎn)的坐標(biāo)遞推公式直線(xiàn)的斜率起點(diǎn)（x1,y1），終點(diǎn)（x2,y2）(x2>x1,y2>y1)以（x1,y1）為起點(diǎn)DDA算法評(píng)價(jià)比直接使用公式

y=k*x+b快，沒(méi)有用乘法;設(shè)置增量的除法運(yùn)算、取整操作和浮點(diǎn)運(yùn)算仍然耗時(shí)，不利于硬件實(shí)現(xiàn)；DDA算法是一個(gè)增量算法。

通過(guò)同時(shí)對(duì)x,y各增加一個(gè)小的增量,計(jì)算下一步的x,y值。在一個(gè)迭代算法中,如果每一步的x,y值是用前一步的值加上一個(gè)增量來(lái)獲得,那么這種算法稱(chēng)為增量算法。拋磚引玉

中點(diǎn)畫(huà)線(xiàn)法

Bresenham畫(huà)線(xiàn)算法假設(shè)斜率k在0、1之間。假設(shè)x坐標(biāo)為xp的各像素點(diǎn)中，與直線(xiàn)最近者已確定，為P（xp,yp），那么，下一個(gè)與直線(xiàn)最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）兩者之一。令M為P1和P2的中點(diǎn)，易知M的坐標(biāo)為（xp+1,yp+0.5）。設(shè)Q是理想直線(xiàn)與垂直線(xiàn)x=xp+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線(xiàn)近，應(yīng)取為下一個(gè)像素；否則應(yīng)取P1。3.1.2

中點(diǎn)畫(huà)線(xiàn)算法假設(shè)直線(xiàn)的起點(diǎn)和終點(diǎn)分別是(x0,y0)和(x1,y1)。則直線(xiàn)方程為：

F(x,y)=ax+by+c=0；其中a=y0-y1，b=x1-x0，c=x0y1-x1y0。該直線(xiàn)方程將平面分為三個(gè)區(qū)域：對(duì)于直線(xiàn)上的點(diǎn)，F(xiàn)(x,y)=0；對(duì)于直線(xiàn)上方的點(diǎn)F(x,y)>0；對(duì)于直線(xiàn)下方的點(diǎn)，F(xiàn)(x,y)<0。xyF(x,y)>0F(x,y)=0F(x,y)<0

直線(xiàn)將平面分為三個(gè)區(qū)域xyF(x,y)>0F(x,y)=0F(x,y)<0判別式：則有：

d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c中點(diǎn)畫(huà)線(xiàn)算法生成直線(xiàn)的原理QP2(xp+1,yp+1)P(xp,yp)P1(xp+1,yp)M(xp+1,yp+0.5)3<+=)0()0(1dydyy誤差項(xiàng)的遞推d≥0：d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+ad≥0P(xp,yp)(xp+1,yp+0.5)(xp+2,yp+0.5)結(jié)論：d的增量為a誤差項(xiàng)的遞推d<0：d2=F(xp+2,yp+1.5)=d+a+b=a(xp+2)+b(yp+1.5)+c

d<0P(xp,yp)(xp+1,yp+0.5)(xp+2,yp+1.5)結(jié)論：d的增量為a+b初始值d的計(jì)算d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b=a+0.5b0≤k≤1時(shí)中點(diǎn)畫(huà)線(xiàn)算法的算法步驟為：1.輸入直線(xiàn)的兩端點(diǎn)P0(x0,y0)和p1(x1,y1)。2.計(jì)算初始值a=y0-y1、b=x1-x0、d=a+0.5b、x=x0、y=y0；3.繪制點(diǎn)(x,y)。判斷d的符號(hào)；若d<0，則(x,y)更新為(x+1,y+1)，d更新為d+a+b；否則(x,y)更新為(x+1,y)，d更新為d+a。4.當(dāng)直線(xiàn)沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3。否則結(jié)束。改進(jìn)：用2d代替d1.輸入直線(xiàn)的兩端點(diǎn)P0(x0,y0)和p1(x1,y1)。2.計(jì)算初始值a=y0-y1、b=x1-x0

、d=2*a+b、x=x0、y=y0、d1=2*a、d2=2*(a+b)。3.繪制點(diǎn)(x,y)。判斷d的符號(hào)。若d<0，則(x,y)更新為(x+1,y+1)，d更新為d+d2；否則(x,y)更新為(x+1,y),d更新為d+d1。4.當(dāng)直線(xiàn)沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3。否則結(jié)束。程序因此，中點(diǎn)畫(huà)線(xiàn)算法的運(yùn)算速度很快，并適于用硬件實(shí)現(xiàn)。(1)不必計(jì)算直線(xiàn)的斜率，因此不必作除法；(2)不用浮點(diǎn)數(shù)，只用整數(shù)；(3)只有加法和乘2運(yùn)算,在計(jì)算機(jī)內(nèi)部是用位移操作實(shí)現(xiàn)的,效率高。中點(diǎn)畫(huà)線(xiàn)算法的優(yōu)點(diǎn)：中點(diǎn)畫(huà)線(xiàn)算法基本思想

:

借助于一個(gè)決策變量d的正負(fù)符號(hào),來(lái)確定下一個(gè)該點(diǎn)亮的象素點(diǎn)。算法總結(jié)假定直線(xiàn)段的0≤k≤1基本原理：3.1.3

Bresenham畫(huà)線(xiàn)算法

Brensemham算法繪制直線(xiàn)的原理ddddkkkkk誤差項(xiàng)的計(jì)算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1算法步驟：1.輸入直線(xiàn)的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、d=0、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.d更新為d+k，判斷d的符號(hào)。若d>0.5，則(x,y)更新為(x+1,y+1)，同時(shí)將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線(xiàn)沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1算法步驟為：1.輸入直線(xiàn)的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、e=-0.5、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.e更新為e+k，判斷e的符號(hào)。若e>0，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線(xiàn)沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)2：用2e△x來(lái)替換ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x算法步驟：1.輸入直線(xiàn)的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、e=-△x、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.e更新為e+2△y，判斷e的符號(hào)。若e>0，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-2△x；否則(x,y)更新為(x+1,y)。5.當(dāng)直線(xiàn)沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3和4。否則結(jié)束。程序因此，Bresenham畫(huà)線(xiàn)算法的運(yùn)算速度很快，并適于用硬件實(shí)現(xiàn)，是應(yīng)用最廣泛的畫(huà)直線(xiàn)算法。(1)不必計(jì)算直線(xiàn)的斜率，因此不必作除法；(2)不用浮點(diǎn)數(shù)，只用整數(shù)；(3)只有加法和乘2運(yùn)算,在計(jì)算機(jī)內(nèi)部是用位移操作實(shí)現(xiàn)的,效率高。Bresenham畫(huà)線(xiàn)算法的優(yōu)點(diǎn)：算法總結(jié)研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字3.2.1簡(jiǎn)單方程產(chǎn)生圓弧算法原理：利用其函數(shù)方程，直接離散計(jì)算[]

)(2R0,

x121211+++-=?+=iiiixRroundyxx3.2

圓的掃描轉(zhuǎn)換解決的問(wèn)題：繪出圓心在原點(diǎn)，半徑為整數(shù)R的圓x2+y2==R2圓的極坐標(biāo)方程為：

)sin(

)cos()(

11111+++++==DD+=iiiiiiRroundyRroundxqqqqqq為一固定角度步長(zhǎng)圓的標(biāo)準(zhǔn)方程包括乘法和平方根運(yùn)算；圓的極坐標(biāo)參數(shù)方程包含乘法和三角運(yùn)算。存在問(wèn)題yx3.2

圓的掃描轉(zhuǎn)換3.2.2圓的對(duì)稱(chēng)性(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,y)yy=-xy=xyy=x1/8圓弧xR3.2.3

中點(diǎn)畫(huà)圓法構(gòu)造函數(shù)F(x,y)=x2+y2-R2。R為整數(shù)。對(duì)于圓上的點(diǎn)，有F(x,y)=0；對(duì)于圓外的點(diǎn)，F(xiàn)(x,y)>0；而對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)(x,y)<0。當(dāng)d≤0時(shí)，下一點(diǎn)取Pu(xi

+1,yi)；當(dāng)d>0時(shí)，下一點(diǎn)取Pd(xi

+1,yi-1)。M的坐標(biāo)為：M(xi

+1,yi-0.5)當(dāng)F(xM,yM)<0時(shí)，取Pu(xi

+1,yi)當(dāng)F(xM,yM)>0時(shí)，取Pd(xi

+1,yi-1)當(dāng)F(xM,yM)=0時(shí)，約定取Pu。構(gòu)造判別式：xy中點(diǎn)畫(huà)圓算法原理PPuPdM算法原理誤差項(xiàng)的遞推，d≤0：

d>0：

判別式的初始值：算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1.25-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)x<y時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)：將1.25-R≈1-R(因?yàn)镽為整數(shù))，算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d≤0，則先將(x,y)更新為(x+1,y)，再將d更新為d+2x+3；否則先將(x,y)更新為(x+1,y-1)，再將d更新為d+2(x-y)+5。5.當(dāng)x<y時(shí)，重復(fù)步驟3和4。否則結(jié)束。程序?qū)嵗齈0=1-10=-9

P1=-9+2*1+1=-6P2=-6+2*2+1=-1P3=-1+2*3+1=6P4=6+2*(4-9)+1=-3P5=-3+2*5+1=8P6=8+2*(6-8)+1=5iPi(xi,yi)0-9(0,10)1-6(1,10)2-1(2,10)36(3,10)4-3(4,9)58(5,9)65(6,8)(7,7)中點(diǎn)畫(huà)圓法實(shí)例(r=10)012345678910012345678910思想判斷公式算法描述程序?qū)崿F(xiàn)舉例xkxk+1ykyk-1yk-23.2.4

Bresenham畫(huà)圓算法Bresenham

算法思想現(xiàn)在從A點(diǎn)開(kāi)始向右下方逐點(diǎn)來(lái)尋找弧AB要用的點(diǎn)。如圖中點(diǎn)Pi-1是已選中的一個(gè)表示圓弧上的點(diǎn)，根據(jù)弧AB的走向，下一個(gè)點(diǎn)應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離AB最近的點(diǎn)作為顯示弧AB的點(diǎn)。假設(shè)圓的半徑為R，顯然，當(dāng)xhi2+yhi2-R2≥R2-(xli2+yli2)時(shí)，應(yīng)該取Li

。否則取Hi

。令di=xhi2+yhi2+xli2+yli2-2R2顯然，當(dāng)di

≥0時(shí)應(yīng)該取Li

。否則，取Hi

。Pi-1HiLi應(yīng)取Hi還是取LiABBresenham畫(huà)圓算法公式推導(dǎo)剩下的問(wèn)題是如何快速的計(jì)算di

。設(shè)圖中Pi-1的坐標(biāo)為(xi-1,yi-1)

，則Hi和Li的坐標(biāo)為(xi,yi-1)和(xi,yi-1-1)

di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2+1Pi-1HiLi應(yīng)取Hi還是取LiBresenham畫(huà)圓算法公式推導(dǎo)當(dāng)di<0時(shí)->取Hi->

yi=yi-1

，則di+1=(xi+1)2+yi-12+(xi+1)2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2+1+4xi+2=di+4xi-1+6Pi-1HiLi應(yīng)取Hi還是取LiBresenham畫(huà)圓算法公式推導(dǎo)當(dāng)di

≥0時(shí)->取Li->yi=yi-1-1

，則di+1=(xi+1)2+(yi-1-1)2

+(xi+1)2+(yi-1-2)2-2R2=2xi2+2yi-12-2yi-1-2R2+1+4xi-4yi-1+6=di

+4(xi-1-yi-1)+10Pi-1HiLi應(yīng)取Hi還是取LiABBresenham畫(huà)圓算法公式推導(dǎo)

求di的初始值d0

di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2+1d0=2x02+2y-12-2y-1-2R2+1=2+2R2-2R-2R2+1=3-2RPi-1HiLi應(yīng)取Hi還是取Li注意：Pi-1(xi-1,yi-1)xi-1=0,yi-1=RXi=xi-1+1=1Bresenham畫(huà)圓算法的步驟1)

輸入圓半徑r和圓心(xc,yc)，

獲得第一個(gè)點(diǎn)：(x0,y0)=(0,R)2)計(jì)算P0=3–2R;3)根據(jù)公式計(jì)算Pk+1，確定下一點(diǎn)；

如果pk<0,選擇(xk+1,yk)

pk≥0,

選擇(xk+1,yk-1)4)確定對(duì)稱(chēng)點(diǎn)；5)重復(fù)步驟3)，直至x≥yBresenham畫(huà)圓算法舉例(R=10)P0=3-20=-17

P1=-17+4*0+6=-11P2=-11+4*1+6=-1P3=-1+4*2+6=13P4=13+4*(3-10)+10=-5P5=-5+4*4+6=17P6=17+4*(5-9)+10=11k0123456Pk-17-11-113-51711(xk,yk)(0,10)(1,10)(2,10)(3,10)(4,9)(5,9)(6,8)(7,7)Bresenham畫(huà)圓算法舉例(R=10)012345678910012345678910xyY=xBresenham算法以決策參數(shù)的增量計(jì)算為基礎(chǔ)，僅包括簡(jiǎn)單的整數(shù)處理。中點(diǎn)方法更易應(yīng)用于其他圓錐曲線(xiàn)，沿任何圓錐曲線(xiàn)所確定的像素位置，其誤差限制在像素分段的1/2以?xún)?nèi)。算法總結(jié)研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字3.3

橢圓的掃描轉(zhuǎn)換3.3.1橢圓的特征baxy

長(zhǎng)半軸為a，短半軸為b的標(biāo)準(zhǔn)橢圓(x,y)(x,-y)(-x,-y)(-x,y)對(duì)于橢圓上的點(diǎn)，有F(x,y)=0；對(duì)于橢圓外的點(diǎn)，F(xiàn)(x,y)>0；對(duì)于橢圓內(nèi)的點(diǎn)，F(xiàn)(x,y)<0。考慮橢圓圓心在原點(diǎn)，長(zhǎng)半軸為a短半軸為b的橢圓(a,b為整數(shù))以弧上斜率為－1的點(diǎn)作為分界將第一象限橢圓弧分為上下兩部分。

上半部分下半部分二分量相等的法向量第一象限的橢圓弧yx引理3-1：若在當(dāng)前中點(diǎn)，法向量的y分量比x分量大，即

而在下一個(gè)中點(diǎn)，不等號(hào)改變方向，則說(shuō)明橢圓弧從上部分轉(zhuǎn)入下部分。法向量:上半部分下半部分二分量相等的法向量第一象限的橢圓弧yx3.3.2

橢圓的中點(diǎn)算法算法原理:Pu橢圓的中點(diǎn)繪制算法原理yxPdPPlPrP先推導(dǎo)上半部分的橢圓繪制公式:p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)上半部分橢圓弧的繪制原理判別式：若d1≤0，取Pu(xi+1,yi);若d1>0，取Pd(xi+1,yi-1)p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)

上半部分橢圓弧的繪制原理誤差項(xiàng)的遞推d1≤0：誤差項(xiàng)遞推d1>0：判別式的初始值

B數(shù)值為初始化的y數(shù)值誤差項(xiàng)遞推演示（橢圓上半部分）再來(lái)推導(dǎo)橢圓弧下半部分的繪制公式。原理如下：p(xi,yi)pl(xi,yi-1)pr(xi+1,yi-1)M(xi+1,yi-0.5)下半部分橢圓弧的繪制原理判別式

:若d2>0，取Pl(xi,yi-1);若d2≤0，取Pr(xi+1,yi-1)p(xi,yi)pl(xi,yi-1)pr(xi+1,yi-1)M(xi+1,yi-0.5)下半部分橢圓弧的繪制原理誤差項(xiàng)的遞推d2>0：誤差項(xiàng)的遞推d2≤0：

注意：上半部分的終止判別；下半部分誤差項(xiàng)的初值；算法步驟：1.輸入橢圓的長(zhǎng)半軸a和短半軸b。2.計(jì)算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.繪制點(diǎn)(x,y)及其在四分象限上的另外三個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d≤0，則先將d更新為d+b2(2x+3)，再將(x,y)更新為(x+1,y)；否則先將d更新為d+b2(2x+3)+a2(-2y+2)，再將(x,y)更新為(x+1,y-1)。5.當(dāng)b2(x+1)<a2(y-0.5)時(shí)，重復(fù)步驟3和4。否則轉(zhuǎn)到步驟6。6.用上半部分計(jì)算的最后點(diǎn)(x,y)來(lái)計(jì)算下半部分中d的初值：7.繪制點(diǎn)(x,y)及其在四分象限上的另外三個(gè)對(duì)稱(chēng)點(diǎn)。8.判斷d的符號(hào)。若d≤0，則先將d更新為b2(2xi+2)+a2(-2yi+3)，再將(x,y)更新為(x+1,y-1)；否則先將d更新為d+a2(-2yi+3)，再將(x,y)更新為(x,y-1)。9.當(dāng)y>0時(shí)，重復(fù)步驟7和8。否則結(jié)束。程序?qū)嵗芯績(jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字3.4

多邊形的掃描轉(zhuǎn)換與區(qū)域填充簡(jiǎn)單邊界，例如多邊形，圓，橢圓以及其他簡(jiǎn)單曲線(xiàn)，通過(guò)掃描線(xiàn)與邊界交點(diǎn)確定填充區(qū)域。復(fù)雜邊界，從內(nèi)部給定位置開(kāi)始填充，遞歸填充直至邊界。掃描線(xiàn)填充算法掃描線(xiàn)多邊形填充算法（3.4.1）邊緣填充算法（3.4.2）邊緣填充算法柵欄填充算法邊標(biāo)志算法遞歸填充算法邊界填充算法（3.4.3）洪泛填充算法（3.4.4）3.4.1掃描線(xiàn)多邊形填充算法算法思想算法技巧如何處理奇數(shù)個(gè)交點(diǎn)？如何處理水平邊？如何計(jì)算交點(diǎn)坐標(biāo)？數(shù)據(jù)結(jié)構(gòu)算法描述

算法思想

掃描線(xiàn)自底向上掃描，計(jì)算掃描線(xiàn)與多邊形邊界的交點(diǎn)確定填充區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。一條掃描線(xiàn)的填充過(guò)程分為求交、排序、配對(duì)和填色四個(gè)步驟。x-掃描線(xiàn)算法填充多邊形xy213356789111234567891011121012算法技巧–交點(diǎn)數(shù)單調(diào)減單調(diào)增掃描線(xiàn)y1掃描線(xiàn)y2算法技巧–水平邊不計(jì)算水平邊和掃描線(xiàn)的交點(diǎn)算法技巧–交點(diǎn)坐標(biāo)計(jì)算交點(diǎn)坐標(biāo)計(jì)算

Yi+1=

Yi+

1

Xi+1=

xi+

1/mm=dy/dxYi+1yiXi+1xi數(shù)據(jù)結(jié)構(gòu)輸入?yún)?shù)頂點(diǎn)數(shù)以及頂點(diǎn)坐標(biāo)數(shù)據(jù)結(jié)構(gòu)有序邊表sortededgetable活化邊表activeedgetableBACC’DE01YAYDYCWindowheightAEABCDDECB最大Y值較低頂點(diǎn)X值1/m有序邊表構(gòu)建過(guò)程：按頂點(diǎn)輸入順序依次形成邊，存儲(chǔ)到每條邊最小Y值所對(duì)應(yīng)的掃描線(xiàn)位置（水平邊除外），相同最小Y值的邊按較低頂點(diǎn)X值升序排序。有序邊表typedef

structtEdge

{intyUpper;floatxIntersect;floatdxPerScan;struct

tEdge*next; }Edge;01YAYDYCWindowheightAEABCDDECB最大Y值較低頂點(diǎn)X值1/m活化邊表CDDEAEABABCC’DE掃描線(xiàn)Y把與當(dāng)前掃描線(xiàn)相交的邊稱(chēng)為活化邊，并把它們按與掃描線(xiàn)交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中,形成活化邊表。算法描述1)輸入多邊形頂點(diǎn)數(shù)及頂點(diǎn)坐標(biāo)；2)建立有序邊表；3)根據(jù)當(dāng)前掃描值建立活化邊表；4)求出掃描線(xiàn)與多邊形邊界交點(diǎn)，交點(diǎn)配對(duì)、填充；5)更新活化邊表并重新排序；6)進(jìn)入下一條掃描線(xiàn)，重復(fù)步驟3，直至掃描線(xiàn)值為窗口高度。算法步驟3.4.2

邊緣填充算法邊緣填充算法算法簡(jiǎn)單，但對(duì)于復(fù)雜圖型，每一象素可能被訪問(wèn)多次柵欄填充算法柵欄指的是一條過(guò)多邊形頂點(diǎn)且與掃描線(xiàn)垂直的直線(xiàn)。它把多邊形分為兩半。邊標(biāo)志算法分為兩個(gè)步驟：

(1)打標(biāo)記

(2)填充基本思想：幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線(xiàn)掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志。然后再采用和掃描線(xiàn)算法類(lèi)似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。使用一個(gè)布爾量inside來(lái)指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。算法過(guò)程：voidedgemark_fill(polydef,color)多邊形定義polydef；

intcolor;{對(duì)多邊形polydef

每條邊進(jìn)行直線(xiàn)掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線(xiàn)y)for(掃描線(xiàn)上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)

drawpixel(x,y,color);elsedrawpixel(x,y,background); }}用軟件實(shí)現(xiàn)時(shí)，掃描線(xiàn)算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。IDEA–填充區(qū)域邊界以一種顏色指定；從區(qū)域的一個(gè)內(nèi)部點(diǎn)開(kāi)始，由內(nèi)至外繪制直到邊界。適用于單色邊界3.4.3邊界填充算法填充方式4-連通8-連通問(wèn)題4連通有時(shí)不能完整填充算法的輸入：種子點(diǎn)坐標(biāo)(x,y)，填充色和邊界顏色。棧結(jié)構(gòu)實(shí)現(xiàn)4-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)檢查出棧象素的4-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。4-連通算法描述voidBoundaryFill4(intx,int

y,int

boundarycolor,int

fillcolor){intcolor=getPixel(x,y); if(color!=fillcolor&&color!=boundarycolor) { setPixel(x,y,fillcolor); BoundaryFill4(x,y+1,boundarycolor,fillcolor); BoundaryFill4(x,y-1,boundarycolor,fillcolor); BoundaryFill4(x-1,y,boundarycolor,fillcolor); BoundaryFill4(x+1,y,boundarycolor,fillcolor);}}邊界表示的4連通區(qū)域的遞歸填充算法:棧結(jié)構(gòu)實(shí)現(xiàn)8-連通邊界填充算法的算法步驟為：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。特點(diǎn)：把太多的象素壓入堆棧，堆?？臻g需求量非常大改進(jìn) 通過(guò)沿掃描線(xiàn)填充水平象素段，來(lái)代替處理4-鄰接點(diǎn)和8-鄰接點(diǎn)。沿掃描線(xiàn)填充水平象素段的4-連通邊界填充算法步驟：種子象素入棧；當(dāng)棧非空時(shí)作如下三步操作：(1)棧頂象素出棧；(2)填充出棧象素所在掃描行的連續(xù)象素段，直到遇到邊界象素為止，即每出棧一個(gè)象素，就對(duì)包含該象素的整個(gè)掃描線(xiàn)區(qū)間進(jìn)行填充；(3)在區(qū)間中檢查與當(dāng)前掃描線(xiàn)相鄰的上下兩條掃描線(xiàn)的有關(guān)象素是否全為邊界象素或已填充的象素，若存在非邊界、未填充邊界的象素，則把每一區(qū)間的最右象素取作種子象素入棧。IDEA–

填充區(qū)域以一種顏色指定；從指定的內(nèi)部點(diǎn)

(x,y)開(kāi)始，將填充色賦給顏色為給定內(nèi)部色的鄰接像素。適用于多色邊界3.4.4泛填充算法算法的輸入：種子點(diǎn)坐標(biāo)(x,y)，填充色和內(nèi)部點(diǎn)的顏色。算法原理：算法從指定的種子(x,y)開(kāi)始，用所希望的填充顏色賦給所有當(dāng)前為給定內(nèi)部顏色的象素點(diǎn)。8-連通泛填充算法步驟如下：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是給定內(nèi)部點(diǎn)的顏色且未置成新的填充色，則把該象素入棧。內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法:voidFloodFill4(intx,int

y,int

oldcolor,int

newcolor){if(getpixel(x,y)==oldcolor)//屬于區(qū)域內(nèi)點(diǎn)oldcolor { drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor);}}注意：當(dāng)以邊界表示時(shí)，4-連通邊界填充算法只能填充4-連通區(qū)域，8-連通邊界填充算法也只能填充8-連通區(qū)域。當(dāng)以?xún)?nèi)點(diǎn)表示時(shí)，8-連通泛填充算法可以填充8-連通區(qū)域也可以填充4-連通區(qū)域，當(dāng)然4-連通泛填充算法還是只能填充4-連通區(qū)域。3.4.5

其他相關(guān)的概念1.內(nèi)-外測(cè)試不自交的多邊形、自相交的多邊形奇-偶規(guī)則（Odd-evenRule）

從任意位置p作一條射線(xiàn)，若與該射線(xiàn)相交的多邊形邊的數(shù)目為奇數(shù)，則p是多邊形內(nèi)部點(diǎn)，否則是外部點(diǎn)。非零環(huán)繞數(shù)規(guī)則（NonzeroWindingNumberRule）首先使多邊形的邊變?yōu)槭噶?。將環(huán)繞數(shù)初始化為零。再?gòu)娜我馕恢胮作一條射線(xiàn)。當(dāng)從p點(diǎn)沿射線(xiàn)方向移動(dòng)時(shí)，對(duì)在每個(gè)方向上穿過(guò)射線(xiàn)的邊計(jì)數(shù)，每當(dāng)多邊形的邊從右到左穿過(guò)射線(xiàn)時(shí)，環(huán)繞數(shù)加1，從左到右時(shí)，環(huán)繞數(shù)減1。處理完多邊形的所有相關(guān)邊之后，若環(huán)繞數(shù)為非零，則p為內(nèi)部點(diǎn)，否則，p是外部點(diǎn)。研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字3.52D裁剪裁剪定義Clipping

識(shí)別圖形在指定區(qū)域內(nèi)或區(qū)域外的過(guò)程->裁剪裁剪的時(shí)機(jī)

(1)針對(duì)窗口邊界裁剪

(2)針對(duì)視區(qū)邊界裁剪裁剪類(lèi)型點(diǎn)裁剪直線(xiàn)裁剪多邊形區(qū)域裁剪曲線(xiàn)裁剪（自學(xué)）文字裁剪3.5.1

點(diǎn)的裁剪點(diǎn)(x,y)如果滿(mǎn)足下列不等式則保留：w1<=x<=w2

w3<=y<=w4w1w2w3w4(x,y)3.5.2直線(xiàn)段的裁剪假定直線(xiàn)段用p1(x1,y1)p2(x2,y2)表示。直線(xiàn)段和剪裁窗口的可能關(guān)系：完全落在窗口內(nèi)完全落在窗口外與窗口邊界相交

窗口

直線(xiàn)段與窗口的關(guān)系A(chǔ)BCDEFHGIJ實(shí)交點(diǎn)是直線(xiàn)段與窗口矩形邊界的交點(diǎn)。虛交點(diǎn)則是直線(xiàn)段與窗口矩形邊界延長(zhǎng)線(xiàn)或直線(xiàn)段的延長(zhǎng)線(xiàn)與窗口矩形邊界的交點(diǎn)。

窗口

實(shí)交點(diǎn)與虛交點(diǎn)ABCDEFHGIJ虛交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)實(shí)交點(diǎn)虛交點(diǎn)虛交點(diǎn)Cohen-Sutherland直線(xiàn)裁剪算法Liang梁友棟-Barsky直線(xiàn)裁剪算法中點(diǎn)分割算法Nicholl-Lee-Nicholl直線(xiàn)裁剪算法Cyrus-Beck算法（自學(xué)）直線(xiàn)段的裁剪算法1.Cohen-Sutherland直線(xiàn)裁剪算法基本思想：直線(xiàn)由端點(diǎn)標(biāo)識(shí)；測(cè)試直線(xiàn)端點(diǎn)和窗口邊界的關(guān)系以確定是否需要計(jì)算交點(diǎn)

；CS編碼方案擴(kuò)展窗口的邊界將整個(gè)2D平面劃分為9個(gè)區(qū)域每個(gè)區(qū)域賦予一個(gè)4位編碼,稱(chēng)為區(qū)域碼000001100100010100100001100110001010上下右左w1w2w3w4編碼規(guī)則b0=1iffx<w1b1=1iff

x>w2b2=1iffy<w3b3=1iffy>w4000001100100010100100001100110001010上下右左w1w2w3w4算法描述計(jì)算直線(xiàn)端點(diǎn)編碼,c1和c2;判斷c1和c2均為0000，保留直線(xiàn)c1&c2不為零，同在某一邊界外，刪除該直線(xiàn)c1和c2不均為0000

且c1&c2為零，需要進(jìn)一步求解交點(diǎn)以L,R,B,T為序，將x=w1/w2或y=w3/w4帶入直線(xiàn)方程，計(jì)算直線(xiàn)與窗口邊界的交點(diǎn)，將交點(diǎn)和另一端點(diǎn)重復(fù)上述過(guò)程，直至線(xiàn)段保留或刪除CS線(xiàn)段裁剪算法舉例P3P41000001100100010100100001100110001010CS線(xiàn)段裁剪算法舉例132P1P2000001100100010100100001100110001010算法的步驟：(1)輸入直線(xiàn)段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。(2)對(duì)p1、p2進(jìn)行編碼：點(diǎn)p1的編碼為code1，點(diǎn)p2的編碼為code2。(3)若code1|code2=0，對(duì)直線(xiàn)段應(yīng)簡(jiǎn)取之，轉(zhuǎn)(6)；否則，若code1&code2≠0，對(duì)直線(xiàn)段可簡(jiǎn)棄之，轉(zhuǎn)(7)；當(dāng)上述兩條均不滿(mǎn)足時(shí)，進(jìn)行步驟(4)。(4)確保p1在窗口外部：若p1在窗口內(nèi)，則交換p1和p2的坐標(biāo)值和編碼。(5)按左、右、上、下的順序求出直線(xiàn)段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的坐標(biāo)值替換p1的坐標(biāo)值。也即在交點(diǎn)s處把線(xiàn)段一分為二，并去掉p1s這一段?？紤]到p1是窗口外的一點(diǎn)，因此可以去掉p1s。用p1替代s轉(zhuǎn)(2)。(6)用直線(xiàn)掃描轉(zhuǎn)換算法畫(huà)出當(dāng)前的直線(xiàn)段p1p2。(7)算法結(jié)束。

計(jì)算線(xiàn)段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn)

if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}程序?qū)崿F(xiàn)p1p2p3p41321舉例。程序流程圖優(yōu)點(diǎn)：簡(jiǎn)單，易于實(shí)現(xiàn)。算法中求交點(diǎn)的次數(shù)決定了算法的速度，最壞要求交三次，反復(fù)循環(huán)。在裁剪窗口非常大或非常小時(shí)效率很高。CS線(xiàn)段裁剪算法小結(jié)2Liang-Barsky直線(xiàn)裁剪算法思想：基于直線(xiàn)段參數(shù)方程分析的快速直線(xiàn)裁剪算法。參數(shù)方程

直線(xiàn)兩端點(diǎn)P1(x1,y1),P2(x2,y2) x=x1+(x2-x1)u y=y1+(y2-y1)u,0≤u≤1已知直線(xiàn)端點(diǎn)：起點(diǎn)P1(x1,y1)，終點(diǎn)P2(x2,y2)參數(shù)方程： x=x1+(x2-x1)u y=y1+(y2-y1)u

P1P2u<00≤u≤1u>1LB算法推導(dǎo)

如果直線(xiàn)在窗口內(nèi),則

w1≤x1+dx*u≤w2 w3≤y1+dy*u≤w4

統(tǒng)一表示為：Pk

*u≤

Qkk=1,2,3,4P1=-dx,Q1=x1-w1P2=dx,Q2=w2-x1P3=-dy,Q3=y1-w3P4=dy,Q4=w4-y1w1w2w3w4ubulutur01dxdyP1=-dx,Q1=x1-w1P2=dx,Q2=w2-x1P3=-dy,Q3=y1-w3P4=dy,Q4=w4-y1算法描述計(jì)算Pk,Qk,k=1~4Pk=0，表示直線(xiàn)平行于窗口某邊界Qk<0，（任一小于零）直線(xiàn)完全在窗口外，被裁剪Qk>=0，直線(xiàn)在窗口內(nèi)，平行邊界內(nèi)對(duì)Pk<>0的情形,用Qk/Pk計(jì)算交點(diǎn)所對(duì)應(yīng)的u值對(duì)每條線(xiàn)計(jì)算參數(shù)u1&u2u1=Max({Qk/Pk|Pk<0}

U

{0})u2=Min({Qk/Pk|Pk>0}

U

{1})如果u1>u2,則直線(xiàn)在窗口外，否則計(jì)算交點(diǎn)坐標(biāo)

x(u)=x1+dx*uy(u)=y1+dy*uLB線(xiàn)段裁剪算法例1已知線(xiàn)段的兩個(gè)端點(diǎn)P1(3,4)，P2(8,2)

窗口邊界x=1,x=4,y=1,y=3用LB算法對(duì)線(xiàn)段進(jìn)行裁剪線(xiàn)段的參數(shù)方程x=3+5u y=4-2uP1=-5,Q1=2,R1=-2/5 P2=5,Q2=1,R2=1/5 P3=2,Q3=3,R3=3/2 P4=-2,Q4=-1,R4=1/2u1=max(0,-2/5,1/2)=1/2 u2

=

min(1,

1/5,

3/2)

=

1/5u1>u2

所以線(xiàn)段全部被裁剪線(xiàn)段的兩個(gè)端點(diǎn)（-2，-1）和（1，1.5）窗口邊界x1=-1,x2=1,y1=-1,y2=1LB線(xiàn)段裁剪算法例2△x=3,△y=2.5p1=-3 q1=-1 r1=1/3p2=3 q2=3 r2=1p3=-2.5 q3=0 r3=0p4=2.5 q4=2 r1=4/5對(duì)于p<0，u1=max{0，1/3，0}=1/3對(duì)于p>0，u2=min{1，1，4/5}=4/5則u1<u2，則可見(jiàn)線(xiàn)段的端點(diǎn)坐標(biāo)：x=x1+u1△x=-1,y=y1+u1△y=-1/6

即(-1,-1/6)x=x1+u2△x=2/5,y=y1+u2

△y=1

即(2/5,1)voidLB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;{ floatdx,dy,u1,u2;

tl=0;tu=1; dx=x2-x1;dy=y2-y1;if(ClipT(-dx,x1-Xl,&u1,&u2)if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)if(ClipT(dy,YT-y1,&u1,&u2){ displayline(x1+u1*dx,y1+u1*dy,x1+u2*dx,y1+u2*dy) return; }}程序?qū)崿F(xiàn)boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;if(p<0){ r=q/p; if(r>*u2)returnFALSE; elseif(r>*u1) { *u1=r; returnTRUE; }}

。。。//下頁(yè)elseif(p>0){ r=p/q; if(r<*u1)returnFALSE; elseif(r<*u2){ *u2=r;returnTRUE;}}elseif(q<0)returnFALSE;returnTRUE;}LBvs.CS LB效率高于CS,因?yàn)闇p少了交點(diǎn)計(jì)算次數(shù)。

參數(shù)u1和u2的更新需要四次除法,交點(diǎn)坐標(biāo)計(jì)算至多4次乘法。Liang-Barsky和Cohen-Sutherland算法很容易擴(kuò)展為三維裁剪算法3中點(diǎn)分割裁剪算法基本思想：與前一種Cohen-Sutherland算法一樣首先對(duì)線(xiàn)段端點(diǎn)進(jìn)行編碼，并把線(xiàn)段與窗口的關(guān)系分為三種情況:全在、完全不在和線(xiàn)段和窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)分割的方法求出線(xiàn)段與窗口的交點(diǎn)。求線(xiàn)段與窗口的交點(diǎn)A、B分別為距P0、P1最近的可見(jiàn)點(diǎn)，Pm為P0P1中點(diǎn)問(wèn)：算法為什么可行？會(huì)不會(huì)無(wú)限循環(huán)、不斷二分？從出發(fā)找最近可見(jiàn)點(diǎn)的方法先求出的中點(diǎn)若不是顯然不可見(jiàn)的，并且在窗口中有可見(jiàn)部分，則距最近的可見(jiàn)點(diǎn)一定落在上，所以用代替；否則取代替再對(duì)新的求中點(diǎn)。重復(fù)上述過(guò)程，直到長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí)收斂于交點(diǎn)。從出發(fā)找最近可見(jiàn)點(diǎn)采用上面類(lèi)似方法。 中點(diǎn)分割算法的核心思想是通過(guò)二分逼近來(lái)確定直線(xiàn)段與窗口的交點(diǎn)。舉例4NLN直線(xiàn)裁剪算法IDEA

通過(guò)在裁剪窗口周?chē)鷦?chuàng)立多個(gè)區(qū)域，并在求交運(yùn)算之前進(jìn)行更多的區(qū)域測(cè)試，從而避免對(duì)直線(xiàn)段進(jìn)行多次剪裁。適用范圍僅僅適用于2D剪裁算法步驟從P1點(diǎn)向窗口的四個(gè)角點(diǎn)發(fā)出射線(xiàn)，這四條射線(xiàn)和窗口的四條邊界直線(xiàn)一起將二維平面劃分為更多的小區(qū)域。線(xiàn)段端點(diǎn)P1的三種位置Case1Case2Case3ACase3BP2位置?

比較直線(xiàn)段P1P2的斜率和剪裁區(qū)域邊界的斜率.yt-y1y2-y1yt-y1xr-x1x2-x1xl-x1交點(diǎn)計(jì)算p2裁剪類(lèi)型點(diǎn)裁剪直線(xiàn)裁剪多邊形區(qū)域裁剪曲線(xiàn)裁剪（自學(xué)）文字裁剪3.5.3

多邊形的裁剪問(wèn)題的提出：

裁剪算法Sutherland-Hodgman

算法Weiler-Atherton算法多邊形的裁剪算法1.Sutherland-Hodgeman多邊形裁剪基本思想：以多邊形頂點(diǎn)為初始集合,首先用窗口左邊界剪裁多邊形，產(chǎn)生新的頂點(diǎn)序列。新的頂點(diǎn)集依次傳給右邊界、下邊界和上邊界進(jìn)行處理。SH算法最終輸出定義剪裁后的多邊形邊界的頂點(diǎn)序列。輸入：ABCDEFGHABCDEFGH輸出：A12DEFGH12用左邊界裁剪ADGH1用上邊界裁剪345678輸入：A134D5678GH輸出：K34D56789IHJ9IJK沿多邊形依次處理頂點(diǎn)有四種情況 剪裁情況一Sout,Pin;由外至內(nèi)輸出i和p

P:secondoutputSINOUTi:firstoutput剪裁情況二S&Pbothin；由內(nèi)至內(nèi)輸出PPolygonbeingclippedP:outputClipboundarySINOUT剪裁情況三Sin,Pout由內(nèi)至外輸出iINOUTSioutputP剪裁情況四S&Pbothout由外至外無(wú)頂點(diǎn)輸出

(nooutput)PSINOUT123456窗口左邊界Example1234561'2'3'4'5'窗口左邊界1234561'2'3'4'5'窗口左邊界算法改進(jìn)

只有當(dāng)窗口的四個(gè)邊界都確定一個(gè)點(diǎn)在窗口內(nèi)時(shí)才加入到輸出頂點(diǎn)表中V1V2V3V1’V2’V2’’V3’問(wèn)題

SH算法適用于凸多邊形多余線(xiàn)段Weiler-Atherton算法

2Weiler-Atherton多邊形裁剪算法思想：通過(guò)修改多邊形頂點(diǎn)處理順序(考慮頂點(diǎn)處理方向)，從而正確顯示凹多邊形。若順時(shí)針處理多邊形頂點(diǎn)，采用下列規(guī)則：對(duì)由外到內(nèi)的頂點(diǎn)對(duì)，沿著多邊形邊界的方向；對(duì)由內(nèi)到外的頂點(diǎn)對(duì)，按順時(shí)針沿窗口邊界的方向。Weiler算法適用于任意多邊形裁剪區(qū)域Weiler-Atherton算法步驟假定按順時(shí)針?lè)较蛱幚眄旤c(diǎn)，且將用戶(hù)多邊形定義為Ps，窗口矩形為Pw。算法從Ps的任一點(diǎn)出發(fā)，跟蹤檢測(cè)Ps的每一條邊，當(dāng)Ps與Pw相交時(shí)（實(shí)交點(diǎn)），按如下規(guī)則處理：(1)若是由不可見(jiàn)側(cè)進(jìn)入可見(jiàn)側(cè)，則輸出可見(jiàn)直線(xiàn)段，轉(zhuǎn)(3)；(2)若是由可見(jiàn)側(cè)進(jìn)入不可見(jiàn)側(cè)，則從當(dāng)前交點(diǎn)開(kāi)始，沿窗口邊界順時(shí)針檢測(cè)Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當(dāng)前交點(diǎn)的另一交點(diǎn)，輸出可見(jiàn)直線(xiàn)段和由當(dāng)前交點(diǎn)到另一交點(diǎn)之間窗口邊界上的線(xiàn)段，然后返回處理的當(dāng)前交點(diǎn)；(3)沿著Ps處理各條邊，直到處理完P(guān)s的每一條邊，回到起點(diǎn)為止。下圖示了Weiler-Atherton算法裁剪凹多邊形的過(guò)程和結(jié)果。ABCDECEV1V2V3V4V1V2V3V4

Weiler-Atherton算法裁剪凹多邊形(a)裁剪前(b)Weiler-Atherton算法的裁剪結(jié)果返回返回3.5.4

其它裁剪1.曲線(xiàn)邊界對(duì)象的裁剪曲線(xiàn)邊界對(duì)象與矩形窗口和多邊形窗口的裁剪加速方法;2.文字裁剪 文字裁剪的策略包括幾種：串精度裁剪字符精度裁剪筆劃、象素精度裁剪

3.外部裁剪 保留落在裁剪區(qū)域外的圖形部分、去掉裁剪區(qū)域內(nèi)的所有圖形，這種裁剪過(guò)程稱(chēng)為外部裁剪，也稱(chēng)空白裁剪。字符裁剪串精度:將包圍字串的外接矩形對(duì)窗口作裁剪字符精度:將包圍字的外接矩形對(duì)窗口作裁剪以及筆畫(huà)\象素精度:將筆劃分解成直線(xiàn)段對(duì)窗口作裁剪

待裁剪字符串 串精度裁剪 字符精度裁剪象素精度裁剪研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充2D裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字字符指數(shù)字、字母、漢字等符號(hào)。計(jì)算機(jī)中字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)?！懊绹?guó)信息交換用標(biāo)準(zhǔn)代碼集”簡(jiǎn)稱(chēng)ASCII碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128個(gè)字符漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集。每個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼（2字節(jié)）共同標(biāo)識(shí)。3.6字符處理基本術(shù)語(yǔ)字體：一組字符的完整設(shè)計(jì)風(fēng)格字模：一組按照特定尺寸和風(fēng)格設(shè)計(jì)的字符模板圖案。字符字模構(gòu)成方式點(diǎn)陣式-----位圖字體矢量式-----輪廓字體字庫(kù)：儲(chǔ)存每個(gè)字符的字模編碼信息，分為矢量字庫(kù)和點(diǎn)陣字庫(kù)兩大類(lèi)型。Def.-采用逐位映射的方式得到字符的字模編碼Example特點(diǎn)易于定義顯示空間需求量大100xFC0x660x660x7C0x660x660xFC0x003.6.1點(diǎn)陣字符

在點(diǎn)陣表示中，每個(gè)字符由一個(gè)點(diǎn)陣位圖來(lái)表示。顯示時(shí)：形成字符的象素圖案字符A的點(diǎn)陣表示111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000(a)字符A的點(diǎn)陣位圖(a)字符A的象素圖案Def.-將字符筆畫(huà)分解為線(xiàn)段，以線(xiàn)段端點(diǎn)坐標(biāo)為字符字模的編碼.3.6.2矢量字符012345670123456700505061616262535364646565565606101620262353012345670123456700505061616262535364646565565606101620262353特點(diǎn)

空間需求量小時(shí)間開(kāi)銷(xiāo)大Example矢量字符采用直線(xiàn)和曲線(xiàn)段來(lái)描述字符形狀，矢量字符庫(kù)中記錄的是筆劃信息。具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。對(duì)于字符的旋轉(zhuǎn)、縮放等變換，顯示時(shí)首先從字庫(kù)中將它的字符信息取出，然后取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。特點(diǎn)：點(diǎn)陣字符：存儲(chǔ)量大，易于顯示矢量字符：存儲(chǔ)量小，美觀，變換方便;但需要光柵化后才能顯示。點(diǎn)陣字符點(diǎn)陣字庫(kù)中的位圖表示矢量輪廓字符總結(jié)研究?jī)?nèi)容直線(xiàn)的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充裁剪字符的處理屬性處理反走樣DDA畫(huà)線(xiàn)法中點(diǎn)畫(huà)線(xiàn)法Bresenham畫(huà)線(xiàn)法中點(diǎn)畫(huà)圓法Bresenham畫(huà)圓法中點(diǎn)畫(huà)橢圓法掃描線(xiàn)多邊形填充算法邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法邊界填充算法泛填充算法掃描線(xiàn)填充遞歸填充Cohen-Sutherland算法中點(diǎn)分割算法Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法Sutherland-Hodgeman多邊形裁剪算法Weiler-Atherton多邊形裁剪算法直線(xiàn)段多邊形文字3.7

屬性處理3.7.1

線(xiàn)型和線(xiàn)寬1.線(xiàn)型處理LineType線(xiàn)型Howto?繪制像素段Pixelmask像素掩碼eg.1111000Problem

根據(jù)直線(xiàn)斜率調(diào)整實(shí)心段和空白段的像素?cái)?shù)目解決:可根據(jù)線(xiàn)的斜率來(lái)調(diào)整實(shí)心段和中間空白段的象素?cái)?shù)目。xy213456789111234567891011121012a相同數(shù)目象素顯示的不等長(zhǎng)劃線(xiàn)b2線(xiàn)寬處理LineWidthHowto?

顯示相鄰平行線(xiàn)段類(lèi)型

(1)水平或垂直方向擴(kuò)展

(2)矩形區(qū)域填充

(3)畫(huà)筆或畫(huà)刷|m|<1(x,y)&(x,y+1)|m|>1(x,y)&(x+1,y)&(x-1,y)&(x-2,y)特點(diǎn)實(shí)現(xiàn)簡(jiǎn)單、效率高。斜線(xiàn)與水平(或垂直)線(xiàn)不一樣粗。當(dāng)線(xiàn)寬為偶數(shù)個(gè)象素時(shí)，線(xiàn)的中心將偏移半個(gè)象素。利用線(xiàn)刷子生成線(xiàn)的始末端總是水平或垂直的，看起來(lái)不太自然。解決：添加“線(xiàn)帽（linecap）”線(xiàn)“帽子”(a)方帽(c)圓帽(b)突方帽調(diào)整平行線(xiàn)的端點(diǎn)位置，使粗線(xiàn)顯示具有垂直于線(xiàn)路徑的方端線(xiàn)段向兩頭延伸一半線(xiàn)寬并添加方帽子方帽兩端添加填充的半圓其他線(xiàn)寬處理方式(畫(huà)筆和畫(huà)刷)Shape形狀Size尺寸Pattern樣式PixelMask3.LineColor4.曲線(xiàn)的線(xiàn)型和線(xiàn)寬Pixelmaskseg.11100根據(jù)曲線(xiàn)斜率設(shè)置像素掩碼的實(shí)心段和空白段像素?cái)?shù)目Curvewidth

水平(|m|>1)或垂直(|m|<1)像素段Pen&BrushoptionsEg.Rectangularpen3x3字體 宋體仿宋體

楷體

黑體隸書(shū)字高宋體

宋體宋體宋體宋體字寬字傾斜角 傾斜傾斜對(duì)齊(左對(duì)齊、中心對(duì)齊、右對(duì)齊)字色紅色、綠色、藍(lán)色……3.7.2字符的屬性3.7.3

區(qū)域填充屬性區(qū)域填充屬性選擇包括顏色、圖案和透明度。001010111(a)圖案模板位圖(b)用該模板進(jìn)行填充

利用圖案模板進(jìn)行三角形的填充模板圖案根據(jù)圖案和透明度屬性來(lái)填充平面區(qū)域的基本思想是：首先用模板定義各種圖案。然后，修改填充的掃描轉(zhuǎn)換算法：在確定了區(qū)域內(nèi)一象素之后，不是馬上往該象素填色而是先查詢(xún)模板位圖的對(duì)應(yīng)位置。若是以透明方式填充圖案，則當(dāng)模