1、第六章 二維變換及二維觀察提出問題：如何對二維圖形進行方向、尺寸和形狀方面的變換如何方便地實現在顯示設備上對二維圖形進行觀察：用戶程序圖形的用戶坐標在圖形顯示設備上輸出6.4 兩維觀察6.4.1 基本概念在計算機圖形學中，將在用戶坐標系中需要進行觀察和處理的一個坐標區域稱為窗口（Window）將窗口映射到顯示設備上的坐標區域稱為視區（Viewport）觀察變換（Viewing Transformation） 將窗口內的圖形在視區中顯示出來，必須經過將窗口到視區的變換（Window-Viewport Transformation）處理如果矩形窗口的矩形邊不一定平行于坐標軸，怎么辦？解決方法：引入

2、觀察坐標系如何消除于具體設備的相關性？解決方法：引入觀察坐標系 觀察坐標系(View Coordinate)和規格化設備坐標系(Normalized Device Coordinate) 觀察坐標系是依據窗口的方向和形狀在用戶坐標平面中定義的直角坐標系。規格化設備坐標系也是直角坐標系，它是將二維的設備坐標系規格化到（0.0，0.0）到（1.0，1.0）的坐標范圍內形成的。二維觀察流程：引入了觀察坐標系和規格化設備坐標系后，觀察變換分為如下圖所示的幾個步驟 變焦距效果 整體放縮效果 漫游效果6.4.2 用戶坐標系到觀察坐標系的變換 用戶坐標系到觀察坐標系的變換分由兩個變換步驟合成：1. 將觀察坐

3、標系原點移動到用戶坐標系原點2. 繞原點旋轉使兩坐標系重合6.4.2 用戶坐標系到觀察坐標系的變換用戶坐標系到觀察坐標系的變換分由兩個變換步驟合成：6.4.3 窗口到視區的變換要將窗口內的點（xw,yw）映射到相對應的視區內的點（xv,yv）需進行以下步驟：(1) 將窗口左下角點移至用戶系統系的坐標原點(2) 針對原點進行比例變換(3) 進行反平移6.4.3 窗口到視區的變換6.5 裁剪在二維觀察中，需要在觀察坐標系下對窗口進行裁剪，即只保留窗口內的那部分圖形，去掉窗口外的圖形。假設窗口是標準矩形，即邊與坐標軸平行的矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）

4、四條邊描述。xyowytwybwxlwxr窗口6.5.1 點的裁剪6.5 裁剪xyowytwybwxlwxr窗口6.5.2 直線段的裁剪假定直線段用p1(x1,y1)p2(x2,y2)表示。直線段和剪裁窗口的可能關系：完全落在窗口內完全落在窗口外與窗口邊界相交6.5 裁剪實交點是直線段與窗口矩形邊界的交點。虛交點則是直線段與窗口矩形邊界延長線或直線段的延長線與窗口矩形邊界的交點。6.5 裁剪1. Cohen-Sutherland算法基本思想：對每條直線段p1(x1,y1)p2(x2,y2)分三種情況處理：(1) 直線段完全可見，“簡取”之。(2) 直線段完全不可見，“簡棄”之。(3) 直線段既

5、不滿足“簡取”的條件，也不滿足“簡棄”的條件，需要對直線段按交點進行分段，分段后重復上述處理。6.5 裁剪編碼：對于任一端點(x,y)，根據其坐標所在的區域，賦予一個4位的二進制碼D3D2D1D0。編碼規則如下：若xwxr，則D1=1，否則D1=0；若ywyt，則D3=1，否則D3=0。1. Cohen-Sutherland算法裁剪一條線段時，先求出端點p1和p2的編碼code1和code2，然后： (1)若code1|code2=0，對直線段應簡取之。 (2)若code1&code20，對直線段可簡棄之。 (3)若上述兩條件均不成立。則需求出直線段與窗口邊界的交點。在交點處把線段一分為二，其

6、中必有一段完全在窗口外，可以棄之。再對另一段重復進行上述處理，直到該線段完全被舍棄或者找到位于窗口內的一段線段為止。1. Cohen-Sutherland算法求交：假定直線的端點坐標為(x1,y1)和(x2,y2)左、右邊界交點的計算：上、下邊界交點的計算：1. Cohen-Sutherland算法算法的步驟：(1)輸入直線段的兩端點坐標：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標：wyt、wyb、wxl和wxr。(2)對p1、p2進行編碼：點p1的編碼為code1，點p2的編碼為code2。(3)若code1|code2=0，對直線段應簡取之，轉(6)；否則，若code1

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

8、，對兩段重復上述測試處理，直至每條線段完全在窗口內或完全在窗口外。p1p2p1p2p3p2p1p4p4p3p1p2p1p4p1p4p4p6p6p3p1p4p4p6p1p4p4p6p6p7p7p3p1p4p4p6p6p7p1p4p4p6p1p4p1p5p5p4算法步驟：(1)輸入直線段的兩端點坐標：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標：wyt、wyb、wxl和wxr。(2)對p1、p2進行編碼：點p1的編碼為code1，點p2的編碼為code2。(3)若code1|code2=0，對直線段應簡取之，保留當前直線段的端點坐標，轉(5)；否則，若code1&code20，對

9、直線段可簡棄之，轉(5)；當上述兩條均不滿足時，進行步驟(4)。(4)求出直線段的中點M(x=round(x1+x2)/2), y=round(y1+y2)/2)，將p1M、p2M入棧。(5)當棧不空時，從棧中彈出一條直線段，取為p1p2，轉(2)進行處理。否則，繼續(6)。(6)當棧為空時，合并保留的直線段端點，得到窗口內的直線段p1p2。用直線掃描轉換算法畫出當前的直線段p1p2，算法結束。2.中點分割算法核心思想：通過二分逼近來確定直線段與窗口的交點。2.中點分割算法p1p2p1p3p1p3p1p4p4p3p1p5p5p4p4p6p6p3p6p7p7p3P3不在窗口內，將p3p2丟掉重新

10、構造算法步驟：(1)若code1|code2=0，對直線段應簡取之，結束；否則，若code1&code20，對直線段可簡棄之，結束；當這兩條均不滿足時，進行步驟(2)。(2)找出該直線段離窗口邊界最遠的點和該直線段的中點。判中點是否在窗口內：若中點不在窗口內，則把中點和離窗口邊界最遠點構成的線段丟掉，以線段上的另一點和該中點再構成線段求其中點；如中點在窗口內，則又以中點和最遠點構成線段，并求其中點，直到中點與窗口邊界的坐標值在規定的誤差范圍內相等，則該中點就是該線段落在窗口內的一個端點坐標。(3)如另一點在窗口內，則經(2)即確定了該線段在窗口內的部分。如另一點不在窗口內，則該點和所求出的在窗

11、口上的那一點構成一條線段，重復步驟(2)，即可求出落在窗口內的另一點。3. Liang-Barsky算法分析推導3. Liang-Barsky算法x=x1+u(x2-x1)y=y1+u(y2-y1)0 u 1任意直線段I（X1,Y1）J(X2,Y2)的參數方程：xyowytwybwxlwxr窗口給定裁剪窗口：3. Liang-Barsky算法wxl x1+u(x2-x1) wxrwyby1+u(y2-y1) wytu(x2-x1) x1 wxl 左邊界u(x1-x2) wxr x1 右邊界u(y2-y1) y1 wyb 下邊界u(y1-y2) wyt y1 上邊界p1 = x2-x1p2 =

12、x1-x2p3 = y2-y1p4 = y1-y2令：q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1upkqk k=1,2,3,4如果任一點（）在窗口內則： 取“=”時求得的u對應的是直線與窗口邊界的交點 1、2、3、4分別對應左、右、下、上邊界 U=0和1時分別對應直線的起點和中點xyowytwybwxlwxr窗口裁剪后的兩端點是哪些點？分析：裁剪的本質3. Liang-Barsky算法Uone=max(0,uk|pk0,uk|pk0,uk|pk0)I1J1對于I1J1P1、P4大于0 U在0、U1、U4取大者P2、P3小于0 U在1、U2、U3取小

13、者如果Uone Utwo取可求得兩端點左p1 = x2-x1 右p2 = x1-x2下p3 = y2-y1上p4 = y1-y2q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1假定PK不為03. Liang-Barsky算法左p1 = x2-x1 右p2 = x1-x2下p3 = y2-y1上p4 = y1-y2q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1如果Uone Utwo表明什么？P1、P3大于0 U在0、U1、U3取大者P2、P4小于0 U在1、U2、U4取小者Uone=max(0,uk|pk0,uk|

14、pk0,uk|pk0)特殊處理：PK為0左p1 = x2-x1 右p2 = x1-x2下p3 = y2-y1上p4 = y1-y2q1 = x1 wxlq2 = wxr x1q3 = y1 wybq4 = wyt y1算法步驟：(1)輸入直線段的兩端點坐標：(x1,y1)和(x2,y2)，以及窗口的四條邊界坐標：wyt、wyb、wxl和wxr。(2)若x=0，則p1=p2=0。此時進一步判斷是否滿足q10或q20且q20，則進一步計算u1和u2。算法轉(5)。(3)若y=0，則p3=p4=0。此時進一步判斷是否滿足q30或q40且q20，則進一步計算u1和u2。算法轉(5)。(4)若上述兩條均

15、不滿足，則有pk0（k=1,2,3,4）。此時計算u1和u2。(5)求得u1和u2后，進行判斷：若u1u2，則直線段在窗口外，算法轉(7)。若u1u2，利用直線的參數方程求得直線段在窗口內的兩端點坐標。(6)利用直線的掃描轉換算法繪制在窗口內的直線段。算法結束。4. 其它裁剪算法簡介Cohen-Sutherland算法、中點分割算法和Liang-Barsky算法Cyrus-Beck算法Nicholl-Lee-Nicholl算法6.5.3 多邊形的裁剪問題的提出：1. Sutherland-Hodgeman多邊形裁剪基本思想1. Sutherland-Hodgeman多邊形裁剪算法實施策略：為窗

16、口各邊界裁剪的多邊形存儲輸入與輸出頂點表。在窗口的一條裁剪邊界處理完所有頂點后，其輸出頂點表將用窗口的下一條邊界繼續裁剪。窗口的一條邊以及延長線構成的裁剪線把平面分為兩個區域，包含有窗口區域的一個域稱為可見側；不包含窗口區域的域為不可見側。沿著多邊形依次處理頂點會遇到四種情況：特點：輸入：ABCDEF輸入：AV1V4DEV3V22. Weiler-Atherton多邊形裁剪 假定按順時針方向處理頂點，且將用戶多邊形定義為Ps，窗口矩形為Pw。算法從Ps的任一點出發，跟蹤檢測Ps的每一條邊，當Ps與Pw相交時（實交點），按如下規則處理：(1)若是由不可見側進入可見側，則輸出可見直線段，轉(3)；(2)若是由可見側進入不可見側，則從當前交點開始，沿窗口邊界順時針檢測Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當前交點的另一交點，輸出可見直線段和由當前交點到另一交點之間窗口邊界上的線段，然后返回處理的當前交點；(3)沿著Ps處理各條邊，直到處理完Ps的每一條邊，回到起點為止。(1)若是由不可見側進入可見側，則輸出可見直線段，轉(3)；(2)若是由可見側進入不可見側，則從當前交點開始，沿窗口邊界順時針檢測Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當前交點的另一交點，