第五章變換和裁剪

第五章變換和裁剪第五章變換和裁剪幾何變換觀察角度和物體位置的改變可以通過(guò)在世界坐標(biāo)系中對(duì)物體進(jìn)行各種變換來(lái)實(shí)現(xiàn)，如平移、放縮、旋轉(zhuǎn)等。

二維窗口的裁剪選擇顯示的內(nèi)容--圖形在窗口內(nèi)的部分被顯示出來(lái)，窗口外的部分被裁剪掉裁剪算法：Sutherland-Cohen算法、Cyrus-Beck算法、梁友棟-Barsky算法、Sutherland-Hodgman算法等。

5.1變換的數(shù)學(xué)基礎(chǔ)

一點(diǎn)在坐標(biāo)系中的坐標(biāo)，就是該點(diǎn)在坐標(biāo)軸上的垂直投影。三維空間中兩點(diǎn)和之間的距離是：圖5.1二維點(diǎn)的坐標(biāo)p(x,y)xy2矢量

矢量是一個(gè)n元組，對(duì)應(yīng)于n維空間中的一個(gè)點(diǎn)?？梢源砦矬w在空間的位置，運(yùn)動(dòng)狀態(tài)等。

矢量的運(yùn)算（以三維矢量為例）幾個(gè)基本概念：3矩陣階矩陣A定義為

1點(diǎn)，可記為或矩陣的性質(zhì)

5.2幾何變換坐標(biāo)系世界坐標(biāo)系（worldcoordinate）:一個(gè)圖形場(chǎng)景往往由多個(gè)對(duì)象組成，為了描述它們之間的空間關(guān)系，需要把它們置于一個(gè)統(tǒng)一的坐標(biāo)系中，該坐標(biāo)系稱為世界坐標(biāo)系。模型坐標(biāo)系（modelingcoordinate）或局部坐標(biāo)系（localcoordinate）：當(dāng)構(gòu)造單個(gè)對(duì)象的數(shù)字模型時(shí)，為了方便可以將其置于一個(gè)特定的坐標(biāo)系下，即模型坐標(biāo)系或局部坐標(biāo)系。設(shè)備坐標(biāo)系（devicecoordinate）：圖形輸出時(shí)，則應(yīng)在輸出設(shè)備上建立一個(gè)坐標(biāo)系，這個(gè)坐標(biāo)系稱為設(shè)備坐標(biāo)系。設(shè)備坐標(biāo)系依據(jù)設(shè)備的種類有不同的形式，如二維的屏幕坐標(biāo)系，描述機(jī)械手運(yùn)動(dòng)軌跡的三維坐標(biāo)系。標(biāo)準(zhǔn)化設(shè)備坐標(biāo)系（normalizeddevicecoordinate）：有些圖形系統(tǒng)，對(duì)設(shè)備坐標(biāo)系進(jìn)行了規(guī)范化，將坐標(biāo)范圍限定在區(qū)間{x,y,z|0≤x≤1,0≤y≤1,0≤z≤1}內(nèi)，稱為標(biāo)準(zhǔn)化設(shè)備坐標(biāo)系。

5.2幾何變換本節(jié)討論的變換適用于任何直角坐標(biāo)系。點(diǎn)由點(diǎn)(x,y,z)在x,y和z軸方向分別移動(dòng)距離Δx,Δy和Δz得到。兩點(diǎn)坐標(biāo)間的關(guān)系為：(5.2)1平移變換

其矩陣形式為：在OpenGL中使用如下函數(shù)進(jìn)行平移變換：voidglTranslate{fd}(TYPEx,TYPEy,TYPEz);其中{fd}表示x、y、z的數(shù)據(jù)類型為float型或double型（下同），x、y和z分別為沿坐標(biāo)軸x、y和z的平移量。

(5.1)世界坐標(biāo)系中的各種幾何變換可用本節(jié)討論的方法來(lái)實(shí)現(xiàn)。2放大和縮小變換

其中sx,sy和sz

分別為沿x,y和z軸方向放縮的比例。其矩陣形式是在OpenGL中使用如下函數(shù)進(jìn)行放縮變換：voidglScale{fd}(TYPEx,TYPEy,TYPEz);其中x、y、z分別為沿三個(gè)坐標(biāo)軸方向的放縮比例因子。

(5.4)設(shè)點(diǎn)(x,y,z)經(jīng)縮放變換后得點(diǎn)

。兩點(diǎn)坐標(biāo)間的關(guān)系為(5.3)2放大和縮小變換放縮變換必定有一個(gè)不動(dòng)點(diǎn)，為了定義放縮變換，可以指定其不動(dòng)點(diǎn)，一個(gè)放縮方向，以及沿該方向的放縮因子。當(dāng)放縮因子大于1時(shí)，對(duì)象在指定方向上變長(zhǎng)

以圖形中心為中心的放縮變換為了使縮放變換后的圖形仍在原來(lái)位置附近，可另外定義一個(gè)相似中心點(diǎn)(xp,yp,zp)把整個(gè)圖形沿x,y和z方向平移-xp,-yp和-zp,使相似中心移到坐標(biāo)原點(diǎn)對(duì)每一點(diǎn)按照式(5.4)作變換沿x,y和z方向平移xp,yp和zp,把經(jīng)過(guò)放縮的圖形移回原處這樣做的綜合效果是圖形以(xp,yp,zp)為中心作了放縮變換。以(xp,yp,zp)為中心的放縮變換

3旋轉(zhuǎn)變換它繞z軸旋轉(zhuǎn)α角后，可得點(diǎn)設(shè)給定點(diǎn)的坐標(biāo)為:該變換的矩陣形式為3旋轉(zhuǎn)變換3旋轉(zhuǎn)變換繞y軸的旋轉(zhuǎn)變換公式為:設(shè)給定點(diǎn)的坐標(biāo)為:3旋轉(zhuǎn)變換繞x軸的旋轉(zhuǎn)變換公式為:設(shè)給定點(diǎn)的坐標(biāo)為:yp繞過(guò)原點(diǎn)的軸的旋轉(zhuǎn)變換

圖5.7

新坐標(biāo)系ouvwyuvwxzo對(duì)繞空間任一通過(guò)坐標(biāo)原點(diǎn)的軸旋轉(zhuǎn)，要給出這根軸的方向向量的坐標(biāo)(Ax,Ay,Az)。首先建立一個(gè)新的坐標(biāo)系ouvw，ow

軸的指向和旋轉(zhuǎn)軸(Ax,Ay,Az)的指向一致把要作旋轉(zhuǎn)變換的對(duì)象先從oxyz坐標(biāo)系變到坐標(biāo)系ouvw

在ouvw

坐標(biāo)系繞ow

軸旋轉(zhuǎn)要求轉(zhuǎn)動(dòng)的角度最后把旋轉(zhuǎn)后的對(duì)象從坐標(biāo)系ouvw

變換到原坐標(biāo)系oxyz中兩個(gè)坐標(biāo)系間的變換關(guān)系軸可取在經(jīng)過(guò)O點(diǎn)并和軸垂直的任一直線上。為了方便，，則軸的方向可取成向量（-Ay,Ax,0）的方向，否則可取的方向。軸方向的單位向量為：當(dāng)，軸方向的單位向量為

若，則取軸的單位方向向量為

，即圖5.7

新坐標(biāo)系ouvwyuvwxzo若坐標(biāo)系變換公式從坐標(biāo)系oxyz至坐標(biāo)系ouvw

的變換為（5.6）向量、、是互相正交的單位向量，可知矩陣A的逆矩陣就是A的轉(zhuǎn)置矩陣AT，即這樣，從坐標(biāo)系ouvw

至坐標(biāo)系oxyz

的變換公式為

（5.7）變換公式由式（5.5）、式（5.6）和式（5.7）可得變換公式為:

（5.8）在OpenGL中使用如下函數(shù)進(jìn)行旋轉(zhuǎn)變換：voidglRotate{fd}(TYPEangle,TYPEx,TYPEy,TYPEz);其中angle為指定的旋轉(zhuǎn)角度（以度數(shù)為單位），參數(shù)x、y、z指定一個(gè)從原點(diǎn)到（x,y,z）點(diǎn)的向量，該向量作為旋轉(zhuǎn)中心軸，旋轉(zhuǎn)的方向?yàn)槟鏁r(shí)針。

如果旋轉(zhuǎn)軸通過(guò)點(diǎn)（xp，yp，zp），而不通過(guò)坐標(biāo)原點(diǎn)，則可先作平移變換把對(duì)象沿x、y和z方向分別平移-xp

、-yp和-zp，然后按照式（5.8）作旋轉(zhuǎn)變換，最后再把圖形沿x、y和z方向分別平移xp

、yp和zp，這樣就可以得到圖形繞任意軸的旋轉(zhuǎn)變換。繞著不是原點(diǎn)的固定點(diǎn)旋轉(zhuǎn)4錯(cuò)切變換設(shè)矩形ABCD沿x軸（稱為方向軸）方向切變，oy軸稱為依賴軸。圖5.8錯(cuò)切切變的程度由參數(shù)s=tgα決定

s的幾何意義是對(duì)y=1的點(diǎn)在切變時(shí)沿x軸正向平移的距離。設(shè)點(diǎn)(x,y,z)經(jīng)切變后成為(x′,y′,z′)，則(5.9)如果依賴軸和方向軸改成其它的坐標(biāo)軸，式（5.9）中的矩陣要作相應(yīng)的變動(dòng)。

4錯(cuò)切變換

5.2.2齊次坐標(biāo)與變換的矩陣表示在實(shí)際繪圖時(shí)，常要對(duì)對(duì)象連續(xù)做幾次變換，例如作了平移后，作旋轉(zhuǎn)，再作放大等。這樣對(duì)每一點(diǎn)的坐標(biāo)要依次用式(5.2)，式(5.8)和式(5.4)作計(jì)算，這樣計(jì)算量較大。如果只有旋轉(zhuǎn)和放縮，則可把式(5.8)和式(5.4)合并成一個(gè)矩陣?？蓪懗扇缦滦问剑?5.10)如果再加上平移變換，變換矩陣就不容易合并了。(5.2)為使平移變換也能像變換(5.4)、(5.5)、(5.8)和(5.9)式那樣容易合并，可以采用齊次坐標(biāo)。式(5.2)的齊次坐標(biāo)表示式為：(5.11)式(5.5)的旋轉(zhuǎn)變換可寫成齊次坐標(biāo)形式齊次坐標(biāo)表示法就是用n+1維向量表示n維向量。例如，我們使用齊次坐標(biāo)（xh，yh，zh，h）來(lái)表示每個(gè)三維空間坐標(biāo)位置（x，y，z）。其中參數(shù)h可取為任意非零值，最簡(jiǎn)單的選擇是取h=1，因此每個(gè)三維位置都可用齊次坐標(biāo)（x，y，z，1）進(jìn)行表示。

5.2.3變換的模式兩種圖形的變換模式圖形模式： 矩陣合并時(shí)，先調(diào)用的矩陣放在右邊，后調(diào)用的矩陣放在左邊，也稱為固定坐標(biāo)系模式。 特點(diǎn)是每一次變換均可看成相對(duì)于原始坐標(biāo)系中執(zhí)行的。空間模式：也稱為活動(dòng)坐標(biāo)系模式，矩陣的合并方式和圖形模式相反。特點(diǎn)是在連續(xù)執(zhí)行幾次變換時(shí)，每一次變換均可看成是在上一次變換所形成的新坐標(biāo)系中進(jìn)行的。對(duì)不同的應(yīng)用常要求用不同的變換模式在很多繪圖的情況下用圖形模式，因?yàn)橛脩舯容^容易估計(jì)變換后的結(jié)果。在整體變換的基礎(chǔ)上再作一些較獨(dú)立的局部變換常用空間模式。數(shù)學(xué)角度看變換的順序

圖形模式---例子1.先把圖形繞z軸旋轉(zhuǎn)30°，然后再沿x軸平移距離72.先把圖形沿x軸平移距離7，然后再繞z軸旋轉(zhuǎn)30°a）xyoxyox′y′b）c）x″xyy″o圖5.9先旋轉(zhuǎn)后平移（b）（a）yxx″y″（c）o圖5.10先平移后旋轉(zhuǎn)光柵化橢圓的變換(1)

考慮4.2.3節(jié)圓弧的離散生成和4.2.4節(jié)的橢圓弧光柵化算法：

（5.13）其中如果對(duì)由式（5.13）生成的橢圓作旋轉(zhuǎn)β角或放大縮小變換，這時(shí)要分別用變換矩陣

如果這兩個(gè)變換都做，則變換矩陣應(yīng)是這兩個(gè)矩陣的乘積T，這時(shí)只要用TMT-1代替式（5.13）中的M，便可得到變換后的橢圓的上的頂點(diǎn)的坐標(biāo)。

光柵化橢圓的變換(2)圖5.11

橢圓的變換β

我們定義橢圓PQ坐標(biāo)原點(diǎn)為中心，橢圓P’Q’是橢圓PQ旋轉(zhuǎn)角，然后放大或縮小后得到的橢圓，設(shè)T為其變換矩陣。如圖5.11所示。則有：(5.14)(5.15)由(5.14)和(5.15)可推出：

(5.16)這時(shí)只要用TMT-1代替式（5.13）中的M，便可得到變換后的橢圓的頂點(diǎn)坐標(biāo)。要注意的是，式(5.16)中的需要先由式(5.15)計(jì)算得到。

空間模式例子

Rotate（30，0，0，1）;

Translate（7，0，0）;

draw_triangle（）;xyx′y′x″y″圖5.12變換模式的影響o圖5.12可看成先對(duì)坐標(biāo)系oxy作旋轉(zhuǎn)，同時(shí)得到相應(yīng)的坐標(biāo)系ox’y’，然后再相對(duì)于新坐標(biāo)系ox’y’作平移得到最后結(jié)果。經(jīng)變換后得到的三角形相對(duì)于原始坐標(biāo)系的位置與圖5.10（c）是一樣的，只是考慮變換的方式不同。

（b）（a）yxx″y″（c）o圖5.10先平移后旋轉(zhuǎn)OpenGL中的變換

在OpenGL中矩陣是狀態(tài)的一部分模型視圖(GL_MODELVIEW)；投影(GL_PROJECTION)glMatrixMode(GL_MODELVIEW);?glMatrixMode(GL_PROJECTION);從概念上說(shuō)，當(dāng)前變換矩陣(CTM)就是一個(gè)4x4階的齊次坐標(biāo)矩陣，它是狀態(tài)的一部分，被應(yīng)用到經(jīng)過(guò)流水線中的所有頂點(diǎn)CTM是在應(yīng)用程序中定義的，并被上載到變換單元中OpenGL中的變換

CTM可以被改變，改變的方法是上載一個(gè)新的CTM或者右乘一個(gè)矩陣上載單位陣：C←I上載任意矩陣：C←M上載一個(gè)平移矩陣：C←T上載一個(gè)旋轉(zhuǎn)矩陣：C←R上載一個(gè)放縮矩陣：C←S右乘任意矩陣：C←CM右乘一個(gè)平移矩陣：C←CT右乘一個(gè)旋轉(zhuǎn)矩陣：C←CR右乘一個(gè)放縮矩陣：C←CSOpenGL中的變換繞固定點(diǎn)的旋轉(zhuǎn)從單位陣開始：C←I把固定點(diǎn)移到原點(diǎn)：C←CT旋轉(zhuǎn)：C←CR把固定點(diǎn)移回到原處：C←CT-1結(jié)果：C=TRT-1其中每個(gè)運(yùn)算對(duì)應(yīng)于程序中的一個(gè)函數(shù)調(diào)用注意：在程序中最后指定的運(yùn)算是最先被執(zhí)行的運(yùn)算OpenGL中的變換例子固定點(diǎn)為(1.0,2.0,3.0),繞z軸旋轉(zhuǎn)30°glMatrixMode(GL_MODEL_VIEW);glLoadIdentity();//此命令不會(huì)把投影矩陣重設(shè)glTranslated(1.0,2.0,3.0);glRotated(30.0,0.0,0.0,1.0);glTranslated(-1.0,-2.0,-3.0);記住在程序中最后指定的矩陣是最先被執(zhí)行的操作變換的應(yīng)用組合圖形變換的應(yīng)用設(shè)計(jì)者可能需要從不同的角度查看同一個(gè)場(chǎng)景。變換的應(yīng)用計(jì)算機(jī)動(dòng)畫

5.3裁剪視見(jiàn)體：限定要繪制的圖形區(qū)域，一般是一個(gè)四棱臺(tái)或四棱柱。

在OpenGL中函數(shù)glFrustum（…）、gluPerspective（…）和glOrtho（…）可定義視見(jiàn)體。

圖2.1

視見(jiàn)體、窗口和視口V′X′Y′U′視口屏幕窗口投影平面視點(diǎn)XYZ近平面遠(yuǎn)平面窗口:

有時(shí)為了突出圖形的某一部分，可定義一個(gè)窗口。只顯示窗口內(nèi)的圖形。視口：在屏幕或繪圖紙上可定一個(gè)矩形，稱為視口，窗口內(nèi)的景物就在視口內(nèi)顯示。

5.3裁剪裁剪作用：選擇顯示的內(nèi)容--圖形在窗口內(nèi)的部分被顯示出來(lái)，窗口外的部分被裁剪掉圖形中每個(gè)圖形基本元素都要經(jīng)過(guò)裁剪，因此裁剪直接影響整個(gè)圖形系統(tǒng)的效率。裁剪窗口：矩形，凸多邊形，任意多邊形裁剪類型：二維裁剪、三維裁剪裁剪對(duì)象：直線段、多邊形、文字等裁剪方法:直線的裁剪方法:Sutherland-Cohen算法,Cyrus-Beck算法,梁友棟-Barsky算法多邊形的裁剪方法:Sutherland-Hodgman算法三維的裁剪方法:Sutherland-Cohen算法,梁友棟-Barsky算法

5.3.1Sutherland-Cohen算法第一步:1)決定完全在窗口內(nèi)的直線段，稱為完全可見(jiàn)的線段；2)或決定完全在窗口外的線段，稱為顯然完全不可見(jiàn)的線段。第二步:處理不能斷定完全可見(jiàn)或顯然完全不可見(jiàn)的線段。*是一個(gè)迭代的過(guò)程，每次拋棄一段顯然完全不可見(jiàn)的線段，對(duì)余下部分再作第一步的判斷，直到得出肯定結(jié)論。Sutherland–Cohen算法分成兩部分：算法的第一步用窗口的四條邊把整個(gè)平面分成九個(gè)區(qū)域，每一個(gè)區(qū)域采用四位編碼表示：在x=xL左側(cè)的區(qū)域,編碼的第四位是1；在x=xR右側(cè)的區(qū)域,編碼的第三位是1；在y=yB下側(cè)的區(qū)域,編碼的第二位是1；在y=yT上側(cè)的區(qū)域,編碼的第一位是1。對(duì)要被裁剪的線段的兩個(gè)端點(diǎn)，如果所在的區(qū)域的兩個(gè)編碼都是0000，則這條線段完全可見(jiàn)；如果兩個(gè)編碼的邏輯乘不為0000，則這條線段是完全不可見(jiàn)的。可用于確定頂點(diǎn)的位置算法的第二步對(duì)線段KL，從K點(diǎn)(1001)的編碼分析出K在x=xL的左側(cè)，KL必和x=xL有交點(diǎn)，求出其交點(diǎn)M，KM顯然是完全不可見(jiàn)的，因而只要對(duì)ML從第一步開始重復(fù)上述處理。由于ML還是不能用第一步下結(jié)論，又從M的編碼發(fā)現(xiàn)M在y=yT的上側(cè)，因而要求ML和y=yT的交點(diǎn)N。丟掉MN，對(duì)NL用第一步的方法可斷定NL為完全可見(jiàn)，至此裁剪結(jié)束。XR

程序代碼floatx1,xr,yt,yb;unsignedcharcode(floatx,floaty){unsignedcharc=0;if(x<xl)c=c|1;elseif(x>xr)c=c|2;if(y<yb)c=c|4;elseif(y>yt)c=c|8;returnc;}voidclip(floatx0,floaty0,floatx2,floaty2){unsignedcharc1,c2,c;floatx,y,wx,wy;c1=code(x0,y0);c2=code(x2,y2);while((!(c1==0))||(!(c2==0))){if((c1&c2))return;c=c1;if(c==0)c=c2;wx=x2-x0;wy=y2-y0;if((c&1)==1){y=y0+wy*(xl-x0)/wx;x=xl;}elseif((c&2)==2){y=y0+wy*(xr-x0)/wx;x=xr;}elseif((c&4)==4){x=x0+wx*(yb-y0)/wy;y=yb;}elseif((c&8)==8){x=x0+wx*(yt-y0)/wy;y=yt;}if(c==c1){x0=x;y0=y;c1=code(x0,y0);}else{x2=x;y2=y;c2=code(x2,y2);}}//While()glLine(int(x0),int(y0),int(x2),int(y2));}補(bǔ)充：中點(diǎn)分割算法設(shè)要裁剪的線段是P0P1。從P0出發(fā)找出離P0最近的可見(jiàn)點(diǎn)(A點(diǎn))，和從P1點(diǎn)出發(fā)找出離P1最近的可見(jiàn)點(diǎn)(B點(diǎn))。從P0出發(fā)找最近可見(jiàn)點(diǎn)：*先求P0P1的中點(diǎn)Pm，*若P0Pm不能定為顯然不可見(jiàn)，則取P0Pm代替P0P1，*否則取PmP1代替P0P1，*再對(duì)新的P0P1求中點(diǎn)Pm。重復(fù)上述過(guò)程，直到P1Pm長(zhǎng)度小于給定的小數(shù)ε為止。在顯示時(shí)ε可取成一個(gè)象素的寬度，對(duì)分辨率為2N×2N的顯示器來(lái)說(shuō)，上面講的二分的過(guò)程最多只要作N次。

5.3.2Cyrus-Beck算法和梁友棟-Barsky算法考慮如圖5.15所示一個(gè)凸多邊形區(qū)域R和一條線段P1P2，要求計(jì)算線段落在區(qū)域R中的部分。假定A是區(qū)域R邊界L上一點(diǎn)。N是區(qū)域邊界在A點(diǎn)的內(nèi)法向量。線段P1P2用參數(shù)方程表示：（0≤t≤1）

（5.17）

P2NRP1P(t)=(P2-P1)t+P1P(tu)P(tl)圖5.15凸多邊形裁剪區(qū)域A對(duì)于線段上任意一點(diǎn)，和多邊形邊界L的關(guān)系有三種可能性：，則在L內(nèi)側(cè)。，則在L外側(cè)。

（性質(zhì)1），則在L或其延長(zhǎng)線上。3）2)1)由性質(zhì)(1)知，在凸多邊形內(nèi)的充要條件是，對(duì)于凸多邊形邊界上任意一點(diǎn)A和該處內(nèi)法向量，都有。現(xiàn)假設(shè)多邊形有k條邊，在每條邊上取—

個(gè)點(diǎn)Ai和該點(diǎn)處的內(nèi)法向量（i=1,2,…,k），則可見(jiàn)線段的參數(shù)區(qū)間為下列不等式的解（i=1,2,…,k）（5.18）

把式（5.17）代入式（5.18），（5.19）可見(jiàn)線段的參數(shù)區(qū)間解的最小值ts和最大值te分別對(duì)應(yīng)于可見(jiàn)線段的端點(diǎn)。P2NRP1P(t)=(P2-P1)t+P1P(tu)P(tl)圖5.15凸多邊形裁剪區(qū)域A整理得:線段在區(qū)域外側(cè)

對(duì)應(yīng)于，可直接判斷線段在多邊形之外；線段在區(qū)域內(nèi)側(cè)

對(duì)應(yīng)于，可不予考慮，繼續(xù)處理其他邊。若對(duì)于某個(gè)i，有，這時(shí)，與對(duì)應(yīng)邊平行，如圖5.16所示。這時(shí)有兩種情況：線段在區(qū)域外側(cè)或內(nèi)側(cè)。圖5.16線段與裁剪邊平行的情況AiNiP1P1P2P2與邊平行的情況注意到的正負(fù)性，所以式（5.19）等價(jià)于（5.20）是線段與第i條邊（或延長(zhǎng)線）的交點(diǎn)參數(shù)。（5.19）

式（5.20）的解的最小值與最大值為若，則和是可見(jiàn)線段的端點(diǎn)參數(shù)，否則整條線段在區(qū)域外部?？梢?jiàn)區(qū)域的解上述算法稱為Cyrus-Beck算法。圖5.17解的幾何意義終點(diǎn)組起點(diǎn)組P2P1解的幾何意義起點(diǎn)組以為特征，表示在該處沿方向前進(jìn)將進(jìn)入多邊形內(nèi)側(cè)。終點(diǎn)組以為特征，表示在該處沿方向前進(jìn)進(jìn)入多邊形外側(cè)。把分為兩組：起點(diǎn)組和終點(diǎn)組。算法的程序double

ts,te;int

Cyrus_Beck(intk,doubleA[][2],doubleN[][2],doublex[2],doubley[2],double*ts,double*te){

inti,j;doublet,dn,nw,D[2],W[2];*ts=0;*te=1;for(i=0;i<k;i++) {

dn=N[i][0]*(x[1]-x[0])+N[i][1]*(y[1]-y[0]);

nw=N[i][0]*(x[0]-A[i][0])+N[i][1]*(y[0]-A[i][1]);

if(fabs(dn)<1.0e-6){if(nw<0)return0;}else{t=-nw/dn;

if(dn<0){if(t<*te) *te=t;}elseif(t>*ts) *ts=t;}if(*ts>*te) return0;}return1;}梁友棟-Barsky算法當(dāng)凸多邊形是矩形窗口，且矩形的邊平行于坐標(biāo)軸時(shí)，上述算法可簡(jiǎn)化為梁友棟-Barsky[LIANG84]算法。對(duì)于窗口的每條邊，表5.1列出了其內(nèi)法向量，該邊上一點(diǎn)，從指向線段起點(diǎn)P1的向量，以及線段與該邊（或延長(zhǎng)線）的交點(diǎn)參數(shù)。由于每個(gè)法向量只有一個(gè)非零分量，所以任意一個(gè)向量與法向量求內(nèi)積，相當(dāng)于給出該向量的相應(yīng)分量。表5.1梁友棟-Barsky算法所用的量邊內(nèi)法向量邊上一點(diǎn)AP1-A左邊x=XL(1，0)(XL，y)(x1-XL，y1-y)右邊x=XR(-1，0)(XR，y)(x1-XR，y1-y)下邊y=YB(0，1)(x，YB)(x1-x，y1-YB)上邊y=YT(0，-1)(x，YT)(x1-x，y1-YT)設(shè)?x=x2－x1，?y=y2－y1，令（5.21）上述終點(diǎn)組和起點(diǎn)組的特征分別表現(xiàn)為rk>0和rk<0，其中k對(duì)應(yīng)于相應(yīng)的裁剪邊界（k=L、R、B、T分別對(duì)應(yīng)于左、右、下、上邊界）。沿方向前進(jìn)，rk>0時(shí)，將進(jìn)入k邊界的外側(cè)；rk<0時(shí)，將進(jìn)入k邊界的內(nèi)側(cè)。梁友棟-Barsky算法起點(diǎn)組終點(diǎn)組梁友棟-Barsky算法的基本步驟初始化線段在邊界內(nèi)的端點(diǎn)參數(shù)為ts=0、te=1。計(jì)算出各個(gè)裁剪邊界的r、s值。當(dāng)r=0且s<0時(shí)，舍棄該線段；否則計(jì)算線段與邊界的交點(diǎn)參數(shù)t。當(dāng)r<0時(shí)，參數(shù)t用于更新ts；當(dāng)r>0時(shí)，參數(shù)t用于更新te。如果更新了ts或te后，使ts>te，則舍棄該線段。tstetste算法的程序doublets,te;double

xL,xR,yB,yT;boolvisible=false;voidLiang_Barsky(doublex[2],doubley[2],double*ts,double*te){doubledx,dy;visible=false;

dx=x[1]-x[0];dy=y[1]-y[0];*ts=0;*te=1;if(clipt(-dx,x[0]-xL,ts,te))if(clipt(dx,xR-x[0],ts,te))if(clipt(-dy,y[0]-yB,ts,te))if(clipt(dy,yT-y[0],ts,te)) visible=true;}bool

clipt(doubler,doubles,double*ts,double*te){doublet;if(r<0){ t=s/r; if(t>*te)returnfalse; elseif(t>*ts)*ts=t;}elseif(r>0){t=s/r;if(t<*ts)returnfalse;elseif(t<*te)*te=t;}elseif(s<0)returnfalse;returntrue;}

5.3.3多邊形裁剪---凸多邊形的二維裁剪

多邊形是由一組線段圍成的封閉區(qū)域，線段裁剪是多邊形裁剪的基礎(chǔ)。正確的剪裁結(jié)果應(yīng)是一個(gè)有邊界的區(qū)域，即裁剪后的結(jié)果仍是一個(gè)（或多個(gè)）多邊形，要求在裁剪過(guò)程中應(yīng)當(dāng)保留多邊形的區(qū)域性質(zhì)。（a）裁剪前（c）對(duì)多邊形區(qū)域做裁剪（b）僅對(duì)多邊形的線段做裁剪圖5.18多邊形裁剪凸多邊形的裁剪方法(1)將窗口看做是由四個(gè)半平面圍成的區(qū)域，依次用每個(gè)半平面同多邊形求交，經(jīng)四次求交后，就得到裁剪后的多邊形。由于多邊形是凸的，每次和半平面求交時(shí)，多邊形或者在半平面內(nèi)（保留），或者在半平面外（去除），或者與半平面的邊界（直線）有兩個(gè)交點(diǎn)。連接這兩個(gè)交點(diǎn)及多邊形在半平面內(nèi)的部分，就構(gòu)成了與該半平面的交，它仍是一個(gè)凸多邊形。ABCDE凸多邊形的裁剪方法(2)對(duì)凸多邊形的裁剪，可以看成是凸多邊形和矩形窗口的求交。凸多邊形和矩形的邊之間或者有交點(diǎn)，或者無(wú)交點(diǎn)。當(dāng)有交點(diǎn)時(shí)，會(huì)產(chǎn)生僅有的兩個(gè)交點(diǎn)，特殊情況下，如交點(diǎn)在多邊形或矩形頂點(diǎn)上，需特殊處理，有時(shí)看做交點(diǎn)，有時(shí)不作為交點(diǎn)（如圖中A、B兩點(diǎn)），但都可以歸結(jié)為兩個(gè)交點(diǎn)的情況。這兩個(gè)交點(diǎn)把凸多邊形和矩形都分成兩部分，選擇凸多邊形在矩形內(nèi)的邊界和矩形在凸多邊形內(nèi)的邊界，就形成了裁剪后的多邊形。ABCDE快速裁剪算法時(shí)間復(fù)雜度o(n)求交、并、差求交檢測(cè)（碰撞檢測(cè)）裁剪、消隱多邊形的裁剪-Sutherland-Hodgman算法圖5.19

Sutherland-Hodgman算法對(duì)多邊形裁剪的Sutherland–Hodgman

算法是一種十分簡(jiǎn)便的方法，只要對(duì)多邊形用窗口的四條邊依次裁剪四次(見(jiàn)圖5.19）便可得到裁剪后的多邊形。線段端點(diǎn)S、P與裁剪線的位置關(guān)系算法的輸入是以頂點(diǎn)序列表示的多邊形，輸出也是一個(gè)頂點(diǎn)序列，構(gòu)成一個(gè)或多個(gè)多邊形?？紤]以窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線，該線把平面分成兩部分：一部分包含窗口，稱為可見(jiàn)側(cè)；另一部分稱為不可見(jiàn)側(cè)。

圖5.20

S、P與裁剪線的四種位置關(guān)系（b）（c）（d）S可見(jiàn)側(cè)可見(jiàn)側(cè)可見(jiàn)側(cè)可見(jiàn)側(cè)SPSPSPP（a）每條線段端點(diǎn)S、P與裁剪線比較后可輸出0至2個(gè)頂點(diǎn)。S、P都在可見(jiàn)一側(cè)，則輸出P。S、P都在不可見(jiàn)一側(cè)，則輸出0個(gè)頂點(diǎn)。S在可見(jiàn)一側(cè)，P在不可見(jiàn)一側(cè)，則輸出SP與裁剪線的交點(diǎn)I。S在不可見(jiàn)一側(cè)，P在可見(jiàn)一側(cè)，則輸出SP與裁剪線的交點(diǎn)I和P。算法框圖上述算法僅用一條裁剪邊對(duì)多邊形裁剪，得到一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過(guò)程的輸入。對(duì)于每條裁剪邊，算法的框圖是一樣的，只是判斷點(diǎn)在裁剪邊哪一側(cè)以及求線段SP與裁剪邊的交點(diǎn)算法應(yīng)做相應(yīng)的改變。

圖5.21

Sutherland-Hodgman算法流程圖（1）主框圖開始第一個(gè)頂點(diǎn)→S,F頂點(diǎn)輸入完畢輸入頂點(diǎn)P處理線段SPP→SF→P處理線段SP結(jié)束NY（2）處理線段SP子過(guò)程SP與裁剪線相交求SP與裁剪線的交點(diǎn)I輸出IP位于可見(jiàn)側(cè)輸出PNNYY

5.3.4字符裁剪字符裁剪的策略有以下三種:串精度裁剪:字符串完全落入窗口之內(nèi)時(shí)才顯示，否則不顯示。字符精度裁剪:當(dāng)一個(gè)字符完全包含于窗口內(nèi)時(shí)，顯示該字符，否則不顯示?；跇?gòu)成字符最小元素的裁剪:這種策略最為精確，即使字符只有一部分在窗口內(nèi)，也要把這一部分顯示出來(lái)。

（a）（b）（c）（d）

圖5.23字符裁剪

5.4OpenGL中簡(jiǎn)單的變換實(shí)例本節(jié)將在2.2節(jié)的程序中增加一個(gè)畫正方形的函數(shù)，通過(guò)對(duì)矩形做平移、放縮和旋轉(zhuǎn)變換介紹OpenGL中的圖形變換功能。畫正方形的函數(shù)可定義如