《計(jì)算機(jī)圖形學(xué)基礎(chǔ)》課件第3章

第3章圖形變換3.1坐標(biāo)系統(tǒng)

3.2幾何變換

3.3投影變換

3.4圖形裁剪

3.5窗口概念及窗口到視區(qū)的變換

習(xí)題3 3.1坐標(biāo)系統(tǒng)

計(jì)算機(jī)只能對(duì)二進(jìn)制數(shù)據(jù)進(jìn)行處理，圖形在計(jì)算機(jī)內(nèi)也是以二進(jìn)制數(shù)據(jù)的方式保存和處理的。因此，計(jì)算機(jī)在處理圖形信息時(shí)，幾何圖形的定義和圖形的輸入、輸出都是在一定的坐標(biāo)系下進(jìn)行的。圖形在輸入、輸出的不同階段需要采用不同的坐標(biāo)系，以方便設(shè)計(jì)人員的理解和操作，提高圖形處理效率。為了方便描述各種物體，在圖形系統(tǒng)中，采用了很多各具特色的坐標(biāo)系統(tǒng)，主要包括世界坐標(biāo)系、造型坐標(biāo)系、觀察坐標(biāo)系、虛擬設(shè)備坐標(biāo)系、設(shè)備坐標(biāo)系等。上述坐標(biāo)系分別屬于二維和三維坐標(biāo)系統(tǒng)。在三維空間中定義幾何形體時(shí)可采用三種坐標(biāo)系：世界坐標(biāo)系、造型坐標(biāo)系和觀察坐標(biāo)系。虛擬設(shè)備坐標(biāo)系和設(shè)備坐標(biāo)系提供了在二維顯示屏幕上定義幾何圖形的坐標(biāo)系。

世界坐標(biāo)系用來(lái)使被顯示的對(duì)象數(shù)量化，是在被顯示對(duì)象所在的空間定義的一個(gè)坐標(biāo)系。這個(gè)坐標(biāo)系的長(zhǎng)度單位和坐標(biāo)軸的方向要適合對(duì)被顯示對(duì)象的描述。為了使被顯示的對(duì)象能以合適的位置、大小和方向顯示出來(lái)，需要將該對(duì)象在世界坐標(biāo)系中進(jìn)行平移、縮放和旋轉(zhuǎn)等。這個(gè)坐標(biāo)系主要用于計(jì)算機(jī)圖形場(chǎng)景中的所有圖形對(duì)象的空間定位和定義，包括觀察者的位置、視線等。其他坐標(biāo)系統(tǒng)都是參照它進(jìn)行定義的。造型坐標(biāo)系用于描述世界坐標(biāo)系中每個(gè)具體物體的形狀，每個(gè)物體均由其自身的造型坐標(biāo)系定義。當(dāng)物體的空間位置發(fā)生變化時(shí)，由造型坐標(biāo)系定義的物體上各點(diǎn)的坐標(biāo)值不變。造型坐標(biāo)系與世界坐標(biāo)系是局部與整體的關(guān)系。在許多CAD系統(tǒng)中，用造型坐標(biāo)系定義基本圖形元素，如圓柱體、球體等。這些基本圖形元素被調(diào)用后，應(yīng)用相關(guān)的變換矩陣將其置于世界坐標(biāo)系的指定位置。因此，造型坐標(biāo)系又稱為局部坐標(biāo)系，而世界坐標(biāo)系又稱為整體坐標(biāo)系。如同將現(xiàn)實(shí)世界的景物投影到人的視網(wǎng)膜上一樣，為了將三維物體投影到顯示屏幕(或觀察平面)上，需要建立觀察坐標(biāo)系(ViewCoordinateSystem，VCS)。在計(jì)算機(jī)圖形處理

中，通常采用透視投影和平行投影兩種方式建立VCS。觀察坐標(biāo)系通常是以視點(diǎn)的位置為原點(diǎn)，通過用戶指定的一個(gè)向上的觀察向量(viewupvector)來(lái)定義整個(gè)坐標(biāo)系的，默認(rèn)為左手坐標(biāo)系。

不同的坐標(biāo)系之間通過變換矩陣建立聯(lián)系。每個(gè)造型坐標(biāo)系的位置和方位可通過變換矩陣由世界坐標(biāo)系確定。同樣，觀察坐標(biāo)系也可通過世界坐標(biāo)系定義的一系列數(shù)據(jù)，由與世界坐標(biāo)系相關(guān)的變換矩陣確定。世界坐標(biāo)系、造型坐標(biāo)系和觀察坐標(biāo)系之間的關(guān)系如圖3-1所示。圖3-1世界坐標(biāo)系、造型坐標(biāo)系和觀察坐標(biāo)系之間的關(guān)系為了避免由于設(shè)備坐標(biāo)系與設(shè)備的相關(guān)性影響應(yīng)用程序的可移植性，在編寫圖形程序時(shí)，應(yīng)采用虛擬設(shè)備坐標(biāo)系(VirtualDeviceCoordinateSystem，VDCS)。虛擬設(shè)備坐標(biāo)系的原點(diǎn)通常位于顯示器的左下角，其軸的正方向分別指向右方和上方，且取值范圍均為0～1。因此，用虛擬設(shè)備坐標(biāo)系定義的點(diǎn)，在不同的圖形設(shè)備上占據(jù)相同的位置而與設(shè)備無(wú)關(guān)，編寫圖形程序時(shí)也不必考慮某個(gè)特定的設(shè)備坐標(biāo)系。當(dāng)圖形程序在某臺(tái)圖形設(shè)備上運(yùn)行時(shí)，圖形程序?qū)⑻摂M設(shè)備坐標(biāo)系發(fā)送給設(shè)備驅(qū)動(dòng)程序，由該程序?qū)⑻摂M設(shè)備坐標(biāo)系轉(zhuǎn)換成與該設(shè)備一致的設(shè)備坐標(biāo)系。虛擬設(shè)備坐標(biāo)系也稱為規(guī)格化的設(shè)備坐標(biāo)系，主要用于定義視圖區(qū)。設(shè)備坐標(biāo)系用于在圖形顯示設(shè)備上定義圖形或窗口的位置。設(shè)備坐標(biāo)系通常由沿水平方向的x軸和沿垂直方向的y軸組成，其坐標(biāo)原點(diǎn)可以任意選擇。由于圖形顯示是將真實(shí)圖形投影于顯示屏幕上，故設(shè)備坐標(biāo)系的z軸垂直于坐標(biāo)系的xoy平面，但通常不予定義。設(shè)備坐標(biāo)系也是定義像素和位圖的坐標(biāo)系。對(duì)于相同的圖形信息，當(dāng)采用設(shè)備坐標(biāo)系編寫

圖形程序時(shí)，由于坐標(biāo)系的原點(diǎn)位置和坐標(biāo)軸方向以及圖形窗口的顯示范圍不同，在不同顯示設(shè)備上顯示出的圖形是不同的，如圖3-2所示。圖3-2設(shè)備坐標(biāo)系要在三維空間創(chuàng)建和顯示一個(gè)(多個(gè))幾何物體，首先必須建立世界坐標(biāo)系，然后需要指定視點(diǎn)的方位、視線和成像面的方位。為了觀察到物體的成像，還必須在各坐標(biāo)系之間進(jìn)行坐標(biāo)變換，然后利用投影變換才能得到物體的成像。坐標(biāo)系間的坐標(biāo)變換過程如圖3-3所示。圖3-3坐標(biāo)系間的坐標(biāo)變換過程

3.2幾何變換

在計(jì)算機(jī)圖形處理中，經(jīng)常需要對(duì)已生成的圖形進(jìn)行旋轉(zhuǎn)、平移、放大或縮小等幾何變換操作，以生成新的圖形信息。由于點(diǎn)是構(gòu)成幾何形體的最基本元素，因此，通過對(duì)構(gòu)成幾何圖形的特征點(diǎn)集進(jìn)行幾何變換，即可實(shí)現(xiàn)整個(gè)圖形的幾何變換。圖形變換后產(chǎn)生了如下結(jié)果：圖形變化了，但原圖形的構(gòu)成規(guī)則(拓?fù)潢P(guān)系)并沒有改變；圖形發(fā)生的變化是由其頂點(diǎn)位置(幾何關(guān)系)的改變決定的。這種通過維持圖形的拓?fù)潢P(guān)系不變，而僅改變圖形的幾何關(guān)系來(lái)實(shí)現(xiàn)改變圖形的方法，稱為圖形的幾何變換。幾何變換用于研究物體坐標(biāo)在直角坐標(biāo)系統(tǒng)內(nèi)的平移、旋轉(zhuǎn)和縮放變化的規(guī)律。按照坐標(biāo)的維數(shù)不同，幾何變換可分為二維幾何變換和三維幾何變換兩大類。3.2.1平移變換

1.二維圖形的平移變換

平移(translation)是指將P點(diǎn)沿直線路徑從一個(gè)坐標(biāo)位置移到另一個(gè)坐標(biāo)位置的重定位過程。假設(shè)(x，y)是變換前的點(diǎn)，(x′，y′)是變換后的點(diǎn)。圖3-4表示了二維圖形的平移過程。

Tx＝x′－x，Ty＝y(tǒng)′－y稱為平移距離,則平移變換的公式為

x′=x+Tx

y′=y+Ty二維平移的矩陣運(yùn)算表示為圖3-4平移變換

2.三維圖形的平移變換

與二維平移變換非常類似，三維平移變換將變換前的點(diǎn)P(x，y，z)變換到變換后的點(diǎn)P′(x′，y′，z′)，則三維平移變換的公式為

x′=x+Tx

y′=y+Ty

z′=z+Tz

三維平移的矩陣運(yùn)算表示為3.2.2縮放變換

縮放(scaling)變換是指對(duì)P點(diǎn)相對(duì)于坐標(biāo)原點(diǎn)沿x方向縮放sx倍，沿y方向縮放sy倍。其中sx和sy稱為縮放系數(shù)。因此，縮放變換是使對(duì)象按比例因子(sx，sy)放大或縮小的變換，如圖3-5所示。

縮放變換的計(jì)算公式為

x′=x·sx

y′=y·sy

縮放變換可以改變物體的大小，如圖3-6所示。圖3-5

sx=2，sy=3的縮放變換圖3-6等比例變換及非等比例變換當(dāng)sx=sy>1時(shí)，圖形沿兩個(gè)坐標(biāo)軸方向等比例放大；當(dāng)sx=sy<1時(shí)，圖形沿兩個(gè)坐標(biāo)軸方向等比例縮?。划?dāng)sx≠sy時(shí)，圖形沿兩個(gè)坐標(biāo)軸方向作非均勻的縮放變換，這時(shí)圖形會(huì)產(chǎn)生一定的變形。

二維縮放的矩陣運(yùn)算表示為

三維縮放的矩陣運(yùn)算表示為3.2.3旋轉(zhuǎn)變換

1.二維旋轉(zhuǎn)變換

旋轉(zhuǎn)(rotation)是以某個(gè)參考點(diǎn)為圓心，將對(duì)象上的點(diǎn)P(x，y)圍繞圓心轉(zhuǎn)動(dòng)一個(gè)逆時(shí)針角度θ(逆時(shí)針為正，順時(shí)針為負(fù))，變?yōu)樾碌淖鴺?biāo)P′(x′，y′)的變換，如圖3-7所示。當(dāng)參考點(diǎn)為(0，0)時(shí)，旋轉(zhuǎn)變換的公式為

因?yàn)?/p>

x=rcosa，y=rsina所以旋轉(zhuǎn)變換公式可轉(zhuǎn)化為

二維旋轉(zhuǎn)變換的矩陣運(yùn)算表示為圖3-7旋轉(zhuǎn)變換

2.三維旋轉(zhuǎn)變換

首先考慮圍繞坐標(biāo)軸旋轉(zhuǎn)，即分別取x、y、z為旋轉(zhuǎn)軸，圍繞某個(gè)坐標(biāo)軸旋轉(zhuǎn)可以看做是在另外兩個(gè)坐標(biāo)軸組成的二維平面上進(jìn)行的二維旋轉(zhuǎn)變換。遵循右手法則，即若θ>0，大拇指指向軸的方向，其他手指指的方向?yàn)樾D(zhuǎn)方向。

1)繞z軸旋轉(zhuǎn)

繞z軸旋轉(zhuǎn)時(shí)，顯然z坐標(biāo)不變，x、y坐標(biāo)相應(yīng)變化，如圖3-8所示。

繞z軸旋轉(zhuǎn)的矩陣運(yùn)算表示為圖3-8繞z軸旋轉(zhuǎn)

2)繞x、y軸旋轉(zhuǎn)

與繞z軸旋轉(zhuǎn)類似，繞x軸旋轉(zhuǎn)的矩陣運(yùn)算表示為

繞y軸旋轉(zhuǎn)的矩陣運(yùn)算表示為3.2.4錯(cuò)切變換

錯(cuò)切變換也稱為錯(cuò)位變換，用于產(chǎn)生彈性物體的變形處理，如圖3-9所示。圖3-9錯(cuò)切變換二維錯(cuò)切的矩陣運(yùn)算表示(其中b表示x方向的錯(cuò)切量，d表示y方向的錯(cuò)切量)為

(1)當(dāng)d=0時(shí)，(x′，y′)=(x+by，y)，圖形的y坐標(biāo)不變，如圖3-10所示。

當(dāng)b>0時(shí)，圖形沿+x方向作錯(cuò)切位移，ABCD→A1B1C1D1。

當(dāng)b<0時(shí)，圖形沿－x方向作錯(cuò)切位移，ABCD→A2B2C2D2。圖3-10沿x方向錯(cuò)切變換

(2)當(dāng)b=0時(shí)，(x′，y′)=(x，dx+y)，圖形的x坐標(biāo)不變，如圖3-11所示。

當(dāng)d>0時(shí)，圖形沿+y方向作錯(cuò)切位移，ABCD→A1B1C1D1。

當(dāng)d<0時(shí)，圖形沿－y方向作錯(cuò)切位移，ABCD→A2B2C2D2。

(3)當(dāng)b≠0且d≠0時(shí)，(x′，y′)=(x+by，dx+y)，圖形沿x，y兩個(gè)方向作錯(cuò)切位移。因此，錯(cuò)切變換將引起圖形角度關(guān)系的改變，甚至導(dǎo)致圖形發(fā)生變形。圖3-11沿y方向錯(cuò)切變換3.2.5反射變換

反射變換后的圖形是原圖形關(guān)于某一軸線或原點(diǎn)的鏡像。主要的反射變換包括關(guān)于x軸的反射變換、關(guān)于y軸的反射變換、關(guān)于原點(diǎn)的反射變換、關(guān)于y=x的反射變換和關(guān)于y=－x的反射變換等。

1．關(guān)于x軸的反射變換

關(guān)于x軸的反射變換，其變換后的圖形與原圖形是關(guān)于x軸對(duì)稱的，因此，反射變換也稱為對(duì)稱變換。變換后得到的新圖形與原圖形的關(guān)系是:新圖形的x坐標(biāo)保持不變，而y坐標(biāo)取反。關(guān)于x軸的反射變換如圖3-12所示。圖3-12關(guān)于x軸的反射變換假設(shè)原圖形的坐標(biāo)用(x，y)表示，新圖形的坐標(biāo)用(x1，y1)表示，則從圖3-12可以看出，新圖形的坐標(biāo)x1=x，y1=－y。用矩陣表示該變換為

2．關(guān)于y軸的反射變換

與關(guān)于x軸的反射變換類似，關(guān)于y軸的反射變換，變換后的圖形與原圖形是關(guān)于y軸對(duì)稱的，新圖形與原圖形的關(guān)系是其y坐標(biāo)保持不變，而x坐標(biāo)取反。關(guān)于y軸的反射變換如圖3-13所示。

從圖3-13可以看出，新圖形的坐標(biāo)為x1=－x，y1=y。用矩陣表示該變換為圖3-13關(guān)于y軸的反射變換

3．關(guān)于坐標(biāo)原點(diǎn)的反射變換

關(guān)于坐標(biāo)原點(diǎn)的反射變換，其變換后的圖形與原圖形是關(guān)于坐標(biāo)原點(diǎn)對(duì)稱的，新圖形與原圖形的關(guān)系是其x、y坐標(biāo)均取反。關(guān)于坐標(biāo)原點(diǎn)的反射變換如圖3-14所示。

從圖3-14可以看出，新圖形的坐標(biāo)為x1=－x，y1=－y。用矩陣表示該變換為圖3-14關(guān)于坐標(biāo)原點(diǎn)的反射變換

4．關(guān)于y=x的反射變換

關(guān)于y=x的反射變換，其變換后的圖形與原圖形是關(guān)于直線y=x對(duì)稱的，新圖形的x坐標(biāo)取為原圖形的y坐標(biāo)，新圖形的y坐標(biāo)取為原圖形的x坐標(biāo)。關(guān)于y=x的反射變換如圖3-15所示。

從圖3-15可以看出，新圖形的坐標(biāo)為x1=y，y1=x。用矩陣表示該變換為圖3-15關(guān)于y=x的反射變換

5．關(guān)于y=－x的反射變換

關(guān)于y=－x的反射變換，其變換后的圖形與原圖形是關(guān)于直線y=－x對(duì)稱的，新圖形的x坐標(biāo)取為原圖形的－y坐標(biāo)，新圖形的y坐標(biāo)取為原圖形的－x坐標(biāo)。關(guān)于y=－x的反射變換如圖3-16所示。

從圖3-16可以看出，新圖形的坐標(biāo)為x1=－y，y1=－x。用矩陣表示該變換為圖3-16關(guān)于y=－x的反射變換3.2.6齊次坐標(biāo)表示

對(duì)于二維的幾何變換及變換中心在坐標(biāo)原點(diǎn)的比例縮放、反射、錯(cuò)切和旋轉(zhuǎn)等各種變換，都可以用2×2的矩陣表示和實(shí)現(xiàn)。但是一個(gè)2×2變換矩陣卻不能實(shí)現(xiàn)圖形的平移以及繞任意點(diǎn)的比例縮放、反射、錯(cuò)切和旋轉(zhuǎn)等各種變換。平移矩陣的第一、二列構(gòu)成單位矩陣，第三列元素為平移常量，平移矩陣表示如下：在實(shí)際繪圖時(shí)，常要對(duì)對(duì)象連續(xù)作幾次變換，例如作了平移后，作旋轉(zhuǎn)，再作放大等。若對(duì)每一個(gè)點(diǎn)的坐標(biāo)依次采用相應(yīng)的矩陣進(jìn)行計(jì)算，則計(jì)算量很大。若能夠先將變換矩陣合并成一個(gè)矩陣，然后再與向量進(jìn)行乘法運(yùn)算，即每個(gè)點(diǎn)的坐標(biāo)只需要進(jìn)行一次乘法運(yùn)算，則運(yùn)算速度可以得到極大的提高。但是，平移變換不能直接進(jìn)行合并，所以需要在點(diǎn)的坐標(biāo)列矩陣［x，y］中引入第三個(gè)元素，增加一個(gè)附加坐標(biāo)，擴(kuò)展為3×1的列矩陣［x，y，1］，這樣用三維空間點(diǎn)(x，y，1)表示二維空間點(diǎn)(x，y)，即采用一種特殊的坐標(biāo)，可以實(shí)現(xiàn)平移變換，變換結(jié)果為

簡(jiǎn)記為P′=P·T(Tx，Ty)。從上式可以看出，引入附加坐標(biāo)后，擴(kuò)充了矩陣的第3行，并沒有使變換結(jié)果受到影響。這種用n+1維向量表示n維向量的方法稱為齊次坐標(biāo)表示法。如n維向量(P1，P2，…，Pn)可表示為(hP1，hP2，…，hPn，h)，其中h稱為啞坐標(biāo)。因?yàn)閔可以取不同的值，所以同一點(diǎn)的齊次坐標(biāo)不是唯一的。如普通坐標(biāo)系下的點(diǎn)(2，3)變換為齊次坐標(biāo)可以是(1，1.5，0.5)、(4，6，2)、(6，9，3)等。普通坐標(biāo)與齊次坐標(biāo)的關(guān)系為“一對(duì)多”，由普通坐標(biāo)×h→齊次坐標(biāo)，由齊次坐標(biāo)÷h→普通坐標(biāo)。當(dāng)h=1時(shí)產(chǎn)生的齊次坐標(biāo)稱為“規(guī)格化坐標(biāo)”，因?yàn)榍皀個(gè)坐標(biāo)就是普通坐標(biāo)系下的n維坐標(biāo)。(x，y)點(diǎn)對(duì)應(yīng)的齊次坐標(biāo)為

(xh，yh，h)，xh=hx，yh=hy，h≠0將各種變換用階數(shù)統(tǒng)一的矩陣來(lái)表示，提供了用矩陣運(yùn)算把二維、三維甚至高維空間上的一個(gè)點(diǎn)從一個(gè)坐標(biāo)系變換到另一坐標(biāo)系的有效方法。齊次坐標(biāo)便于表示無(wú)窮遠(yuǎn)點(diǎn)。例

如：(x×h，y×h，h)，令h等于0，即可表示無(wú)窮遠(yuǎn)點(diǎn)。齊次坐標(biāo)變換矩陣形式把直線變換成直線，平面變換成平面，多邊形變換成多邊形，多面體變換成多面體，即圖形拓?fù)潢P(guān)系保持不變。齊次坐標(biāo)變換具有統(tǒng)一表示形式的優(yōu)點(diǎn)，便于變換合成，便于硬件實(shí)現(xiàn)。齊次坐標(biāo)表示的三維平移變換為

簡(jiǎn)記為P′=P·T(Tx，Ty，Tz)。齊次坐標(biāo)表示的二維縮放變換為

簡(jiǎn)記為P′=P·S(sx，sy)。

齊次坐標(biāo)表示的三維縮放變換為

簡(jiǎn)記為P′=P·S(sx，sy，sz)。齊次坐標(biāo)表示的二維旋轉(zhuǎn)變換為

簡(jiǎn)記為P′＝P·R2(θ)。

齊次坐標(biāo)表示的三維繞z軸旋轉(zhuǎn)的變換矩陣為

簡(jiǎn)記為P′＝P·R3(θ)。齊次坐標(biāo)表示的錯(cuò)切變換為3.2.7變換矩陣表示

1.二維變換的矩陣表示

二維圖形的幾何變換實(shí)現(xiàn)可以用矩陣表示為從變換功能上可把T2D分為四個(gè)子矩陣，其中 是對(duì)圖形的縮放、旋轉(zhuǎn)、對(duì)稱、錯(cuò)切等變換；［c

f］是對(duì)圖形進(jìn)行平移變換； 是對(duì)圖形作投影變換，g的作用是在x軸的1/g處產(chǎn)生一個(gè)滅點(diǎn)，h的作用是在y軸的1/h處產(chǎn)生一個(gè)滅點(diǎn)；［i］是對(duì)整個(gè)圖形作伸縮變換，該矩陣為單位矩陣即定義二維空間中的直角坐標(biāo)系。

2.三維變換的矩陣表示

若用齊次坐標(biāo)表示，三維幾何變換的矩陣是一個(gè)4階方陣，其形式如下：

其中： 產(chǎn)生縮放、旋轉(zhuǎn)、對(duì)稱、錯(cuò)切等變

換；［a41

a42

a43］產(chǎn)生平移變換； 產(chǎn)生投影變換；

［a44］產(chǎn)生整體的縮放變換。3.2.8復(fù)合變換

一個(gè)比較復(fù)雜的變換要連續(xù)進(jìn)行若干個(gè)基本變換才能完成，這些由基本變換構(gòu)成的連續(xù)變換序列稱為復(fù)合變換，如連續(xù)作平移、旋轉(zhuǎn)、放大等。由于采用齊次坐標(biāo)表示，可以將多個(gè)變換矩陣合并成一個(gè)復(fù)合變換矩陣，這樣每個(gè)點(diǎn)的坐標(biāo)只需要進(jìn)行一次乘法運(yùn)算即可，使得變換的運(yùn)算速度得到極大的提高。

以先平移，再旋轉(zhuǎn)為例，本應(yīng)進(jìn)行兩次變換，分別是P′＝P·T(xf

，yf)，P″＝P′·R(θ)。合并兩個(gè)變換公式得 P″＝P·(T(xf，yf)·R(θ))令Tc＝T(xf，yf)·R(θ)，則有P″＝P·Tc，Tc

稱為復(fù)合變換矩陣。由上面的推導(dǎo)可知，在計(jì)算復(fù)合變換時(shí)，首先可將各基本變換矩陣按序相乘，形成總的復(fù)合變換矩陣Tc，然后只需將坐標(biāo)與Tc相乘一次，便可同時(shí)完成一連串基本變換。

由于矩陣的乘法一般情況下不滿足交換率，因此，一般情況下T(xf，yf)·R(θ)≠R(θ)·T(xf，yf)。復(fù)合變換矩陣Tc的執(zhí)行方式是先調(diào)用的變換先執(zhí)行，后調(diào)用的后執(zhí)行。體現(xiàn)在矩陣合并時(shí)，先調(diào)用的變換矩陣放在左邊，后調(diào)用的變換矩陣放在右邊，這種方式稱為圖形模式或固定坐標(biāo)模式。它的特點(diǎn)是在連續(xù)執(zhí)行幾次變換時(shí)，每一次變換均可看成是相對(duì)于原坐標(biāo)系執(zhí)行的，如圖3-17所示。圖3-17圖形模式下的復(fù)合變換從圖3-17可以看出，平移是相對(duì)于原坐標(biāo)系進(jìn)行的，而旋轉(zhuǎn)變換也是在相同的坐標(biāo)系中完成的。若令Td=R(θ)·T(xf，yf)，這種模式稱為空間模式或活動(dòng)坐標(biāo)模式。在這種模式下，連續(xù)執(zhí)行幾個(gè)變換時(shí)，變換矩陣的合并方式恰好和圖形模式相反，即先調(diào)用的變換矩陣放在右邊，后調(diào)用的變換矩陣放在左邊，如圖3-18所示。圖3-18空間模式下的復(fù)合變換圖形模式的特點(diǎn)是每一次變換均可看成是在上一次變換所形成的新坐標(biāo)系中進(jìn)行的。圖3-17中的變換結(jié)果可以看做是先將對(duì)象平移，平移后在新對(duì)象處建立新的坐標(biāo)系，然后在新坐標(biāo)系中對(duì)對(duì)象再進(jìn)行旋轉(zhuǎn)變換。

不同的應(yīng)用要求不同的變換模式。在整體變換的基礎(chǔ)上再作一些比較獨(dú)立的局部變換常用空間模式。例如要適應(yīng)屏幕的大小，以便把圖形放在屏幕上不同的位置，這時(shí)要用空間模式。又例如要將機(jī)械手的手臂經(jīng)過變換后移動(dòng)到適當(dāng)位置，手腕和手指的運(yùn)動(dòng)是相對(duì)于手臂的，如果在手臂上建立了一個(gè)新坐標(biāo)系，手腕和手指的運(yùn)動(dòng)則要在新坐標(biāo)系中考慮，這種多次變換的情況要用空間模式。在很多繪圖的情況下要用圖形模式，在這種模式下用戶比較容易估計(jì)變換后的結(jié)果。3.2.9相對(duì)于任意參考點(diǎn)的幾何變換

前面講的縮放、旋轉(zhuǎn)等幾何變換都是相對(duì)于坐標(biāo)原點(diǎn)的，這樣常使變換后的圖形不在原來(lái)的位置上。原圖形距坐標(biāo)原點(diǎn)越遠(yuǎn)，位置改變?cè)矫黠@。例如將物體放大2倍，可能會(huì)產(chǎn)生明顯的位移，如圖3-19所示。

從圖3-19中可以看出，原圖經(jīng)過放大后發(fā)生了明顯的位移。為了使變換后的圖形仍在原來(lái)的位置附近，可另外定義一個(gè)相似中心。例如可取相似中心為圖形的中心。圖3-19相對(duì)于坐標(biāo)原點(diǎn)放大兩倍如果相對(duì)某個(gè)一般的參考點(diǎn)(xf

，yf)作縮放、旋轉(zhuǎn)變換，相當(dāng)于將該點(diǎn)移到坐標(biāo)原點(diǎn)處，然后進(jìn)行縮放、旋轉(zhuǎn)變換，最后將(xf，yf)點(diǎn)移回原來(lái)的位置。

關(guān)于(xf，yf)點(diǎn)的縮放變換的變換矩陣如下：繞(xf，yf)點(diǎn)的旋轉(zhuǎn)變換矩陣如下：各種復(fù)雜的變換都是一些基本變換的組合。解決復(fù)合變換問題，關(guān)鍵是將其分解為一定順序的基本變換，然后逐一進(jìn)行這些基本變換；或者求出這些基本變換矩陣的連乘積，即得復(fù)合變換矩陣，進(jìn)而由矩陣作復(fù)合變換使得問題被解決。

例3-1相對(duì)任意點(diǎn)的旋轉(zhuǎn)。如圖3-20所示，要求三角形相對(duì)于Q點(diǎn)正向旋轉(zhuǎn)30°，求其變換后的三角形。圖3-20變換前的原圖

解

(1)將Q點(diǎn)移至坐標(biāo)原點(diǎn)，三角形的三個(gè)頂點(diǎn)的齊次坐標(biāo)為

則平移后的三個(gè)頂點(diǎn)的齊次坐標(biāo)為平移后的圖形如圖3-21所示。圖3-21平移變換

(2)三角形相對(duì)坐標(biāo)原點(diǎn)旋轉(zhuǎn)30°，則該三角形三個(gè)頂點(diǎn)的齊次坐標(biāo)為

旋轉(zhuǎn)后的圖形如圖3-22所示。圖3-22旋轉(zhuǎn)變換

(3)點(diǎn)Q還原到原位置，則該三角形三個(gè)頂點(diǎn)的齊次坐標(biāo)為

Q點(diǎn)還原后的圖形如圖3-23所示。圖3-23反方向平移(旋轉(zhuǎn)后的效果圖)在例3-1中實(shí)現(xiàn)了將三角形相對(duì)任意參考點(diǎn)的旋轉(zhuǎn)變換，方法采用的是將圖形的所有點(diǎn)與每個(gè)變換矩陣分別進(jìn)行相乘。這種方法在圖形比較復(fù)雜時(shí)，即點(diǎn)的坐標(biāo)比較多時(shí)效率很低。

例3-2相對(duì)任意軸的反射變換。如圖3-24(a)所示，要求對(duì)一個(gè)三角形相對(duì)軸線y=bx+a進(jìn)行反射變換。

解變換過程如圖3-24(b)～(f)所示。

(1)將點(diǎn)(0，a)平移至坐標(biāo)原點(diǎn)，如圖3-24(b)所示，其變換矩陣為圖3-24相對(duì)于任意參考軸的幾何變換

(2)將軸線y=bx沿順時(shí)針方向旋轉(zhuǎn)θ角，使其落在x軸上，其變換矩陣為

角度θ的計(jì)算公式為tanθ=b。

(3)三角形相對(duì)x軸作反射變換，其變換矩陣為

(4)作第(2)步的逆變換，其變換矩陣為

(5)作第(1)步的逆變換，其變換矩陣為

(6)將上述5步綜合起來(lái)，作為三角形相對(duì)軸線y=bx+a進(jìn)行反射變換的變換矩陣：則反射變換后，新三角形三個(gè)頂點(diǎn)的齊次坐標(biāo)為

例3-2中采用的方法與例3-1有所不同，該例將5個(gè)變換矩陣合并為一個(gè)復(fù)合變換矩陣后與原圖中點(diǎn)的坐標(biāo)進(jìn)行了一次乘法，這樣當(dāng)圖形中的點(diǎn)比較多時(shí)，算法的效率將明顯高

于例3-1的方法。 3.3投影變換

三維圖形的一個(gè)基本問題是如何在二維屏幕上顯示三維物體。由于顯示器屏幕、繪圖紙等是二維的，而要顯示的對(duì)象是三維的，因此，必須進(jìn)行投影變換才能在二維的顯示屏幕上將三維的物體顯示出來(lái)。當(dāng)然，三維圖形的顯示除了需要進(jìn)行投影變換外，還要解決三維形體的表示問題、消除隱藏面與隱藏線問題，以及建立光照明模型、研究真實(shí)感圖形繪制方法問題。投影變換就是把三維立體(或物體)投射到投影面上得到二維平面圖形。投影中心是觀察者的觀察點(diǎn)或稱為視點(diǎn)；投影面是不經(jīng)過投影中心的平面；投影線是從投影中心向物體上各點(diǎn)發(fā)出的射線。有兩種基本投影方法：平行投影和透視投影，如圖3-25所示。圖3-25平行投影和透視投影透視投影是指使用一組由投影中心產(chǎn)生的放射投影線，將三維對(duì)象投影到投影平面上去。透視投影的投影中心與投影面之間的距離是有限的。

平行投影是使用一組平行投影線將三維對(duì)象投影到投影平面上去。平行投影的投影中心與投影平面之間的距離是無(wú)限的，因此，投影線之間可以看做是相互平行的。

3.3.1透視投影變換

透視投影的參數(shù)主要有投影方向和投影距離。透視投影主要適用于室內(nèi)白熾燈的投影及視覺系統(tǒng)仿真。透視投影的特點(diǎn)是產(chǎn)生近大遠(yuǎn)小的視覺效果，由于它產(chǎn)生的圖形深度感強(qiáng)，看起來(lái)更加真實(shí)，如圖3-26所示。圖3-26透視投影示意圖根據(jù)三角形相似原理，有

則可以得到

令 ，因此，得到透視投影的變換矩陣為采用上述變換矩陣計(jì)算得到的投影坐標(biāo)為

三維物體經(jīng)過透視投影后，存在滅點(diǎn)問題,即不平行于投影面的平行線的投影會(huì)匯聚到一個(gè)點(diǎn)，這個(gè)點(diǎn)稱為滅點(diǎn)。其中，坐標(biāo)軸方向的平行線在投影面上形成的滅點(diǎn)稱做主滅點(diǎn)。根據(jù)主滅點(diǎn)的數(shù)量可以將透視投影分為一點(diǎn)透視、兩點(diǎn)透視和三點(diǎn)透視，如圖3-27所示。一點(diǎn)透視：有一個(gè)主滅點(diǎn)，即投影面與一個(gè)坐標(biāo)軸正交，與另外兩個(gè)坐標(biāo)軸平行。

兩點(diǎn)透視：有兩個(gè)主滅點(diǎn)，即投影面與兩個(gè)坐標(biāo)軸相交，與另一個(gè)坐標(biāo)軸平行。

三點(diǎn)透視：有三個(gè)主滅點(diǎn)，即投影面與三個(gè)坐標(biāo)軸都相交。

圖3-27(a)就是一點(diǎn)透視圖。一點(diǎn)透視的主要參數(shù)有：三維形體與畫面(投影面)的相對(duì)位置；視距，即視點(diǎn)(投影中心)與畫面的距離；視點(diǎn)的高度。圖3-27三種類型的透視投影圖3-27(b)是兩點(diǎn)透視圖，可以這樣來(lái)構(gòu)造兩點(diǎn)透視：先將三維形體平移到適當(dāng)位置，使視點(diǎn)有一定高度，且使形體的主要表面不會(huì)積聚成線；將形體繞y軸旋轉(zhuǎn)一個(gè)φ角(φ＜90°)，方向滿足右手定則；進(jìn)行透視變換；最后向xoy面作正投影，即得兩點(diǎn)透視圖，如圖3-28所示。圖3-28兩點(diǎn)透視圖圖3-27(c)是三點(diǎn)透視圖，其構(gòu)造過程是：首先將三維形體平移到適當(dāng)位置，將形體進(jìn)行透視變換；然后使形體先繞y軸旋轉(zhuǎn)φ角；再繞x軸旋轉(zhuǎn)θ角；將變形且旋轉(zhuǎn)后的形體向xoy面作正投影。

例3-3把圖3-29中的立方體投影到xy平面上，使用透視投影變換畫出單位立方體的投影圖像，其中d=1。圖3-29對(duì)三維立方體進(jìn)行透視投影

解

(1)用全部頂點(diǎn)的齊次坐標(biāo)來(lái)表示立方體：

(2)由于投影面為xoy面，故透視變換的投影矩陣為

(3)用透視投影矩陣作用于坐標(biāo)矩陣V，并將d=1代入得：

(4)將齊次坐標(biāo)轉(zhuǎn)換為三維坐標(biāo)，則投影后的圖像有坐標(biāo)：

A′=(0，0，0)

B′=(1，0，0)

C′=(1，1，0)

D′=(0，1，0)

E′=(0，1/2，0)

F′=(0，0，0)

G′=(1/2，0，0)

H′=(1/2，1/2，0)3.3.2平行投影變換

按照投影線與投影面的交角的不同，可將平行投影分為兩類：正投影和斜投影，如圖3-30所示。圖3-30平行投影正投影又可分為三視圖和正軸測(cè)圖。當(dāng)投影面與某一坐標(biāo)軸垂直時(shí)，得到的投影為三視圖，如圖3-31(a)所示；否則，得到的投影為正軸測(cè)圖，如圖3-31(b)所示。圖3-31三視圖和正軸測(cè)圖正投影的投影線與投影平面成90°角。將一個(gè)三維點(diǎn)(x，y，z)用正交平行投影法投影到投影平面xoy上，得到一個(gè)二維點(diǎn)(xp，yp)。這種變換可以由正投影變換公式來(lái)計(jì)算： xp=x

yp=y

zp=0

同樣，也可以將三維物體正投影于xoz和yoz平面上，分別獲得主視圖與側(cè)視圖。設(shè)計(jì)中常把正投影產(chǎn)生的三視圖稱為正視圖。它們具有x、y方向易于測(cè)量的特點(diǎn)，因此可作為主要的工程施工圖紙，如圖3-32所示。圖3-32三視圖投影方向不垂直于投影平面的平行投影被稱為斜投影，如圖3-33所示。其中，z=0的坐標(biāo)平面為觀察平面，點(diǎn)(x，y)為點(diǎn)(x，y，z)在觀察平面上的正投影坐標(biāo)，點(diǎn)(x′，y′)為斜投影坐標(biāo)。(x，y)與(x′，y′)的距離為L(zhǎng)。斜投影的投影線與投影面成β交角。L與x軸之夾角為α。

斜投影變換的公式為

x′＝x＋Lcosα

y′＝y(tǒng)＋Lsinα

而L的長(zhǎng)度依賴于z和β：圖3-33斜投影由此可知，當(dāng)β一定時(shí)，L與z成比例。則

令L1=1/tanβ，則上式可改寫為

x′=x＋z(L1·cosα)

y′=y＋z(L1·sinα)

z′=0它的矩陣運(yùn)算式為

式中的L1與α是任意斜投影的重要顯示參數(shù)，它們的物理意義由圖3-33可知，α控制與z軸平行的線的投影方向，L1則控制投影的長(zhǎng)度。在工程制圖中，經(jīng)常選擇一些兼有美觀及繪圖方便的α與L1之值來(lái)投影。常用值有：

(1)α＝45°或α＝30°，此時(shí)既美觀，繪圖也方便。

(2)L1=1，即z＝L(tanα＝1，α＝45°)，此時(shí)可以在投影圖上直接量出z的大小。

(3)L1=0.5，即z＝2L(tanα＝2，α＝63.4°)，此時(shí)圖形比較美觀，z值也較易算出。 3.4圖形裁剪

在二維觀察中，需要在觀察坐標(biāo)系下對(duì)窗口進(jìn)行裁剪，即只保留窗口內(nèi)的那部分圖形，去掉窗口外的圖形。對(duì)于一個(gè)二維矩形區(qū)域的裁剪，將這個(gè)矩形區(qū)域稱為窗口。當(dāng)窗口被確定之后，只有窗口內(nèi)的物體才能顯示出來(lái)，窗口之外的物體都是不可見的,如圖3-34所示。

假設(shè)窗口是標(biāo)準(zhǔn)矩形，即邊與坐標(biāo)軸平行的矩形，由上(y=wyt)、下(y=wyb)、左(x=wxl)、右(x=wxr)四條邊描述。因此，裁剪是裁去窗口之外物體的一種操作。圖形裁剪算法直接影響圖形系統(tǒng)的效率。圖3-34裁剪的示意圖3.4.1點(diǎn)的裁剪

點(diǎn)的裁剪是圖形裁剪中最基本的問題。對(duì)于給定點(diǎn)P(x，y)，P點(diǎn)在窗口內(nèi)的條件是要滿足下列不等式：

wxl≤x≤wxr

wyb≤y≤wyt

否則，P點(diǎn)就在窗口外。

3.4.2直線的裁剪

直線的裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來(lái)近似，從而裁剪問題也可以化為直線段的裁剪問題。假定直線段用P1(x1，y1)P2(x2，y2)表示。直線段和剪裁窗口的可能關(guān)系是(如圖3-35所示)：圖3-35直線段與窗口的關(guān)系

(1)完全落在窗口內(nèi)，此時(shí)不需裁剪，顯示整條直線。

(2)完全落在窗口外，此時(shí)不需裁剪，不顯示整條直線。

(3)與窗口邊界相交，部分在窗口之外。此時(shí)，需要求出直線與窗口之交點(diǎn)，并將窗口外的直線部分裁剪掉，顯示窗口內(nèi)的部分。

在圖3-35中，直線段EF對(duì)應(yīng)于第一種情況，完全在窗口內(nèi)；IJ和DC對(duì)應(yīng)第二種情況，完全在窗口外；AB和HG對(duì)應(yīng)第三種情況，和窗口有交點(diǎn)。直線與窗口的交點(diǎn)分為兩類：

實(shí)交點(diǎn)和虛交點(diǎn)。實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)，虛交點(diǎn)則是直線段與窗口矩形邊界延長(zhǎng)線或直線段的延長(zhǎng)線與窗口矩形邊界的交點(diǎn)，如圖3-36所示。圖3-36實(shí)交點(diǎn)與虛交點(diǎn)要提高裁剪算法的效率，就是要能夠快速判斷直線段和剪裁窗口的關(guān)系(1)和(2)，對(duì)于關(guān)系(3)，設(shè)法減少求交次數(shù)和每次求交時(shí)所需的計(jì)算量。

1.Cohen-Sutherland算法

該算法的基本思想是：首先將不需剪裁的直線挑出，并刪去全部在窗外的直線；然后對(duì)其余直線逐條與窗口求交點(diǎn)，并將窗外部分刪去。關(guān)鍵問題是如何判斷直線是否與窗

口有交點(diǎn)。

Cohen-Sutherland算法采用區(qū)域編碼方法解決交點(diǎn)問題，對(duì)窗口及其周圍的8個(gè)方向以4bit的二進(jìn)制數(shù)進(jìn)行編碼。4個(gè)bit分別代表窗外上、下、左、右空間的編碼值。如左上區(qū)域編碼為1001，右上區(qū)域編碼為1010，窗內(nèi)編碼為0000，如圖3-37所示。

圖3-37所示的編碼方法，是將4位的二進(jìn)制碼D3D2D1D0按如下的編碼規(guī)則進(jìn)行編碼：

(1)若x<wxl，則D0=1，否則D0=0；

(2)若x>wxr，則D1=1，否則D1=0；

(3)若y<wyb，則D2=1，否則D2=0；

(4)若y>wyt，則D3=1，否則D3=0。圖3-37窗口與區(qū)域編碼根據(jù)以上編碼規(guī)則，可將窗口及其鄰域分為5個(gè)區(qū)域：內(nèi)域(0000)，上域(1001，1000，1010)，下域(0101，0100，0110)，左域(1001，0001，0101)，右域(1010，0010，0110)。一旦給定所有的線段端點(diǎn)的區(qū)域碼，就可以快速判斷哪條直線完全在裁剪窗口內(nèi)，哪條直線完全在窗口外。

這種編碼方法的優(yōu)點(diǎn)是：如果一條直線的兩端在同一區(qū)域，則該直線不需裁剪，否則，該直線為可能裁剪直線；對(duì)可能裁剪的直線，縮小與之求交的邊框范圍，規(guī)則是：如果直線的一個(gè)端點(diǎn)在上(下、左、右)域，則將此直線與上邊框求交，然后刪去上邊框以上的部分。該規(guī)則對(duì)直線的另一端點(diǎn)也適用。這樣，一條直線至多只需與兩條邊框求交。因此，Cohen-Sutherland的區(qū)域編碼裁剪算法是一個(gè)簡(jiǎn)明高速的直線裁剪算法。

Cohen-Sutherland算法的主要思想為：

裁剪一條線段時(shí)，先求出端點(diǎn)P1和P2的編碼code1和code2，然后：

(1)若code1|code2=0，對(duì)直線段應(yīng)保留，顯示該直線段。

(2)若code1&code2≠0，對(duì)直線段可放棄，不顯示。

(3)若上述兩條件均不成立，則需求出直線段與窗口邊界的交點(diǎn)。在交點(diǎn)處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對(duì)另一段重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找到位于窗口內(nèi)的一段線段為止。

Cohen-Sutherland算法的步驟是：

(1)輸入直線段的兩端點(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ì)直線段應(yīng)保留，轉(zhuǎn)(6)；否則，若code1&code2≠0，對(duì)直線段可放棄，轉(zhuǎn)(7)；當(dāng)上述條件均不滿足時(shí)，進(jìn)行步驟(4)。

(4)確保P1在窗口外部：若P1在窗口內(nèi)，則交換P1和P2的坐標(biāo)值和編碼。

(5)按左、右、上、下的順序求出直線段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的坐標(biāo)值替換P1的坐標(biāo)值。也即在交點(diǎn)S處把線段一分為二，并去掉P1S這一段?？紤]到P1是窗口外的一點(diǎn)，因此可以去掉P1S。轉(zhuǎn)(2)。

(6)用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段P1P2。

算法結(jié)束。

過程clip描述了這一算法，其中用一個(gè)集合(top,bottom，right，left)來(lái)表示端點(diǎn)的編碼。該算法的優(yōu)點(diǎn)在于簡(jiǎn)單，易于實(shí)現(xiàn)，可以簡(jiǎn)單地描述為將直線在窗口左邊的部分刪去，按左、右、上、下的順序依次進(jìn)行，處理之后，剩余部分就是可見的了。在這個(gè)算法中求交點(diǎn)是很重要的，決定了算法的速度。但是，該算法對(duì)于其他形狀的窗口不一定有效。該算法的特點(diǎn)：用編碼方法可快速判斷線段的完全可見和顯然不可見。

2.中點(diǎn)分割算法

中點(diǎn)分割算法的基本思想：當(dāng)對(duì)直線段不能判斷出是保留還是放棄時(shí)，簡(jiǎn)單地把線段等分為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直至每條線段完全在窗口內(nèi)或完全在窗口外，如圖3-38所示。圖3-38中點(diǎn)分割圖與Cohen-Sutherland算法一樣，首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況。對(duì)于前兩種情況，進(jìn)行與Cohen-Sutherland算法一樣的處理；對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。中點(diǎn)分割算法的核心思想是通過二分逼近來(lái)確定直線段與窗口的交點(diǎn)算法步驟：

(1)若code1|code2=0，對(duì)直線段應(yīng)保留，結(jié)束；否則，若code1&code2≠0，對(duì)直線段可放棄，結(jié)束；當(dāng)這兩條均不滿足時(shí)，進(jìn)行步驟(2)。

(2)找出該直線段離窗口邊界最遠(yuǎn)的端點(diǎn)和該直線段的中點(diǎn)。判斷中點(diǎn)是否在窗口內(nèi)，若不在，則把中點(diǎn)和離窗口邊界最遠(yuǎn)點(diǎn)構(gòu)成的線段丟掉，以線段上的另一端點(diǎn)和該中點(diǎn)再構(gòu)成線段求其中點(diǎn)。如中點(diǎn)在窗口外，則又以中點(diǎn)和最遠(yuǎn)點(diǎn)構(gòu)成線段，并求其中點(diǎn)，直到中點(diǎn)與窗口邊界的坐標(biāo)值在規(guī)定的誤差范圍內(nèi)相等，則該中點(diǎn)就是該線段落在窗口內(nèi)的一個(gè)端點(diǎn)坐標(biāo)。

(3)如另一點(diǎn)在窗口內(nèi)，則經(jīng)(2)即確定了該線段在窗口內(nèi)的部分。如另一點(diǎn)不在窗口內(nèi)，則該點(diǎn)和所求出的在窗口上的那一點(diǎn)構(gòu)成一條線段，重復(fù)步驟(2)，即可求出落在窗口內(nèi)的另一點(diǎn)。

中點(diǎn)分割算法的算法流程圖如圖3-39所示。圖3-39中點(diǎn)分割算法的流程圖中點(diǎn)分割算法的優(yōu)點(diǎn)是：對(duì)分辨率為2N×2N的顯示器，上述二分過程至多進(jìn)行N次；算法的主要過程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用左右移位來(lái)代替乘除法，這樣就大大加快了速度。

其他裁剪算法還有梁友棟-Barsky算法、快速算法等。

3.4.3多邊形的裁剪

對(duì)于多邊形的裁剪，如果使用直線裁剪算法進(jìn)行裁剪，裁剪后的多邊形之邊就會(huì)成為一組彼此不連貫的折線，從而給填色帶來(lái)困難，如圖3-40所示。圖3-40多邊形裁剪從圖3-40可以看出，多邊形的邊界不再封閉，容易產(chǎn)生歧義。因此，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它。多邊形裁剪算法需要通過裁剪，不僅保持窗口內(nèi)多邊形的邊界部分，而且要將窗框的有關(guān)部分按一定次序插入多邊形之保留邊界之間，從而使裁剪后的多邊形之邊仍舊保持封閉狀態(tài)，以使填色算法得以正確實(shí)現(xiàn)。

1.Sutherland-Hodgman算法

該算法采用分割處理策略，將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。其處理過程稱為流水線過程(左上右下)，即前邊的結(jié)果是后邊的輸入。該算法亦稱為逐邊裁剪算法。

該算法的基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線，把平面分成兩個(gè)部分：可見一側(cè)和不可見一側(cè)。多邊形的各條邊的兩端點(diǎn)表示為S、P，它們與裁剪線的位置關(guān)系只有四種，如圖3-41所示。圖3-41裁剪線與各邊的四種位置關(guān)系對(duì)應(yīng)于四種情況，其輸出各不相同：

情況(1)僅輸出頂點(diǎn)P；

情況(2)輸出0個(gè)頂點(diǎn)；

情況(3)輸出線段SP與裁剪線的交點(diǎn)；

情況(4)輸出線段SP與裁剪線的交點(diǎn)和終點(diǎn)P。

Sutherland-Hodgman算法步驟：

(1)上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪，得到一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過程的輸入。

(2)對(duì)于每一條裁剪邊，算法框圖如圖3-39所示，只是判斷點(diǎn)在窗口哪一側(cè)以及求線段SP與裁剪邊的交點(diǎn)，算法的輸出隨之改變。圖3-42是一個(gè)采用Sutherland-Hodgman算法進(jìn)行多邊形裁剪的例子。

對(duì)凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對(duì)凹多邊形的裁剪將顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個(gè)或者多個(gè)分離部分的時(shí)候出現(xiàn)。因?yàn)橹挥幸粋€(gè)輸出頂點(diǎn)表，所以表中最后一個(gè)頂點(diǎn)總是連著第一個(gè)頂點(diǎn)。

解決這個(gè)問題有多種方法。一種是把凹多邊形分割成若干個(gè)凸多邊形，然后分別處理各個(gè)凸多邊形。另一種是修改本算法，沿著任何一個(gè)裁剪窗口邊檢查頂點(diǎn)表，正確的連接頂點(diǎn)對(duì)。再有就是Weiler-Atherton算法。圖3-42多邊形裁剪的實(shí)例

2.Weiler-Atherton多邊形裁剪算法

假定按順時(shí)針方向處理頂點(diǎn)，且將用戶多邊形定義為Ps，窗口矩形為Pw。算法從Ps的任一點(diǎn)出發(fā)，跟蹤檢測(cè)Ps

的每一條邊，當(dāng)Ps與Pw相交時(shí)(實(shí)交點(diǎn))，按如下規(guī)則處理：

(1)若是由不可見側(cè)進(jìn)入可見側(cè)，則輸出可見直線段，轉(zhuǎn)(3)。

(2)若是由可見側(cè)進(jìn)入不可見側(cè)，則從當(dāng)前交點(diǎn)開始，沿窗口邊界順時(shí)針檢測(cè)Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當(dāng)前交點(diǎn)的另一交點(diǎn)，輸出可見直線段和由當(dāng)前交點(diǎn)到另一交點(diǎn)之間窗口邊界上的線段，然后返回處理的當(dāng)前交點(diǎn)。

(3)沿著Ps處理各條邊，直到處理完P(guān)s的每一條邊，回到起點(diǎn)為止。

圖3-43給出了用Weiler-Atherton算法裁剪凹多邊形的過程和結(jié)果。圖3-43

Weiler-Atherton算法的過程和結(jié)果

例3-4對(duì)于邊界與x和y軸平行的矩形窗口，在其上進(jìn)行的裁剪涉及計(jì)算直線段與垂直和水平線的交點(diǎn)。請(qǐng)求出線段P1P2(P1(x1，y1)，P2(x2，y2))與下列直線的交點(diǎn)：①垂直線x=a；②水平線y=b。

解用參數(shù)形式寫出P1P2的方程：

x=x1+t(x2－x1)，0≤t≤1

(1)

y=y1+t(y2－y1)，0≤t≤1

(2)

①將x=a代入方程(1)，求得 ，然后將t代入方程(2)，求得交點(diǎn)為

②將y=b代入方程(2)，求得 ，然后將t代入方程(2)，求得交點(diǎn)為

例3-5怎樣才能確定點(diǎn)P(x，y)是位于一條連接點(diǎn)A(x1，y1)和B(x2，y2)的直線的左邊還是右邊？

解構(gòu)造向量AB和AP，如果點(diǎn)P是在AB的左邊，那么按照兩個(gè)向量積的定義，AB×AP

指向垂直于xy平面的向量K的方向。如果點(diǎn)P在AB的右邊，那么向量積指向－K的向，現(xiàn)有

AB=(x2－x1)I+(y2－y1)J

AP=(x－x1)I+(y－y1)J

所以

AB×AP=［(x2－x1)(y－y1)－(y2－y1)(x－x1)］K

則這個(gè)向量積的方向由下面的數(shù)確定：

H=(x2－x1)(y－y1)－(y2－y1)(x－x1)

如果H為正，則P位于AB的左邊；如果H為負(fù)，則P位于AB的右邊。

例3-6使用Sutherland-Hodgman算法,以A(1，1)，B(5，3)，C(4，5)，D(0，3)所圍著的矩形作為窗口，對(duì)連接P1(－1，2)到P2(6，4)的線段進(jìn)行裁剪。

解