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

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

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

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

5、部的區域是由用戶在世界坐標系中指定，而且通常是矩形區域，稱這個矩形區域為窗口（Window）指定或選取這樣的一個區域稱為開窗口。不是把整個屏幕都用來顯示窗口內的圖形，而是在屏幕上指定一個較小的矩形區域用于顯示窗口內的圖形，這個在屏幕上的矩形區域就稱為視區（Viewport），它是用規格化設備坐標系進行描述的。 窗口與視區窗口是在世界坐標系中指定待顯示內容的區域，視區是在顯示器（輸出設備）上顯示窗口內圖形的區域。 窗口與視區的關系 如下圖：窗口在圖形顯示中的應用 利用開窗口技術，可靈活地在屏幕上顯示一景物的不同部分 ：改變位置變焦：觀察細節放大、縮小尺寸掠過要觀察的物體多方位的觀察物體窗口到視區

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

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

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

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

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

11、code1&code20，對直線段可簡棄之。(3)若上述兩條件均不成立。則需求出直線段與窗口邊界的交點。在交點處把線段一分為二，其中必有一段完全在窗口外，可以棄之。再對另一段重復進行上述處理，直到該線段完全被舍棄或者找到位于窗口內的一段線段為止。000010000100000110010101101000100110Cohen-Sutherland算法求交：假定直線的端點坐標為(x1,y1)和(x2,y2)左、右邊界交點的計算：下、上邊界交點的計算：計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點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)輸入直線段的兩端點坐標：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標：yt、yb、xl和xr。(2)對p1、p2進行編碼：點p1的編碼為code1，點p2的編碼為

13、code2。(3)若code1|code2=0，對直線段應簡取之，轉(6)；否則，若code1&code20，對直線段可簡棄之，轉(7)；當上述兩條均不滿足時，進行步驟(4)。(4)確保p1在窗口外部：若p1在窗口內，則交換p1和p2的坐標值和編碼。(5)按左、右、下、上的順序求出直線段與窗口邊界的交點，并用該交點的坐標值替換p1的坐標值。也即在交點s處把線段一分為二，并去掉p1s這一段。考慮到p1是窗口外的一點，因此可以去掉p1s。轉(2)。(6)用直線掃描轉換算法畫出當前的直線段p1p2。(7)算法結束。Cohen-Sutherland算法中點分割算法 中點分割算法的基本思想是，與Cohe

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

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

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

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

18、。 此算法的執行過程 ：Sutherland-Hodgman算法為了裁剪此多邊形，可把各頂點依次與窗口邊界比較。在窗口邊界內的頂點保留下來，窗口邊界外的頂點則排除而不考慮，窗口邊界內外兩點連線與窗口邊界的交點也應保留下來。設相對于某一邊界處理的當前點為P，處理的前一點為S，此時可能有四種情況.：當所有頂點已相對于窗口左邊界處理完時，得到的新的多邊形頂點序列又相對于下一邊界進行裁剪。 Sutherland-Hodgman算法在所裁剪的多邊形是一個凹多邊形時，最后裁剪生成的區域可能存在兩個或多個不相連接的多邊形。因為上述區域裁剪算法只產生一個頂點表，所以這些分開的區域可能被連接線連到一塊，如圖所示

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