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

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

點的裁剪直線線段的裁剪多邊形的裁剪字符的裁剪

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

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

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

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

局部坐標系又稱為符號坐標系，是在定義圖形時，采用相對于物體的坐標系，使圖形描述簡單。規(guī)格化設(shè)備坐標系(NormalDeviceCoordinatesSystem--NDC）

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

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

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

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

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

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

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

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

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

編碼裁剪法

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

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

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

P1P2，并返回到1）重新判別計算。P2P1P1P2（二）直線段P1P2的兩個端點都不可見。計算P1P2的最近可見點Pma和Pmb

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

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

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

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

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

Pn-1，Pn

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