計(jì)算機(jī)圖形學(xué) 第六章 二維變換及二維觀察-2

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

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

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

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

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

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

7、&code20，對直線段可簡棄之，轉(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é)束。1. Cohen-Sutherland算法例如： 特點(diǎn)：1. Cohen-Sutherland算法2.中點(diǎn)分割算法基本思想： 當(dāng)對直線段不能簡取也不能簡棄時(shí)，簡單地把線段等分為二段

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

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

10、構(gòu)造算法步驟：(1)若code1|code2=0，對直線段應(yīng)簡取之，結(jié)束；否則，若code1&code20，對直線段可簡棄之，結(jié)束；當(dāng)這兩條均不滿足時(shí)，進(jìn)行步驟(2)。(2)找出該直線段離窗口邊界最遠(yuǎn)的點(diǎn)和該直線段的中點(diǎn)。判中點(diǎn)是否在窗口內(nèi)：若中點(diǎn)不在窗口內(nèi)，則把中點(diǎn)和離窗口邊界最遠(yuǎn)點(diǎn)構(gòu)成的線段丟掉，以線段上的另一點(diǎn)和該中點(diǎn)再構(gòu)成線段求其中點(diǎn)；如中點(diǎn)在窗口內(nèi)，則又以中點(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)和所求出的在窗

11、口上的那一點(diǎn)構(gòu)成一條線段，重復(fù)步驟(2)，即可求出落在窗口內(nèi)的另一點(diǎn)。3. Liang-Barsky算法分析推導(dǎo)3. Liang-Barsky算法x=x1+u(x2-x1)y=y1+u(y2-y1)0 u 1任意直線段I（X1,Y1）J(X2,Y2)的參數(shù)方程：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如果任一點(diǎn)（）在窗口內(nèi)則： 取“=”時(shí)求得的u對應(yīng)的是直線與窗口邊界的交點(diǎn) 1、2、3、4分別對應(yīng)左、右、下、上邊界 U=0和1時(shí)分別對應(yīng)直線的起點(diǎn)和中點(diǎn)xyowytwybwxlwxr窗口裁剪后的兩端點(diǎn)是哪些點(diǎn)？分析：裁剪的本質(zhì)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取可求得兩端點(diǎn)左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)輸入直線段的兩端點(diǎn)坐標(biāo)：(x1,y1)和(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。(2)若x=0，則p1=p2=0。此時(shí)進(jìn)一步判斷是否滿足q10或q20且q20，則進(jìn)一步計(jì)算u1和u2。算法轉(zhuǎn)(5)。(3)若y=0，則p3=p4=0。此時(shí)進(jìn)一步判斷是否滿足q30或q40且q20，則進(jìn)一步計(jì)算u1和u2。算法轉(zhuǎn)(5)。(4)若上述兩條均

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

16、口各邊界裁剪的多邊形存儲輸入與輸出頂點(diǎn)表。在窗口的一條裁剪邊界處理完所有頂點(diǎn)后，其輸出頂點(diǎn)表將用窗口的下一條邊界繼續(xù)裁剪。窗口的一條邊以及延長線構(gòu)成的裁剪線把平面分為兩個(gè)區(qū)域，包含有窗口區(qū)域的一個(gè)域稱為可見側(cè)；不包含窗口區(qū)域的域?yàn)椴豢梢妭?cè)。沿著多邊形依次處理頂點(diǎn)會遇到四種情況：特點(diǎn)：輸入：ABCDEF輸入：AV1V4DEV3V22. Weiler-Atherton多邊形裁剪 假定按順時(shí)針方向處理頂點(diǎn)，且將用戶多邊形定義為Ps，窗口矩形為Pw。算法從Ps的任一點(diǎn)出發(fā)，跟蹤檢測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í)針檢測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)為止。(1)若是由不可見側(cè)進(jìn)入可見側(cè)，則輸出可見直線段，轉(zhuǎn)(3)；(2)若是由可見側(cè)進(jìn)入不可見側(cè)，則從當(dāng)前交點(diǎn)開始，沿窗口邊界順時(shí)針檢測Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當(dāng)前交點(diǎn)的另一交點(diǎn)，