第五章變換和裁剪

1、Computer Graphics第五章 變換和裁剪Computer Graphics 第五章 變換和裁剪v幾何變換 觀察角度和物體位置的改變可以通過在世界坐標(biāo)系中對物體進(jìn)行各種變換來實(shí)現(xiàn)，如平移、放縮、旋轉(zhuǎn)等。 v二維窗口的裁剪 選擇顯示的內(nèi)容-圖形在窗口內(nèi)的部分被顯示出來，窗口外的部分被裁剪掉 裁剪算法：Sutherland-Cohen算法、Cyrus-Beck算法、梁友棟-Barsky算法、 Sutherland-Hodgman算法等。Computer Graphics 5.1 變換的數(shù)學(xué)基礎(chǔ) 一點(diǎn)在坐標(biāo)系中的坐標(biāo)，就是該點(diǎn)在坐標(biāo)軸上的垂直投影。三維空間中兩點(diǎn) 和 之間的距離是：1111

2、( ,)p x y z2222(,)pxyz22212212121|()()()p pxxyyzz圖5.1二維點(diǎn)的坐標(biāo)p (x,y)xy2 矢量矢量 矢量是一個n元組，對應(yīng)于n維空間中的一個點(diǎn)?？梢源砦矬w在空間的位置，運(yùn)動狀態(tài)等。 矢量的運(yùn)算（以三維矢量為例）幾個基本概念：3 矩陣矩陣階矩陣A定義為 nm111212122212nnmmmnaaaaaaaaaA1 點(diǎn)點(diǎn)，可記為 或 m nAnmija)(矩陣的性質(zhì) Computer Graphics 5.2 幾何變換v 坐標(biāo)系 世界坐標(biāo)系（world coordinate）:一個圖形場景往往由多個對象組成，為了描述它們之間的空間關(guān)系，需要把它

3、們置于一個統(tǒng)一的坐標(biāo)系中，該坐標(biāo)系稱為世界坐標(biāo)系。 模型坐標(biāo)系（modeling coordinate）或局部坐標(biāo)系（local coordinate）：當(dāng)構(gòu)造單個對象的數(shù)字模型時，為了方便可以將其置于一個特定的坐標(biāo)系下，即模型坐標(biāo)系或局部坐標(biāo)系。 設(shè)備坐標(biāo)系（device coordinate）：圖形輸出時，則應(yīng)在輸出設(shè)備上建立一個坐標(biāo)系，這個坐標(biāo)系稱為設(shè)備坐標(biāo)系。設(shè)備坐標(biāo)系依據(jù)設(shè)備的種類有不同的形式，如二維的屏幕坐標(biāo)系，描述機(jī)械手運(yùn)動軌跡的三維坐標(biāo)系。 標(biāo)準(zhǔn)化設(shè)備坐標(biāo)系（normalized device coordinate）：有些圖形系統(tǒng)，對設(shè)備坐標(biāo)系進(jìn)行了規(guī)范化，將坐標(biāo)范圍限定在區(qū)間

4、x,y,z | 0 x1, 0y1, 0z1內(nèi)，稱為標(biāo)準(zhǔn)化設(shè)備坐標(biāo)系。Computer Graphics 5.2 幾何變換本節(jié)討論的變換適用于任何直角坐標(biāo)系。點(diǎn) 由點(diǎn)(x, y, z)在x, y和z軸方向分別移動距離x, y和z得到。兩點(diǎn)坐標(biāo)間的關(guān)系為：zyxzyxzyx100010001(5.2)1 1 平移平移變換變換 其矩陣形式為：在OpenGL中使用如下函數(shù)進(jìn)行平移變換：void glTranslatefd (TYPE x, TYPE y, TYPE z);其中fd表示x、y、z的數(shù)據(jù)類型為float型或double型（下同），x、y和z分別為沿坐標(biāo)軸x、y和z的平移量。 ( ,)x

5、y z(5.1)zzzyyyxxx世界坐標(biāo)系中的各種幾何變換可用本節(jié)討論的方法來實(shí)現(xiàn)。Computer Graphics2 2 放大和縮小變換放大和縮小變換 其中sx,sy和sz 分別為沿x, y和z軸方向放縮的比例。其矩陣形式是xyzxs xys yzs z zyxssszyxzyx000000在OpenGL中使用如下函數(shù)進(jìn)行放縮變換：void glScalefd (TYPE x, TYPE y, TYPE z);其中x、y、z分別為沿三個坐標(biāo)軸方向的放縮比例因子。 (5.4)設(shè)點(diǎn)(x, y, z)經(jīng)縮放變換后得點(diǎn) 。兩點(diǎn)坐標(biāo)間的關(guān)系為( ,)x y z(5.3)Computer Graph

6、ics2 2 放大和縮小變換放大和縮小變換放縮變換必定有一個不動點(diǎn)，為了定義放縮變換，可以指定其不動點(diǎn)，一個放縮方向，以及沿該方向的放縮因子。當(dāng)放縮因子大于1時，對象在指定方向上變長Computer Graphics 以圖形中心為中心的放縮變換v 為了使縮放變換后的圖形仍在原來位置附近，可另外定義一個相似中心點(diǎn)(xp,yp,zp)v 把整個圖形沿x, y和z方向平移 -xp,-yp和-zp,使相似中心移到坐標(biāo)原點(diǎn)v 對每一點(diǎn)按照式(5.4)作變換v 沿x, y和z方向平移xp, yp和zp,把經(jīng)過放縮的圖形移回原處v 這樣做的綜合效果是圖形以(xp, yp, zp)為中心作了放縮變換。ppzp

7、pyppxzzzszyyysyxxxsx)()()(以(xp,yp,zp)為中心的放縮變換 Computer Graphics 3 旋轉(zhuǎn)變換它繞z軸旋轉(zhuǎn)角后，可得點(diǎn)zzyxryyxrxcossin)sin(sincos)cos(zyxzyx1000cossin0sincos設(shè)給定點(diǎn)的坐標(biāo)為:該變換的矩陣形式為),sin,cos(),(zrrzyxP),(zyxPComputer Graphics3 旋轉(zhuǎn)變換Computer Graphics3 旋轉(zhuǎn)變換繞y軸的旋轉(zhuǎn)變換公式為:cos0sin010sin0cosxxyyzz 設(shè)給定點(diǎn)的坐標(biāo)為:( , , )( sin , , cos )P x y

8、 zry rComputer Graphics3 旋轉(zhuǎn)變換繞x軸的旋轉(zhuǎn)變換公式為:zyxzyxcossin0sincos0001設(shè)給定點(diǎn)的坐標(biāo)為:( , , )(xcossin )P x y zrr，ypComputer Graphics 繞過原點(diǎn)的軸的旋轉(zhuǎn)變換 圖5.7 新坐標(biāo)系ouvwyuvwxzovuwv 對繞空間任一通過坐標(biāo)原點(diǎn)的軸旋轉(zhuǎn)，要給出這根軸的方向向量的坐標(biāo)(Ax,Ay,Az)。v 首先建立一個新的坐標(biāo)系ouvw，ow 軸的指向和旋轉(zhuǎn)軸(Ax,Ay,Az)的指向一致v 把要作旋轉(zhuǎn)變換的對象先從oxyz坐標(biāo)系變到坐標(biāo)系ouvw v 在ouvw 坐標(biāo)系繞ow 軸旋轉(zhuǎn)要求轉(zhuǎn)動的角度v

9、 最后把旋轉(zhuǎn)后的對象從坐標(biāo)系ouvw 變換到原坐標(biāo)系oxyz中Computer Graphics 兩個坐標(biāo)系間的變換關(guān)系ou軸可取在經(jīng)過O點(diǎn)并和 軸垂直的任一直線上。為了方便，ow022yxAA，則 軸的方向可取成向量（-Ay,Ax,0）的方向，否則可取 的方向。 軸方向的單位向量為：ow當(dāng)022yxAA，軸方向的單位向量為 若022yxAA，則取軸的單位方向向量為 ，即ov)0 , 0 ,(zAou222313233(,)(,)xyzxyzA AAAAAaaaw22111213(,0)(,)yxxyAAAAaaa uou111213(1,0,0),aaauvwu133212331133133

10、112311132212223(,)(,)a aa aa aa aa aa aaaav圖5.7 新坐標(biāo)系ouvwyuvwxzovuw若Computer Graphics 坐標(biāo)系變換公式從坐標(biāo)系oxyz至坐標(biāo)系ouvw 的變換為（5.6）向量 、 、 是互相正交的單位向量，可知矩陣A A的逆矩陣就是A A的轉(zhuǎn)置矩陣A AT T，即3323133222123121111aaaaaaaaaTA AA A這樣，從坐標(biāo)系ouvw 至坐標(biāo)系oxyz 的變換公式為 （5.7）uvwwvuzyxTAzyxzyxaaaaaaaaawvuA333231232221131211Computer Graphics 變

11、換公式由式（5.5）、式（5.6）和式（5.7）可得變換公式為: （5.8）在OpenGL中使用如下函數(shù)進(jìn)行旋轉(zhuǎn)變換：void glRotatefd (TYPE angle, TYPE x, TYPE y, TYPE z);其中angle為指定的旋轉(zhuǎn)角度（以度數(shù)為單位），參數(shù)x、y、z指定一個從原點(diǎn)到（x, y, z）點(diǎn)的向量，該向量作為旋轉(zhuǎn)中心軸，旋轉(zhuǎn)的方向?yàn)槟鏁r針。 zyxzyxTAA1000cossin0sincos 如果旋轉(zhuǎn)軸通過點(diǎn)（xp，yp，zp），而不通過坐標(biāo)原點(diǎn)，則可先作平移變換把對象沿x、y和z方向分別平移-xp 、-yp和-zp，然后按照式（5.8）作旋轉(zhuǎn)變換，最后再把圖形

12、沿x、y和z方向分別平移xp 、yp和zp，這樣就可以得到圖形繞任意軸的旋轉(zhuǎn)變換。 Computer Graphics繞著不是原點(diǎn)的固定點(diǎn)旋轉(zhuǎn)Computer Graphics4 錯切變換設(shè)矩形ABCD沿x軸（稱為方向軸）方向切變，oy軸稱為依賴軸。圖5.8 錯切切變的程度由參數(shù)s=tg決定sytgoAAA s的幾何意義是對y=1的點(diǎn)在切變時沿x軸正向平移的距離。設(shè)點(diǎn)(x, y, z)經(jīng)切變后成為(x, y, z)，則zyxszyx10001001(5.9) 如果依賴軸和方向軸改成其它的坐標(biāo)軸，式（5.9）中的矩陣要作相應(yīng)的變動。 Computer Graphics4 錯切變換Computer

13、 Graphics 5.2.2 齊次坐標(biāo)與變換的矩陣表示在實(shí)際繪圖時，常要對對象連續(xù)做幾次變換，例如作了平移后，作旋轉(zhuǎn)，再作放大等。這樣對每一點(diǎn)的坐標(biāo)要依次用式(5.2)，式(5.8)和式(5.4)作計(jì)算，這樣計(jì)算量較大。如果只有旋轉(zhuǎn)和放縮，則可把式(5.8)和式(5.4)合并成一個矩陣?？蓪懗扇缦滦问剑?(5.10) zyxzyxssszyxTzyx11000cossin0sincos000000TAA如果再加上平移變換，變換矩陣就不容易合并了。zyxzyxzyx100010001(5.2)Computer Graphics為使平移變換也能像變換(5.4)、(5.5)、(5.8)和(5.9)

14、式那樣容易合并，可以采用齊次坐標(biāo)。式(5.2)的齊次坐標(biāo)表示式為：(5.11)110001000100011zyxzyxzyx式(5.5)的旋轉(zhuǎn)變換可寫成齊次坐標(biāo)形式11000010000cossin00sincos1zyxzyx齊次坐標(biāo)表示法齊次坐標(biāo)表示法就是用n+1維向量表示n維向量。例如，我們使用齊次坐標(biāo)（xh，yh，zh，h）來表示每個三維空間坐標(biāo)位置（x，y，z）。 其中參數(shù)h可取為任意非零值，最簡單的選擇是取h=1，因此每個三維位置都可用齊次坐標(biāo)（x，y，z，1）進(jìn)行表示。Computer Graphics 5.2.3 變換的模式v 兩種圖形的變換模式 圖形模式：矩陣合并時，先調(diào)用

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

16、x軸平移距離7，然后再繞z軸旋轉(zhuǎn)30a）xyoxyoxyb）c）xxyyo圖5.9 先旋轉(zhuǎn)后平移1100001000003cos03sin0003sin03cos10000100001070011zyxzyx11000010000107001100001000003cos03sin0003sin03coszyx11000010003sin7003cos03sin03cos7003sin03coszyx1100001000003cos03sin7003sin03coszyx（b）（a）yxxy（c）o圖5.10 先平移后旋轉(zhuǎn)Computer Graphics 光柵化橢圓的變換(1) 考慮4.2.

17、3節(jié)圓弧的離散生成和4.2.4節(jié)的橢圓弧光柵化算法： 11iiiixxyyM（5.13） 其中cossinsincosabba M 如果對由式（5.13）生成的橢圓作旋轉(zhuǎn)角或放大縮小變換，這時要分別用變換矩陣0cossin 0sincosxRSySS或TT 如果這兩個變換都做，則變換矩陣應(yīng)是這兩個矩陣的乘積T T，這時只要用 TMTTMT-1-1代替式（5.13）中的M M，便可得到變換后的橢圓的上的頂點(diǎn)的坐標(biāo)。 Computer Graphics 光柵化橢圓的變換(2)圖5.11 橢圓的變換) ,( iiyxQ),(11iiyxP),(iiyxQ),(11iiyxP 我們定義橢圓PQ PQ

18、坐標(biāo)原點(diǎn)為中心，橢圓P PQ Q是橢圓PQ PQ 旋轉(zhuǎn) 角，然后放大或縮小后得到的橢圓，設(shè)T T 為其變換矩陣。如圖5.11所示。則有：11iiiixxyyM(5.14) iiiixxyyT1111iiiixxyyT(5.15) 由(5.14) 和(5.15)可推出： 11111iiiiiiiixxxxyyyy TT MT M T(5.16) 這時只要用 TMTTMT-1-1代替式（5.13）中的M M，便可得到變換后的橢圓的頂點(diǎn)坐標(biāo)。要注意的是，式(5.16)中的 需要先由式(5.15)計(jì)算得到。 ),(iiyxComputer Graphics 空間模式v 例子 Rotate（30，0，0

19、，1）; Translate（7，0，0）; draw_triangle（）;xyxyxy圖5.12 變換模式的影響o圖5.12可看成先對坐標(biāo)系oxy作旋轉(zhuǎn)，同時得到相應(yīng)的坐標(biāo)系oxy，然后再相對于新坐標(biāo)系oxy作平移得到最后結(jié)果。經(jīng)變換后得到的三角形相對于原始坐標(biāo)系的位置與圖5.10（c）是一樣的，只是考慮變換的方式不同。 11000010000107001100001000003cos03sin0003sin03coszyx11000010003sin7003cos03sin03cos7003sin03coszyx（b）（a）yxxy（c）o圖5.10 先平移后旋轉(zhuǎn)Computer Gra

20、phicsOpenGLOpenGL中的變換 在OpenGL中矩陣是狀態(tài)的一部分 模型視圖(GL_MODELVIEW)；投影(GL_PROJECTION) glMatrixMode(GL_MODELVIEW); glMatrixMode(GL_PROJECTION); 從概念上說，當(dāng)前變換矩陣(CTM)就是一個4x4階的齊次坐標(biāo)矩陣，它是狀態(tài)的一部分，被應(yīng)用到經(jīng)過流水線中的所有頂點(diǎn)CTM是在應(yīng)用程序中定義的，并被上載到變換單元中Computer GraphicsOpenGLOpenGL中的變換 CTM可以被改變，改變的方法是上載一個新的CTM或者右乘一個矩陣 上載單位陣：C I 上載任意矩陣：C

21、 M 上載一個平移矩陣：C T 上載一個旋轉(zhuǎn)矩陣：C R 上載一個放縮矩陣：C S 右乘任意矩陣：C CM 右乘一個平移矩陣：C CT 右乘一個旋轉(zhuǎn)矩陣：C CR 右乘一個放縮矩陣：C CSComputer GraphicsOpenGLOpenGL中的變換 繞固定點(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 其中每個運(yùn)算對應(yīng)于程序中的一個函數(shù)調(diào)用 注意：在程序中最后指定的運(yùn)算是最先被執(zhí)行的運(yùn)算Computer GraphicsOpenGLOpenGL中的變換例子v固定點(diǎn)為(1.0, 2.0, 3.0),

22、繞z軸旋轉(zhuǎn)30glMatrixMode(GL_MODEL_VIEW);glLoadIdentity(); /此命令不會把投影矩陣重設(shè)glTranslated(1.0, 2.0, 3.0);glRotated(30.0,0.0,0.0,1.0);glTranslated(-1.0,-2.0,-3.0);v記住在程序中最后指定的矩陣是最先被執(zhí)行的操作Computer Graphics變換的應(yīng)用v組合圖形Computer Graphics變換的應(yīng)用設(shè)計(jì)者可能需要從不同的角度查看同一個場景。Computer Graphics變換的應(yīng)用v計(jì)算機(jī)動畫Computer Graphics 5.3 裁 剪v 視

23、見體視見體：限定要繪制的圖形區(qū)域，一般是一個四棱臺或四棱柱。在OpenGL中函數(shù)glFrustum（）、gluPerspective（）和glOrtho（）可定義視見體。 圖2.1 視見體、窗口和視口VXYU視口屏幕窗口投 影 平面視點(diǎn)XYZ近平面遠(yuǎn)平面v 窗口窗口: : 有時為了突出圖形的某一部分，可定義一個窗口。只顯示窗口內(nèi)的圖形。v 視口：視口：在屏幕或繪圖紙上可定一個矩形，稱為視口，窗口內(nèi)的景物就在視口內(nèi)顯示。Computer Graphics 5.3 裁 剪v 裁剪作用裁剪作用： 選擇顯示的內(nèi)容-圖形在窗口內(nèi)的部分被顯示出來，窗口外的部分被裁剪掉 圖形中每個圖形基本元素都要經(jīng)過裁剪，

24、因此裁剪直接影響整個圖形系統(tǒng)的效率。v 裁剪窗口裁剪窗口：矩形，凸多邊形，任意多邊形v 裁剪類型裁剪類型：二維裁剪、三維裁剪v 裁剪對象裁剪對象：直線段、多邊形、文字等v 裁剪方法裁剪方法: : 直線的裁剪方法: Sutherland-Cohen算法 , Cyrus-Beck算法,梁友棟-Barsky算法 多邊形的裁剪方法:Sutherland-Hodgman算法 三維的裁剪方法: Sutherland-Cohen算法 ,梁友棟-Barsky算法Computer Graphics 5.3.1 Sutherland-Cohen算法第一步第一步:1)決定完全在窗口內(nèi)的直線段，稱為完全可見的線段；2

25、) 或決定完全在窗口外的線段，稱為顯然完全不可見的線段。第二步第二步: :處理不能斷定完全可見或顯然完全不可見的線段。*是一個迭代的過程，每次拋棄一段顯然完全不可見的線段，對余下部分再作第一步的判斷，直到得出肯定結(jié)論。SutherlandCohen算法分成兩部分：Computer Graphics 算法的第一步用窗口的四條邊把整個平面分成九個區(qū)域，每一個區(qū)域采用四位編碼表示：在x=xL左側(cè)的區(qū)域,編碼的第四位是1；在x=xR右側(cè)的區(qū)域,編碼的第三位是1； 在y=yB下側(cè)的區(qū)域,編碼的第二位是1；在y=yT上側(cè)的區(qū)域,編碼的第一位是1 。對要被裁剪的線段的兩個端點(diǎn)，如果所在的區(qū)域的兩個編碼都是0

26、000，則這條線段完全可見；如果兩個編碼的邏輯乘不為0000，則這條線段是完全不可見的?？捎糜诖_定頂點(diǎn)的位置Computer Graphics 算法的第二步對線段KL，從K點(diǎn)(1001)的編碼分析出K在x=xL的左側(cè)，KL必和x=xL有交點(diǎn)，求出其交點(diǎn)M，KM顯然是完全不可見的，因而只要對ML從第一步開始重復(fù)上述處理。由于ML還是不能用第一步下結(jié)論，又從M的編碼發(fā)現(xiàn)M在y=yT的上側(cè)，因而要求ML和y=yT的交點(diǎn)N。丟掉MN，對NL用第一步的方法可斷定NL為完全可見，至此裁剪結(jié)束。XRComputer Graphics 程序代碼float x1, xr, yt, yb;unsigned cha

27、r code(float x, float y)unsigned char c = 0;if (x xr) c = c|2;if (y yt) c = c|8;return c;void clip(float x0, float y0, float x2, float y2)unsigned char c1, c2, c;float x, 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

28、-x0; wy=y2-y0;if (c & 1) = 1) y = y0 + wy * (xl - x0) /wx; x = xl;else if (c & 2) = 2) y = y0 +wy * (xr - x0) /wx; x = xr;else if (c & 4) = 4) x = x0 +wx * (yb - y0) /wy; y = yb;else if (c & 8) = 8) x = x0 +wx * (yt - y0) / wy; y = yt;if (c = c1) x0 = x; y0 = y;c1 = code(x0, y0);else

29、 x2 = x; y2 = y;c2 = code(x2, y2);/ While()glLine(int(x0), int(y0), int(x2), int(y2);Computer Graphics 補(bǔ)充：中點(diǎn)分割算法設(shè)要裁剪的線段是P0P1。從P0出發(fā)找出離P0最近的可見點(diǎn)(A點(diǎn))，和從P1點(diǎn)出發(fā)找出離P1最近的可見點(diǎn)(B點(diǎn))。從P0出發(fā)找最近可見點(diǎn)：*先求P0P1的中點(diǎn)Pm，*若P0Pm不能定為顯然不可見，則取P0Pm代替P0P1，*否則取PmP1代替P0P1，*再對新的P0P1求中點(diǎn)Pm。重復(fù)上述過程，直到P1Pm長度小于給定的小數(shù)為止。在顯示時可取成一個象素的寬度，對分辨率為2N

30、2N的顯示器來說，上面講的二分的過程最多只要作N次。Computer Graphics 5.3.2 Cyrus-Beck算法和梁友棟-Barsky算法 考慮如圖5.15所示一個凸多邊形區(qū)域R和一條線段P1P2，要求計(jì)算線段落在區(qū)域R中的部分。假定A是區(qū)域R邊界L上一點(diǎn)。N是區(qū)域邊界在A點(diǎn)的內(nèi)法向量。線段P1P2用參數(shù)方程表示：112)()(PtPPtP（0t1） （5.17） P2NRP1P(t)=(P2-P1)t+P1P(tu)P(tl)圖5.15 凸多邊形裁剪區(qū)域A 對于線段上任意一點(diǎn) ， 和多邊形邊界L的關(guān)系有三種可能性：)(tP0)(AtPN0)(AtPN，則 在L內(nèi)側(cè)。，則 在L外側(cè)

31、。 （性質(zhì)1）0)(AtPN，則 在L或其延長線上。)(tP)(tP)(tP3）2)1)(tPComputer Graphics 由性質(zhì)(1)知， 在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點(diǎn)A和該處內(nèi)法向量 ，都有 。 現(xiàn)假設(shè)多邊形有k條邊，在每 條邊 上 取 個 點(diǎn) Ai 和 該 點(diǎn) 處 的 內(nèi) 法向量（i=1,2,k），則可見線段的參數(shù)區(qū)間為下列不等式的解)(tPN0)(AtPN（i=1,2,k） （5.18） 把式 （5.17）代入式（5.18），（5.19） ( ( )0, 01iiP tAt N10 , 0)()(121ttPPNAPiiiN112)()(PtPPtP 可見

32、線段的參數(shù)區(qū)間解的最小值ts和最大值te分別對應(yīng)于可見線段的端點(diǎn)。P2NRP1P(t)=(P2-P1)t+P1P(tu)P(tl)圖5.15 凸多邊形裁剪區(qū)域A整理得:Computer Graphicsv 線段在區(qū)域外側(cè) 對應(yīng)于 ，可直接判斷線段在多邊形之外；v 線段在區(qū)域內(nèi)側(cè) 對應(yīng)于 ，可不予考慮，繼續(xù)處理其他邊。 若對于某個i，有 ，這時 ， 與對應(yīng)邊平行，如圖5.16所示。這時有兩種情況：線段在區(qū)域外側(cè)或內(nèi)側(cè)。0)(12PPiN)(12PPiN21PP0)(1iiAPN1()0iiPAN圖5.16 線段與裁剪邊平行的情況AiNiP1P1P2P2 與邊平行的情況Computer Graph

33、ics注意到 的正負(fù)性，所以式（5.19）等價于)(12PPiN（5.20） )()(121PPAPtiiiiNN是線段與第i條邊（或延長線）的交點(diǎn)參數(shù)。10 , 0)()(121ttPPNAPiiiN（5.19） 式（5.20）的解的最小值與最大值為若 ，則 和 是可見線段的端點(diǎn)參數(shù)，否則整條線段在區(qū)域外部。2121max0, max|()0min1, min|()0siieiittPPttPPNNestt stet2121 ()0()0iit-tPPt-tPP 當(dāng)，當(dāng)ii,NN 可見區(qū)域的解Computer Graphics21()0iPPN21PP上述算法稱為Cyrus-Beck算法。2

34、1()0iPPN21PP圖5.17 解的幾何意義終點(diǎn)組起點(diǎn)組P2P1 解的幾何意義v 起點(diǎn)組以 為特征，表示在該處沿 方向前進(jìn)將進(jìn)入多邊形內(nèi)側(cè)。v 終點(diǎn)組以 為特征，表示在該處沿 方向前進(jìn)進(jìn)入多邊形外側(cè)。把 分為兩組：起點(diǎn)組和終點(diǎn)組。)(12PPiNitComputer Graphics 算法的程序double ts,te;int Cyrus_Beck (int k,double A2,double N2,double x2,double y2,double *ts,double *te) int i,j; double t,dn,nw,D2,W2; *ts=0;*te=1; for(i=0;

35、ik;i+) dn=Ni0*(x1- x0) +Ni1* (y1-y0);nw=Ni0* (x0-Ai0) +Ni1* (y0- Ai1);if(fabs(dn)1.0e-6) if(nw0) return 0; else t=-nw/dn; if(dn0) if(t *ts) *ts=t; if(*ts*te) return 0; return 1;10 , 0)()(121ttPPNAPiiiNComputer Graphics梁友棟-Barsky算法 當(dāng)凸多邊形是矩形窗口，且矩形的邊平行于坐標(biāo)軸時，上述算法可簡化為梁友棟-BarskyLIANG84算法。 對于窗口的每條邊，表5.1列出了

36、其內(nèi)法向量 ，該邊上一點(diǎn) ，從 指向線段起點(diǎn)P1 的向量 ，以及線段與該邊（或延長線）的交點(diǎn)參數(shù)。iNiAiAiAP 1)()(121PPAPtiiiiNN2121 ()0()0iit-tPPt-tPP 當(dāng)，當(dāng)ii,NN 由于每個法向量只有一個非零分量，所以任意一個向量與法向量求內(nèi)積，相當(dāng)于給出該向量的相應(yīng)分量。表表5.1 梁友棟梁友棟-Barsky算法所用的量算法所用的量)()(121PPAPtNN)()(121xxXLx121)(xxXRx)()(121yyYBy121)(yyYTy邊內(nèi)法向量邊上一點(diǎn)AP1-A左邊x=XL(1，0)(XL，y)(x1-XL， y1-y)右邊x=XR(-1，

37、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)Computer Graphics設(shè)x=x2x1，y=y2y1，令（5.21） 上述終點(diǎn)組和起點(diǎn)組的特征分別表現(xiàn)為rk0和rk0時，將進(jìn)入k邊界的外側(cè)；rk0時，將進(jìn)入k邊界的內(nèi)側(cè)。21PP,yryrxrxrTBRL,1111yysyysxxsxxsTTBBRRLL 梁友棟-Barsky算法起點(diǎn)組終點(diǎn)組Computer Graphics 梁友棟梁友棟-Barsky-Barsky算法的基本步驟算法的基本步驟v 初始化線段在邊界內(nèi)的端點(diǎn)參數(shù)為

38、ts=0、te=1。v 計(jì)算出各個裁剪邊界的r、s值。v 當(dāng)r=0且s0時，舍棄該線段；否則計(jì)算線段與邊界的交點(diǎn)參數(shù)t。 當(dāng)r0時，參數(shù)t用于更新te。v 如果更新了ts或te后，使tste，則舍棄該線段。tstetsteComputer Graphics 算法的程序double ts,te;double xL,xR,yB,yT;bool visible=false;void Liang_Barsky (double x2,double y2,double *ts,double *te) double dx,dy; visible=false; dx=x1-x0; dy= y1-y0; *ts

39、=0; *te=1; if(clipt(-dx,x0-xL,ts,te) if(clipt(dx,xR-x0,ts,te) if(clipt(-dy,y0-yB,ts,te) if(clipt(dy,yT-y0,ts,te) visible=true; bool clipt (double r,double s,double * ts,double *te) double t; if(r* te) return false;else if(t* ts) *ts=t; else if(r0) t=s/r; if(t*ts) return false; else if(t* te) *te=t;

40、else if(s0) return false; return true; Computer Graphics 5.3.3 多邊形裁剪-凸多邊形的二維裁剪 多邊形是由一組線段圍成的封閉區(qū)域，線段裁剪是多邊形裁剪的基礎(chǔ)。正確的剪裁結(jié)果應(yīng)是一個有邊界的區(qū)域，即裁剪后的結(jié)果仍是一個（或多個）多邊形，要求在裁剪過程中應(yīng)當(dāng)保留多邊形的區(qū)域性質(zhì)。（a） 裁剪前（c） 對多邊形區(qū)域做裁剪（b） 僅對多邊形的線段做裁剪圖5.18 多邊形裁剪Computer Graphics凸多邊形的裁剪方法(1)v 將窗口看做是由四個半平面圍成的區(qū)域，依次用每個半平面同多邊形求交，經(jīng)四次求交后，就得到裁剪后的多邊形。由于多

41、邊形是凸的，每次和半平面求交時， 多邊形或者在半平面內(nèi)（保留）， 或者在半平面外（去除）， 或者與半平面的邊界（直線）有兩個交點(diǎn)。 連接這兩個交點(diǎn)及多邊形在半平面內(nèi)的部分，就構(gòu)成了與該半平面的交，它仍是一個凸多邊形。ABCDEComputer Graphics凸多邊形的裁剪方法(2)v 對凸多邊形的裁剪，可以看成是凸多邊形和矩形窗口的求交。凸多邊形和矩形的邊之間或者有交點(diǎn)，或者無交點(diǎn)。v 當(dāng)有交點(diǎn)時，會產(chǎn)生僅有的兩個交點(diǎn)，特殊情況下，如交點(diǎn)在多邊形或矩形頂點(diǎn)上，需特殊處理，有時看做交點(diǎn)，有時不作為交點(diǎn)（如圖中A、B兩點(diǎn)），但都可以歸結(jié)為兩個交點(diǎn)的情況。這兩個交點(diǎn)把凸多邊形和矩形都分成兩部分，選

42、擇凸多邊形在矩形內(nèi)的邊界和矩形在凸多邊形內(nèi)的邊界，就形成了裁剪后的多邊形。ABCDEComputer Graphics快速裁剪算法時間復(fù)雜度時間復(fù)雜度o(n)o(n)求交、并、差求交、并、差求交檢測求交檢測（碰撞檢測）（碰撞檢測）裁剪、消隱裁剪、消隱Computer Graphics多邊形的裁剪-Sutherland-Hodgman算法圖5.19Sutherland-Hodgman算法對多邊形裁剪的SutherlandHodgman 算法是一種十分簡便的方法，只要對多邊形用窗口的四條邊依次裁剪四次(見圖5.19）便可得到裁剪后的多邊形。Computer Graphics 線段端點(diǎn)S、P與裁剪線

43、的位置關(guān)系 算法的輸入是以頂點(diǎn)序列表示的多邊形，輸出也是一個頂點(diǎn)序列，構(gòu)成一個或多個多邊形。 考慮以窗口的一條邊以及延長線構(gòu)成的裁剪線，該線把平面分成兩部分：一部分包含窗口，稱為可見側(cè)；另一部分稱為不可見側(cè)。 圖5.20 S、P與裁剪線的四種位置關(guān)系（b）（c）（d）S可見側(cè)可見側(cè)可見側(cè)可見側(cè)SPSPSPP（a）v 每條線段端點(diǎn)S、P與裁剪線比較后可輸出0至2個頂點(diǎn)。 S、P都在可見一側(cè)，則輸出P。 S、P都在不可見一側(cè)，則輸出0個頂點(diǎn)。 S在可見一側(cè)，P在不可見一側(cè)，則輸出SP與裁剪線的交點(diǎn)I。 S在不可見一側(cè)，P在可見一側(cè)，則輸出SP與裁剪線的交點(diǎn)I和P。Computer Graphics

44、算法框圖上述算法僅用一條裁剪邊對多邊形裁剪，得到一個頂點(diǎn)序列，作為下一條裁剪邊處理過程的輸入。對于每條裁剪邊，算法的框圖是一樣的，只是判斷點(diǎn)在裁剪邊哪一側(cè)以及求線段SP與裁剪邊的交點(diǎn)算法應(yīng)做相應(yīng)的改變。 圖5.21 Sutherland-Hodgman算法流程圖（1）主框圖開始第一個頂點(diǎn)S,F頂點(diǎn)輸入完畢輸入頂點(diǎn)P處理線段SPPSFP處理線段SP結(jié)束NY（2）處理線段SP子過程SP與裁剪線相交求SP與裁剪線的交點(diǎn)I輸出IP位于可見側(cè)輸出PNNYYComputer Graphics 5.3.4 字符裁剪v 字符裁剪的策略有以下三種: 串精度裁剪:字符串完全落入窗口之內(nèi)時才顯示，否則不顯示。 字符

45、精度裁剪:當(dāng)一個字符完全包含于窗口內(nèi)時，顯示該字符，否則不顯示。 基于構(gòu)成字符最小元素的裁剪:這種策略最為精確，即使字符只有一部分在窗口內(nèi)，也要把這一部分顯示出來。 （a） （b） （c） （d） 圖5.23 字符裁剪Computer Graphics 5.4 OpenGL中簡單的變換實(shí)例 本節(jié)將在2.2節(jié)的程序中增加一個畫正方形的函數(shù)，通過對矩形做平移、放縮和旋轉(zhuǎn)變換介紹OpenGL中的圖形變換功能。畫正方形的函數(shù)可定義如下:void CExam1View:gl_Rect()int x1, y1, x2, y2;/ 設(shè)置繪圖顏色為黑色glColor3f(0,0,0);x1 = 100; y1 = 100; x2 = 200; y2 = 200;glLine(x1, y1, x2, y1); glLine(x2, y1, x2, y2); glLine(x2, y2, x1, y2);glLine(x1, y2, x1, y1);void CExam1View:glLine(int x1, int x1, int x2, int y2)glBegin(GL