計(jì)算機(jī)圖形學(xué)之裁剪算法

基本圖形生成算法原理(四)第三章本章內(nèi)容一、點(diǎn)、直線段生成二、曲線的生成三、區(qū)域填充算法四、線寬與線型的處理五、字符及漢字生成六、二維圖形裁剪六、二維圖形裁剪圖形坐標(biāo)系統(tǒng)

點(diǎn)的裁剪直線線段的裁剪多邊形的裁剪字符的裁剪

幾何物體具有很多重要的性質(zhì)，如大小、形狀、位置、方向以及相互之間的空間關(guān)系等。為了描述、度量、分析上述特性，需要定義一個(gè)參考框架，該參考框架稱(chēng)為坐標(biāo)系統(tǒng)。

計(jì)算機(jī)圖形坐標(biāo)系統(tǒng)建立了圖形與數(shù)據(jù)之間的對(duì)應(yīng)聯(lián)系。（一）圖形坐標(biāo)系統(tǒng)設(shè)備坐標(biāo)系（Devicecoordinatesystem--DC）

與圖形設(shè)備相關(guān)聯(lián)的坐標(biāo)系叫設(shè)備坐標(biāo)系。世界坐標(biāo)系(用戶(hù)坐標(biāo)系）（WorldCoordinateSystem--WC）

世界坐標(biāo)系通常為直角坐標(biāo)系，一般由用戶(hù)選定，與機(jī)器設(shè)備無(wú)關(guān)。用戶(hù)在使用圖形系統(tǒng)創(chuàng)建或定義圖形時(shí)，都用自己熟悉的坐標(biāo)系，即用戶(hù)坐標(biāo)系來(lái)描述圖形數(shù)據(jù)。如常用的圖幅坐標(biāo)系、大地坐標(biāo)系等。1、常用坐標(biāo)系

局部坐標(biāo)系又稱(chēng)為符號(hào)坐標(biāo)系，是在定義圖形時(shí)，采用相對(duì)于物體的坐標(biāo)系，使圖形描述簡(jiǎn)單。規(guī)格化設(shè)備坐標(biāo)系(NormalDeviceCoordinatesSystem--NDC）

把各個(gè)設(shè)備坐標(biāo)系的數(shù)據(jù)經(jīng)過(guò)變換轉(zhuǎn)化為統(tǒng)一的數(shù)據(jù)范圍就得到規(guī)格化的設(shè)備坐標(biāo)系。對(duì)于具有多種圖形設(shè)備的圖形處理系統(tǒng)，采用該坐標(biāo)系是可以簡(jiǎn)化圖形數(shù)據(jù)的處理。局部坐標(biāo)系

(LocalCoordinatesSystem--LC）2、幾個(gè)基本概念用戶(hù)域----由用戶(hù)定義的描述圖形的整個(gè)自然空間。窗口區(qū)----由用戶(hù)指定的用戶(hù)域中的某個(gè)矩形區(qū)域。

用戶(hù)域是指用戶(hù)在世界坐標(biāo)系中定義的描述圖形區(qū)域，是連續(xù)無(wú)限的實(shí)數(shù)域；用戶(hù)在用戶(hù)域中指定的一個(gè)矩形范圍稱(chēng)為窗口區(qū)或窗口。窗口區(qū)小于或等于用戶(hù)域。屏幕域----設(shè)備輸出圖形的最大區(qū)域。視圖區(qū)----設(shè)定的小于或等于屏幕域的矩形區(qū)域。

屏幕域是在設(shè)備坐標(biāo)系中定義設(shè)備輸出圖形的最大區(qū)域，是有限的整數(shù)域；用戶(hù)在屏幕域中指定的一個(gè)矩形范圍稱(chēng)為視圖區(qū)或視口。視口小于或等于屏幕域，是用設(shè)備坐標(biāo)來(lái)定義的。

視圖區(qū)一般為矩形。在一個(gè)屏幕上，可以定義多個(gè)視圖區(qū)，作為不同的應(yīng)用。如在交互式圖形系統(tǒng)中，屏幕分為幾個(gè)區(qū)，可分別用于圖形顯示、放置菜單、工具條、提示信息、備注等。12341、主菜單區(qū)2、工具條3、圖形顯示區(qū)4、提示信息區(qū)（xw1，yw1）ywxwLwHW窗口坐標(biāo)Windowxvyv（xv1，yv1）LVHV視口坐標(biāo)Viewport變換公式：3、窗口到視口的變換圖形裁剪：

確定并提取出在指定區(qū)域（裁剪窗口）內(nèi)部的圖形對(duì)象（裁剪對(duì)象）的過(guò)程。即從數(shù)據(jù)集合中抽取部分?jǐn)?shù)據(jù)（子集）的過(guò)程。裁剪過(guò)程：

判斷圖形對(duì)象與裁剪窗口之間的關(guān)系并找出其位于窗口內(nèi)部（或外部）的部分。圖形裁剪的概念裁剪窗口：1、矩形窗口：由上（Top）、下（Bottom）、左（Left）、右（Right）四條邊界圍成。用其左下角點(diǎn)（XL，YB）和右上角點(diǎn)（XR，YT）來(lái)定義。2、多邊形窗口：由窗口多邊形的頂點(diǎn)坐標(biāo)串來(lái)定義。即

判斷點(diǎn)P（x，y）在裁剪窗口(矩形)內(nèi)（可見(jiàn)）、或在窗口外（不可見(jiàn)）。（二）點(diǎn)的裁剪判別式：≤≤≤≤（三）直線線段的裁剪直線段與窗口的位置關(guān)系：

完全可見(jiàn)完全不可見(jiàn)部分可見(jiàn)通過(guò)對(duì)線段端點(diǎn)的判別，確定線段與窗口的位置關(guān)系，并找出線段在窗口內(nèi)（或外）的部分。裁剪方法：

編碼裁剪法

中點(diǎn)裁剪法矢量裁剪法1、編碼裁剪法(Cohen-Sutherland)100110000001010100001010001001000110區(qū)域編碼：(四位代碼)從左到右各位依次表示上、下、右、左。裁剪步驟：第一步計(jì)算直線段兩端點(diǎn)的編碼C1、C2；第二步C1=C2=0000，線段可見(jiàn)，在窗口內(nèi)；第三步C1ΛC2≠0000，線段不可見(jiàn)，在窗口外；第四步否則，計(jì)算線段與窗口邊線的交點(diǎn)（求交），將其分為兩段，分別重復(fù)第一、二、三、四步重新判別，直至結(jié)束。100110000001010100001010001001000110求交：通過(guò)判斷直線段端點(diǎn)的編碼值（ClCtCrCb），確定與之相交的是哪條窗口邊所在直線？計(jì)算交點(diǎn)。特點(diǎn)：1）用編碼可快速判斷線段--完全可見(jiàn)和顯然不可見(jiàn)。2）特別適用兩種場(chǎng)合：大窗口場(chǎng)合；窗口特別小的場(chǎng)合。2、中點(diǎn)裁剪法

中點(diǎn)分割裁剪法是將Cohen-Sutherland算法中求線段與窗口邊界的交點(diǎn)的過(guò)程用折半查找（即求中點(diǎn)）的方法來(lái)代替。仍然采用對(duì)線段端點(diǎn)進(jìn)行編碼的方式判斷完全可見(jiàn)和顯然完全不可見(jiàn)的線段，對(duì)于與窗口有交點(diǎn)的線段，該算法分別求離兩個(gè)端點(diǎn)最近（或最遠(yuǎn)）的可見(jiàn)點(diǎn)。這兩個(gè)可見(jiàn)點(diǎn)之間的線段即是原線段的可見(jiàn)部分。只需解算不可見(jiàn)端點(diǎn)的最近的可見(jiàn)點(diǎn)。判斷中點(diǎn)Pm1如果落在（接近）窗口邊上，則確定該中點(diǎn)為最近可見(jiàn)點(diǎn)。裁剪結(jié)束。否則，P2P1P1P2（一）直線段P1P2的一個(gè)端點(diǎn)可見(jiàn)，另一個(gè)端點(diǎn)不可見(jiàn)。計(jì)算P1P2的最近可見(jiàn)點(diǎn)Pma和Pmb

：1）設(shè)P1不可見(jiàn)，計(jì)算P1P2的中點(diǎn)Pm1。如果Pm1可見(jiàn)，以Pm1取代P2，返回到1）計(jì)算P1Pm1的中點(diǎn)Pm2，判斷Pm22）判斷Pm1是否可見(jiàn)：如果Pm1不可見(jiàn)，以Pm1取代P1，返回到1）計(jì)算Pm1P2的中點(diǎn)Pm2，判斷Pm2Yes,則P1P2為不可見(jiàn)線段，結(jié)束。No,將兩線段中為非顯然不可見(jiàn)的線段取代

P1P2，并返回到1）重新判別計(jì)算。P2P1P1P2（二）直線段P1P2的兩個(gè)端點(diǎn)都不可見(jiàn)。計(jì)算P1P2的最近可見(jiàn)點(diǎn)Pma和Pmb

：1）計(jì)算P1P2的中點(diǎn)Pm。如果Pm可見(jiàn)，將P1P2分為兩段：P1Pm和PmP2，分別按（一）中的方法解算出各自的最近可見(jiàn)點(diǎn)。2）判斷Pm是否可見(jiàn)：如果Pm不可見(jiàn)，判斷線段P1Pm和PmP2是否為顯然不可見(jiàn)。兩種線段裁剪算法的比較

Cohen-Sutherland算法是最早的、使用最廣泛的線段裁剪算法之一。在裁剪窗口很大，大部分線段完全可見(jiàn)，或裁剪窗口很小，大部分線段完全不可見(jiàn)的情況下，該算法特別有效；在一般情況下，該算法有時(shí)要做不必要的求交運(yùn)算，因而效率不是太高.

中點(diǎn)分割裁剪算法是Cohen-Sutherland算法的硬件版本。該算法只需要做加法和移位，不要做乘除法，用硬件實(shí)現(xiàn)既簡(jiǎn)單又有效。

平面多邊形是由若干直線段圍成的平面封閉圖形。裁剪的結(jié)果，應(yīng)仍是封閉的圖形。（四）多邊形的裁剪平面多邊形和窗口之間的位置關(guān)系：

依次用窗口的四條邊框所在的直線對(duì)多邊形進(jìn)行分步裁剪。逐邊裁剪算法（Sutherland-Hodgman）將多邊形表示為頂點(diǎn)表，即｛P1，P2，……

Pn-1，Pn

｝,并生成邊表P1P2，P2P3，……Pn-1Pn，PnP1。(2)用窗口邊裁剪原多邊形，生成中間多邊形(3)對(duì)中間多邊形重復(fù)步驟(2)，直至被窗口所有邊裁剪完為止關(guān)鍵：根據(jù)多邊形的邊表，逐次對(duì)每一段邊與裁剪線(窗口邊直線)比較，判別輸入頂點(diǎn)的個(gè)數(shù)和坐標(biāo)，并聯(lián)結(jié)成封閉多邊形。多邊形邊與裁剪線相對(duì)位置的四種情況與處理方法：(1)位于可見(jiàn)一側(cè)：輸出終點(diǎn)作為新多邊形頂點(diǎn)(2)位于不可見(jiàn)一側(cè)：不輸出(3)由可見(jiàn)到不可見(jiàn)：輸出與裁剪線的交點(diǎn)(4)由不可見(jiàn)到可見(jiàn)：輸出與裁剪線的交點(diǎn)及終點(diǎn)可見(jiàn)側(cè)不可見(jiàn)側(cè)1423P1P2P3P4P5P6P7P8P’1P2P3P4P5P6P7P8P9P’1P2P’3P4P