計(jì)算機(jī)圖形學(xué)：Lecture 8 開窗口及二維裁剪

1、Lecture 8開窗口及二維裁剪 概述我們把用一觀察窗口有選擇地顯示物體的某一部分稱為開窗口技術(shù)，如果要求刪除顯示區(qū)域之外的畫面部分則稱為裁剪，用開窗口技術(shù)不但可靈活地顯示物體的各個(gè)部分，還可通過動(dòng)態(tài)地改變畫面的大小及位置，產(chǎn)生某些特殊的顯示效果。 開窗口及裁剪的基本概念 坐標(biāo)系 窗口與視區(qū) 窗口在圖形顯示中的應(yīng)用 裁剪 坐標(biāo)系 圖形系統(tǒng)中使用的坐標(biāo)系是人們廣為熟悉的直角坐標(biāo)系，也稱笛卡爾坐標(biāo)系。 建模坐標(biāo)系 世界坐標(biāo)系 設(shè)備坐標(biāo)系 規(guī)格化設(shè)備坐標(biāo)系 建模坐標(biāo)系 構(gòu)造一個(gè)復(fù)雜的場(chǎng)景需要許多物體，如果這些物體都定義于世界坐標(biāo)系中，那么它們的表示可能是極其復(fù)雜的，甚至是難于構(gòu)造的.此時(shí)，不妨將物

2、體定義于其局部坐標(biāo)系建模坐標(biāo)系（MC：Modeling Coordinates）中，由于建模坐標(biāo)系是依物體而建的，物體在其中的表示相對(duì)簡(jiǎn)單，易于描述，模型坐標(biāo)系是直角右手坐標(biāo)系，長(zhǎng)度單位由用戶自定，取值范圍是整個(gè)實(shí)數(shù)域。 世界坐標(biāo)系 單個(gè)物體的形狀一旦被指定后，需要將其放入到場(chǎng)景的適當(dāng)位置.世界坐標(biāo)系也就是場(chǎng)景坐標(biāo)系。場(chǎng)景是采用世界坐標(biāo)系（WC：World Coordinates）描述的，世界坐標(biāo)系是直角右手坐標(biāo)系，長(zhǎng)度單位由用戶自定，取值范圍是整個(gè)實(shí)數(shù)域。 設(shè)備坐標(biāo)系 圖形用的第三種坐標(biāo)系是設(shè)備坐標(biāo)系（DC：Device Coordinates）。 顯示器屏幕的直角坐標(biāo)系，原點(diǎn)在左上角，x軸

3、向右為正，y軸向下為正，長(zhǎng)度以光柵單位(兩個(gè)像素之距)為單位。 繪圖儀、數(shù)字化儀這類設(shè)備的坐標(biāo)系，原點(diǎn)在設(shè)備臺(tái)面的左下角，x軸向右為正，y軸向上為正，長(zhǎng)度單位是設(shè)備的步距。 規(guī)格化設(shè)備坐標(biāo)系 第四種坐標(biāo)系稱為規(guī)格化設(shè)備坐標(biāo)系（NDC：Normalized Device Coordinates）。NDC是一種虛擬的坐標(biāo)系，它與具體設(shè)備無(wú)關(guān)，其坐標(biāo)值在0l之間。NDC將WC與DC聯(lián)系起來(lái)，使兩種坐標(biāo)系間建立一一對(duì)應(yīng)的關(guān)系，用戶在用WC描述物體圖形時(shí)，能在具體的圖形設(shè)備上正確輸出。 坐標(biāo)系變換通常，在最后變換為特定的設(shè)備坐標(biāo)之前，圖形系統(tǒng)需要將世界坐標(biāo)位置變換為規(guī)范化設(shè)備坐標(biāo)位置。這樣可使系統(tǒng)獨(dú)立于

4、可能使用的特定工作站的各種設(shè)備。下圖是從建模坐標(biāo)系到設(shè)備坐標(biāo)系的坐標(biāo)變換系列。圖中初始的建模坐標(biāo)位置（xmc, ymc）變換為設(shè)備坐標(biāo)位置（xdc, ydc），其序列為：（xmc, ymc）（xwc, ywc）（xndc, yndc）（xdc, ydc） 窗口與視區(qū) 考察一個(gè)圖形時(shí)，采用兩種模型：物理模型，它是用戶在世界坐標(biāo)系中描述物體的圖形；邏輯模型，也就是在顯示器上呈現(xiàn)的物體的圖形它是在設(shè)備坐標(biāo)系中描述的。世界坐標(biāo)系中描述物體的圖形可能相當(dāng)復(fù)雜：只能在顯示器上顯示局部的內(nèi)容，以使用戶能清晰地觀察其細(xì)節(jié)部分 用戶可能只對(duì)圖形的某一區(qū)域感興趣，因此也只需要顯示這一感興趣的區(qū)域 窗口與視區(qū)這個(gè)局

5、部的區(qū)域是由用戶在世界坐標(biāo)系中指定，而且通常是矩形區(qū)域，稱這個(gè)矩形區(qū)域?yàn)榇翱冢╓indow）指定或選取這樣的一個(gè)區(qū)域稱為開窗口。不是把整個(gè)屏幕都用來(lái)顯示窗口內(nèi)的圖形，而是在屏幕上指定一個(gè)較小的矩形區(qū)域用于顯示窗口內(nèi)的圖形，這個(gè)在屏幕上的矩形區(qū)域就稱為視區(qū)（Viewport），它是用規(guī)格化設(shè)備坐標(biāo)系進(jìn)行描述的。 窗口與視區(qū)窗口是在世界坐標(biāo)系中指定待顯示內(nèi)容的區(qū)域，視區(qū)是在顯示器（輸出設(shè)備）上顯示窗口內(nèi)圖形的區(qū)域。 窗口與視區(qū)的關(guān)系 如下圖：窗口在圖形顯示中的應(yīng)用 利用開窗口技術(shù)，可靈活地在屏幕上顯示一景物的不同部分 ：改變位置變焦：觀察細(xì)節(jié)放大、縮小尺寸掠過要觀察的物體多方位的觀察物體窗口到視區(qū)

6、的變換 在點(diǎn)、直線、多邊形及文本的裁剪完成后，最后的結(jié)果要映射到視區(qū)中顯示出來(lái)。在此映射過程中，畫面的相對(duì)比例保持不變。在下圖中，窗口內(nèi)位于（xw，yw）處的一點(diǎn)映射入視區(qū)的（xv，yv）處，為保持點(diǎn)在窗口與在視區(qū)的相對(duì)位置一致，則應(yīng)滿足以下關(guān)系： 窗口到視區(qū)的變換改寫以下兩式可得到計(jì)算坐標(biāo)xv及yv的公式如下：從窗口到視區(qū)的變換中包括比例及平移兩種變換。 窗口到視區(qū)的變換窗口視區(qū)變換也可以通過組合變換實(shí)現(xiàn)：在世界坐標(biāo)系Owxwyw中，平移使(xwmin，ywmin)至坐標(biāo)原點(diǎn)，變換為T(-xwmin,-ywmin)。 縮放使窗口的大小和視區(qū)相等，變換為：在設(shè)備坐標(biāo)系Ovxvxv中，平移使窗口

7、與視區(qū)重合，變換為T(xvmin, yvmin)。 窗口到視區(qū)的變換那么，窗口視區(qū)變換可表示為：則有： 裁剪 刪去窗口邊界外所定義畫面部分的過程稱為裁剪（Clipping）。裁剪有兩種實(shí)現(xiàn)方式：一種是先將圖形對(duì)象針對(duì)窗口進(jìn)行裁剪，然后只把窗口內(nèi)的圖形映射入視區(qū)（這種方法稱為先裁剪后掃描轉(zhuǎn)換）另一種是把世界坐標(biāo)系中定義的圖形首先映射入規(guī)格化坐標(biāo)系，然后沿視區(qū)邊界裁剪（這種方法稱為邊掃描轉(zhuǎn)換邊裁剪）。一般采用前一種方式。裁剪為了實(shí)現(xiàn)沿窗口邊界對(duì)圖形的裁剪，我們首先要討論組成圖形的基本因素（點(diǎn)、線、區(qū)域）的裁剪算法。沿著邊界對(duì)點(diǎn)的裁剪是十分簡(jiǎn)單方便的，我們只要檢查一個(gè)點(diǎn)是否在邊界內(nèi)即可。點(diǎn)（x，y）

8、若滿足以下不等式則保存下來(lái)并映射入視區(qū)： xwminxxwmax , ywminyywmax 如果以上四個(gè)不等式中任一個(gè)不成立，則該點(diǎn)被裁剪。直線及區(qū)域與邊界相交的情況則復(fù)雜得多，其裁剪算法也必須考慮多種情況。 直線的裁剪直線與窗口的關(guān)系通常有以下三種情況：整個(gè)線段全在窗口內(nèi)；整個(gè)線段全在窗口外；線段部分在窗口外，部分在窗口內(nèi)。當(dāng)窗口采用凸多邊形時(shí)，任何一條直線只會(huì)至多有一段在窗口內(nèi)：當(dāng)一條直線的兩個(gè)端點(diǎn)全在窗口內(nèi)時(shí)，該直線整個(gè)在窗口內(nèi)當(dāng)一條直線的兩個(gè)端點(diǎn)，一個(gè)在窗口內(nèi)，一個(gè)在窗口外時(shí)，該直線部分在窗口內(nèi)，部分在窗口外當(dāng)一條直線的兩個(gè)端點(diǎn)全在窗口外時(shí)，該直線可能整個(gè)在窗口外，也可能部分在窗口內(nèi)

9、，部分在窗口外實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)。虛交點(diǎn)則是直線段與窗口矩形邊界延長(zhǎng)線或直線段的延長(zhǎng)線與窗口矩形邊界的交點(diǎn)。直線段和窗口邊界的交點(diǎn)基本思想：對(duì)每條直線段p1(x1,y1)p2(x2,y2)分三種情況處理：(1) 直線段完全可見，“簡(jiǎn)取”之。(2) 直線段完全不可見，“簡(jiǎn)棄”之。(3) 直線段既不滿足“簡(jiǎn)取”的條件，也不滿足“簡(jiǎn)棄”的條件，需要對(duì)直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。Cohen-Sutherland算法P1P2P5P6P3P4這是一個(gè)最早最流行的線段裁剪算法。該算法通過初始測(cè)試來(lái)減少要計(jì)算的交點(diǎn)數(shù)目從而加快線段裁剪算法的速度。編碼 每條線段的端點(diǎn)都賦以四位二進(jìn)

10、制碼D3D2D1D0 (上下右左) ，稱為區(qū)域碼（region code）,用來(lái)標(biāo)識(shí)出端點(diǎn)相對(duì)于裁剪矩形邊界的位置。編碼規(guī)則如下：若xxr，則D1=1，否則D1=0；若yyt，則D3=1，否則D3=0。 任何位賦值為1，代表端點(diǎn)落在相應(yīng)的位置上，否則該位為0。若端點(diǎn)在裁剪矩形內(nèi)，區(qū)域碼為0000。如果端點(diǎn)落在矩形的左下角，則區(qū)域碼為0101，其它類推。000010000100000110010101101000100110Cohen-Sutherland算法裁剪裁剪一條線段時(shí)，先求出端點(diǎn)p1和p2的編碼code1和code2，然后：(1)若code1|code2=0，對(duì)直線段應(yīng)簡(jiǎn)取之。(2)若

11、code1&code20，對(duì)直線段可簡(jiǎn)棄之。(3)若上述兩條件均不成立。則需求出直線段與窗口邊界的交點(diǎn)。在交點(diǎn)處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對(duì)另一段重復(fù)進(jìn)行上述處理，直到該線段完全被舍棄或者找到位于窗口內(nèi)的一段線段為止。000010000100000110010101101000100110Cohen-Sutherland算法求交：假定直線的端點(diǎn)坐標(biāo)為(x1,y1)和(x2,y2)左、右邊界交點(diǎn)的計(jì)算：下、上邊界交點(diǎn)的計(jì)算：計(jì)算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn)if(LEFT&code !=0)x=XL;y=y1+(y2-y1)*(XL-x1)/

12、(x2-x1);else if(RIGHT&code !=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code !=0) y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1); else if(TOP & code !=0) y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);Cohen-Sutherland算法算法的步驟：(1)輸入直線段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：yt、yb、xl和xr。(2)對(duì)p1、p2進(jìn)行編碼：點(diǎn)p1的編碼為code1，點(diǎn)p2的編碼為

13、code2。(3)若code1|code2=0，對(duì)直線段應(yīng)簡(jiǎn)取之，轉(zhuǎn)(6)；否則，若code1&code20，對(duì)直線段可簡(jiǎn)棄之，轉(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。(7)算法結(jié)束。Cohen-Sutherland算法中點(diǎn)分割算法 中點(diǎn)分割算法的基本思想是，與Cohe

14、n-Sutherland算法一樣對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系同樣分為三種情況，并對(duì)前兩種情況進(jìn)行同樣的處理。對(duì)于第三種情況，則簡(jiǎn)單地把線段等分為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直至每條線段完全在窗口內(nèi)或完全在窗口外為止。 Liang - Barsky算法 Liang（梁友棟）Barsky算法又稱為參數(shù)方程法。首先寫出端點(diǎn)（x1，y1）及（x2，y2）之間連線的參數(shù)方程如下：如果直線上的某點(diǎn)（x，y）處于（xwmin，ywmin）及（xwmax，ywmax）所定義的窗口之內(nèi)，則滿足以下條件: Liang - Barsky算法以上四個(gè)不等式可改寫為以下形式: 式中p及q定義為：若pk=0

15、，表示任何一條與窗口邊界平行的直線，此處k值表示取哪一個(gè)邊界(k=1,2,3及4,分別相應(yīng)于左、右、下及上邊界)。如果對(duì)某一k值，還滿足qk0，則此直線完全在邊界外，可不進(jìn)一步考慮：如果qk0，則此與邊界平行的直線在邊界內(nèi)。 Liang - Barsky算法如果pk0，則情況較復(fù)雜。此時(shí)我們可把直線按從（x1，y1）到（x2，y2）連線方向作為正向，將此直線無(wú)限延伸，同時(shí)把各窗口邊界也無(wú)限延伸（如圖所示）。然后分以下兩種情況討論：（1）當(dāng)pk0時(shí)，則是由窗口外發(fā)出的一條直線的無(wú)限延伸線進(jìn)入相應(yīng)窗口邊界的無(wú)限延伸線的內(nèi)部。（2）當(dāng)pk0時(shí)，情況相反。即直線的延伸線是由窗口邊界延伸線的內(nèi)部到外部。

16、 Liang - Barsky算法當(dāng)qk0時(shí)，我們可以用式u=qk/pk計(jì)算出一參數(shù)u，此u值應(yīng)于直線延伸線與窗口邊界k的延伸線的交點(diǎn)u1,u2的計(jì)算： u1=max(u11, u12), u2=min(u21, u22)EnterEnterLeaveLeaveEnterLeaveEnterLeaveu11u12u21u22Liang - Barsky算法判別準(zhǔn)則：u2u1，則此直線被裁剪，并可由u1及u2計(jì)算出裁剪點(diǎn)； u1u2，則此直線全部被排除。此裁剪算法所需的計(jì)算量較小。每修改一次u1或u2只需要一次除法，在u1及u2確定后，直線與窗口邊界的交點(diǎn)只需計(jì)算一次，但該算法只能應(yīng)用于矩形窗口

17、的情形。區(qū)域碼方法要多次重復(fù)計(jì)算直線與窗口邊界的交點(diǎn)，且每計(jì)算一次交點(diǎn)需要一次除法及一次乘法。 多邊形裁剪 在一個(gè)多邊形只畫出外部輪廓時(shí)，其每條邊可按上述直線裁剪算法處理，這樣，多邊形區(qū)域的裁剪就簡(jiǎn)化為一系列直線的裁剪，如圖所示。當(dāng)用多邊形邊界定義一個(gè)填充區(qū)時(shí)，要對(duì)此填充區(qū)裁剪時(shí)，就要對(duì)直線裁剪算法作某些修改，此時(shí)，最后產(chǎn)生的應(yīng)是由一個(gè)以上的閉合區(qū)定義的填充區(qū)邊界，如圖所示。 多邊形裁剪兩種常用的多邊形的裁剪算法：Sutherland-Hodgman算法Weiler-Atherton算法 Sutherland-Hodgman算法 基本思路：把被裁剪的多邊形依次與窗口的各邊界比較，裁剪去多余部分

18、。 此算法的執(zhí)行過程 ：Sutherland-Hodgman算法為了裁剪此多邊形，可把各頂點(diǎn)依次與窗口邊界比較。在窗口邊界內(nèi)的頂點(diǎn)保留下來(lái)，窗口邊界外的頂點(diǎn)則排除而不考慮，窗口邊界內(nèi)外兩點(diǎn)連線與窗口邊界的交點(diǎn)也應(yīng)保留下來(lái)。設(shè)相對(duì)于某一邊界處理的當(dāng)前點(diǎn)為P，處理的前一點(diǎn)為S，此時(shí)可能有四種情況.：當(dāng)所有頂點(diǎn)已相對(duì)于窗口左邊界處理完時(shí)，得到的新的多邊形頂點(diǎn)序列又相對(duì)于下一邊界進(jìn)行裁剪。 Sutherland-Hodgman算法在所裁剪的多邊形是一個(gè)凹多邊形時(shí)，最后裁剪生成的區(qū)域可能存在兩個(gè)或多個(gè)不相連接的多邊形。因?yàn)樯鲜鰠^(qū)域裁剪算法只產(chǎn)生一個(gè)頂點(diǎn)表，所以這些分開的區(qū)域可能被連接線連到一塊，如圖所示

19、。為了移去這些連接線，要對(duì)上述算法作修改，或采用更通用的裁剪算法。Weiler-Atherton算法 它可以用一個(gè)有內(nèi)孔的凹多邊形去裁剪另一個(gè)也有內(nèi)孔的凹多邊形，被裁剪的多邊形簡(jiǎn)稱為主多邊形裁剪區(qū)域稱為裁剪多邊形。交點(diǎn)：主多邊形和裁剪多邊形的邊界可能相交，也可能不相交。若它們相交，則交點(diǎn)必成對(duì)地出現(xiàn)，其中一個(gè)交點(diǎn)為主多邊形的邊進(jìn)入裁剪多邊形內(nèi)部時(shí)的交點(diǎn)，而另一交點(diǎn)為其離開時(shí)的交點(diǎn)。Weiler-Atherton算法例如：I1為進(jìn)入交點(diǎn) I2為離開交點(diǎn)Weiler-Atherton算法算法從進(jìn)入交點(diǎn)開始，沿主多邊形的外部邊界按照逆時(shí)針方向向前跟蹤，直至找到它與裁剪多邊形的一個(gè)交點(diǎn)為止。在交點(diǎn)處開始