【文章內(nèi)容簡(jiǎn)介】 p0）。 對(duì)這些邊界計(jì)算 tk=qk/pk 。 tl=min{0,tk}。 取 te ≤ tl時(shí)的線段，否則完全落在裁剪窗口之外。 pk0,線段從外到內(nèi) Pk0,線段從內(nèi)到外 p1＝ x1x20》》 x2xLx1 p2＝ x2x10》》 x1xR x2 p3＝ y1y20》》 y2 yBy1 p4＝ y2y10》》 y1yT y2 60 3. 多邊形裁剪算法 多邊形裁剪 :等價(jià)于 直線段逐段裁剪的組合？ 問(wèn)題 ： 1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它，如何確定其邊界？ 61 2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小多邊形，如何 確定這些小多邊形的邊界？ 62 SutherlandHodgman算法 （ 逐邊裁剪算法 ） 算法基本思想 : 逐邊裁剪、兩次分解、流水線作業(yè) .首先將多邊形對(duì)于矩形窗口的裁剪 分解 為 多邊形關(guān)于窗口四邊所在直線的裁剪，其次，將多邊形對(duì)一條直線的裁剪分解為各邊對(duì)直線的裁剪。 亦稱 逐邊裁剪算法 . 63 考慮窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線 ,把平面分成：含窗口可見(jiàn)一側(cè)；不可見(jiàn)一側(cè)。 依序考慮多邊形的各條邊的兩端點(diǎn) S、 P。 它們與裁剪邊界有四種位置關(guān)系 :(1)S,P均在可見(jiàn)側(cè) (2)S可見(jiàn) ,P不可見(jiàn)（ 3） S,P均在不可見(jiàn)側(cè) (4)S不可見(jiàn) ,P可見(jiàn)。 64 每條線段端點(diǎn) S、 P與裁剪線比較后，可輸出 0至 2 個(gè)頂點(diǎn)： 情況（ 1）僅輸出終點(diǎn) P； 情況（ 2）輸出線段 SP 與裁剪線的交點(diǎn) I； 情況（ 3）輸出 0 個(gè)頂點(diǎn)； 情況（ 4）輸出線段 SP與裁剪線的交點(diǎn) I和終點(diǎn) P。 上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪，得到 一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過(guò)程的輸入。 65 66 67 裁剪結(jié)果的頂點(diǎn)構(gòu)成 ： 裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多 邊形的邊與裁剪邊的交點(diǎn)。 順序連接。 幾點(diǎn)說(shuō)明： 裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)。 可推廣到任意凸多邊形裁剪窗口 . 68 裁剪窗口可以為任意多邊形，規(guī)定 主多邊形 ：被裁剪多邊形，記為 A 裁剪多邊形 ：裁剪窗口，記為 B 多邊形頂點(diǎn)的排列順序： 使多邊形區(qū)域位于有向邊的左側(cè) 。 外環(huán)（逆時(shí)針）、內(nèi)環(huán)（順時(shí)針） 內(nèi)裁剪結(jié)果： A ∩ B 外裁剪結(jié)果： AB WeilerAtherton 算法 (雙邊裁剪算法） 69 裁剪結(jié)果區(qū)域的邊界由 A的部分邊界和 B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至 B的邊界，或由 B的邊界轉(zhuǎn)至 A的邊界。 70 兩類交點(diǎn) : 入點(diǎn) 沿主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi) 出點(diǎn) 沿主多邊形邊界由此離開(kāi)裁剪多邊形區(qū)域 特點(diǎn)： 入點(diǎn)和出點(diǎn)成對(duì)出現(xiàn)。 Weiler_Athenton裁剪算法（內(nèi)裁剪）步驟： 建立主多邊形和裁剪多邊形的頂點(diǎn)環(huán)表； 求主多邊形和裁剪多邊形的交點(diǎn)， 建立入點(diǎn)表和出點(diǎn)表； 并將這些交點(diǎn)按順序插入 兩多邊形的頂點(diǎn)環(huán)表 。在兩多邊形頂點(diǎn)環(huán)表中的相同交點(diǎn)間 建立雙向指針 ； 裁剪過(guò)程： 71 1)建立裁剪結(jié)果多邊形的頂點(diǎn)表 。 2)依次選取 入點(diǎn)表 中的一個(gè)入點(diǎn)，檢測(cè)其是否被處理過(guò)？是，取下一個(gè)入點(diǎn)，直至入點(diǎn)表中的入點(diǎn)全被處理過(guò)，結(jié)束； 3)沿主多邊形頂點(diǎn)環(huán)表正向搜索，將搜索到的主多邊形頂點(diǎn)記入裁剪結(jié)果多邊形的頂點(diǎn)表中，直至 下一個(gè)交點(diǎn) （出點(diǎn)）； 4）按該交點(diǎn)的雙向指針，搜索路徑由主多邊形轉(zhuǎn)入裁剪多邊形； 5）沿裁剪多邊形頂點(diǎn)環(huán)表正向搜索，將搜索到的裁剪多邊形頂點(diǎn)記入裁剪結(jié)果多邊形頂點(diǎn)表中，直至 下一個(gè)交點(diǎn) （入點(diǎn)）；檢測(cè)該入點(diǎn)是否與開(kāi)始入點(diǎn)相同？相同，轉(zhuǎn) 2）； 6） 按該交點(diǎn)的雙向指針，搜索路徑又由裁剪多邊形回到主多邊形；轉(zhuǎn) 3）。 72 建立主多邊形和裁剪多邊形的頂點(diǎn)環(huán)表； S1 S2 S3 S4 S5 S6 S7 S1 C1 C2 C3 C4 C1 S1 S2 S3 S4 S5 S6 S7 C1 C2 C3 C4 I1 I2 I3 I4 I5 I6 I7 I8 主 裁 73 S5 S1 S2 S3 S4 S6 S7 C1 C2 C3 C4 I1 I2 I3 I4 I5 I6 I7 I8 求主多邊形和裁剪多邊形的交點(diǎn)， 建立入點(diǎn)表和出點(diǎn)表； 并將這些交點(diǎn) 按順序插入 兩多邊形的頂點(diǎn)環(huán)表 。在 兩多邊形頂點(diǎn)環(huán)表中的相同交點(diǎn)間 建 立雙向指針 ； I2 I4 I6 I8 I1 I3 I5 I7 主 裁 入 出 S1 I2 I3 S2 I4 S3 I5 S4 I6 I7 S5 I8 S6 I1 S7 C1 I1 I2 C2 I3 I4 C3 I5 I6 C4 I7 I8 C1 74 S5 S1 S2 S3 S4 S6 S7 C1 C2 C3 C4 I1 I2 I3 I4 I5 I6 I7 I8 S1 I2 I3 S2 I4 S3 I5 S4 I6 I7 S5 I8 S6 I1 S7 S1 C1 I1 I2 C2 I3 I4 C3 I5 I6 C4 I7 I8 C1 主 裁 I2 I4 I6 I8 I1 I3 I5 I7 入 出 75 S1 S2 S3 S4 S5 S6 S7 S8 S9 C1 C2 C3 C4 I1 I2 I3 I4 I1 I3 I2 I4 入 出 S1 S2 S3 S4 S5 I1 S6 I2 S7 S8 S9 I3 I4 S1 C1 I3 C2 I2 C3 I1 C4 I4 C1 主 裁 76 出點(diǎn) ： I0,I2, I4, I6, I8, I10 入點(diǎn) ： I1,I3, I5, I7, I9, I11 例 1 77 78 79 例 2 A4 A1 A3 A2 A5 A6 A7 A8 W1 W2 W3 W4 W5 W6 I1 I2 I3 I4 I5 I6 入點(diǎn)表： I1， I3， I5 出點(diǎn)表： I2， I4， I6 80 主多邊形環(huán)表 ： W1， W2， W3， I2， W4， I5， I4， W5， W6， I3， I6， I1， W1 A1， I1， A2， I2， A3， A4， A1。A5， A6， I3， I4， A7， A8， I5， I6， A5 外邊界頂點(diǎn) 內(nèi)邊界頂點(diǎn) 裁剪多邊形環(huán)表 入點(diǎn)表： I1， I3， I5 出點(diǎn)表： I2， I4， I6 81 主多邊形環(huán)表 ： W1， W2， W3， I2， W4， I5， I4， W5， W6， I3， I6， I1， W1 A1， I1， A2， I2， A3， A4， A1。A5， A6， I3， I4， A7， A8， I5， I6， A5 外邊界頂點(diǎn) 內(nèi)邊界頂點(diǎn) 裁剪多邊形環(huán)表 入點(diǎn)表： I1， I3， I5 出點(diǎn)表： I2， I4， I6 82 交點(diǎn)的奇異情況處理 與裁剪多邊形邊重合的主多邊形的邊不參與求交點(diǎn)； 對(duì)于頂點(diǎn)落在裁剪多邊形的邊上的主多邊的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點(diǎn)算作交點(diǎn)；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點(diǎn)不看作交點(diǎn) 83 4. 字符裁剪 字符和文本部分在窗內(nèi)、部分在窗外時(shí)，就出現(xiàn)字符裁剪問(wèn)題。 STRING1 STRING2 STRING1 字符裁剪按三個(gè)精度進(jìn)行： 串精度、字符精度、以及筆畫(huà) \象素精度 。 串精度裁剪： 將包圍字串的外接矩形對(duì)窗口作裁剪。當(dāng) 字符串方框整個(gè)在窗口內(nèi)時(shí)予以顯示 ，否則不顯示。 84 字符精度裁剪： 將包圍字的外接矩形對(duì)窗口作裁剪，某個(gè)字符方框整個(gè)落在窗口內(nèi)予以顯示，否則不顯示。 STRING1 STRING2 STRING1 ING2 85 筆畫(huà) \象素精度裁剪： 將矢量字符的筆劃分解成直線段對(duì)窗口作裁剪；將點(diǎn)陣字符的像素相對(duì)窗口邊界作取舍。 STRING1 STRING2 STRING1 STRING2 86 3維觀察控制流程 1. 定義 把世界坐標(biāo)系描述的 3維景物對(duì)象最終變換到計(jì)算機(jī)圖形輸出設(shè)備坐標(biāo)系中，生成 3維景物的視圖 (像 )的整個(gè)過(guò)程。 87 2. 3維觀察過(guò)程 NDC DC WC VC 觀察方向 觀察平面 窗口 E xe ye ze O Xw Yw Zw 88 類比照像機(jī)拍攝景物的過(guò)程 拍攝過(guò)程 ?選景 ?取景 裁剪 ?對(duì)焦 —參 考點(diǎn) ?按快門(mén) 成像 移動(dòng)方式 ?移動(dòng)景物 ?移動(dòng)照相機(jī) 兩個(gè)坐標(biāo)系 89 簡(jiǎn)單的三維圖形顯示流程圖 90 3. 3維觀察控制流程 WC：描述 3D景物 WC 到VC變換 VC：定義觀察體、規(guī)范化裁剪空間 NVC NDC投影變換 NDC到 DC窗口視區(qū)變換 DC： 景物視圖顯示 NVC： 規(guī)范化裁剪空間裁剪 MC到WC變換 MC：模型描述 91 觀察坐標(biāo)系及其變換 1. 觀察坐標(biāo)系定義 觀察坐標(biāo)系 （ View Reference Coordinate或 VRC） 照相機(jī)所在的坐標(biāo)系 如何建立觀察坐標(biāo)系 坐標(biāo)原點(diǎn) 聚焦參考點(diǎn)在底片（投影平面）上的投影， 稱為 觀察參考點(diǎn) VRP（ View Reference Point ) n 軸 (N)照相機(jī)鏡頭方向（投影平面的法向 VPN） v 軸 (V)照相機(jī)向上的方向（代表觀察正向 VUP） u 軸 (U) nvu ??92 （觀察平面） VUP V（ Ye) U(Xe) N(Ze) VUP V VPN VRP u、 v、 n 分別表示 U、 V、 N的單位向量 93 為什么采用觀察坐標(biāo)系？ 攝像類比問(wèn)題：移動(dòng)舞臺(tái)還是移動(dòng)攝像機(jī)？ 移動(dòng)舞臺(tái)： 投 影（攝像）簡(jiǎn)單； 移動(dòng)難度大。 移動(dòng)攝像機(jī)：移動(dòng)容易；投影復(fù)雜。 采用了觀察坐標(biāo)系： 簡(jiǎn)化投影，加速投影變換 投影平面 n=0 投影中心 （ 0， 0， d) 94 2. WC 到 VC的變換 條件： VRC的坐標(biāo)原點(diǎn)（觀察參考點(diǎn)） VRP（ XR， YR， ZR）； 投影平面法向 VPN； 觀察正向 VUP ； （ 1）單位矢量法 [ u v n 1 ] = [ x y z 1 ] . TWtoV 95 ??????????????????],[],[],[zyxzyxzyxvvvunvuuuVPNV UPVPNV UPunnnVPNVPNn記為記為記為 TWtoV=TT .TR（ X， Y， Z） 1 0 0 0 0 1 0 0 0 0 1 0 XR YR ZR 1 = ux vx nx 0 uy vy ny 0 uz vz nz 0 0 0 0 1 96 （ 2）組合變換法 1） WC 原點(diǎn) O平移到視點(diǎn) E（ m， n， l） E X’ Y’ Z’ X Y Z O 1 0 0 0 0 1 0 0 0 0 1 0 m –n –l 1 T