計(jì)算機(jī)圖形學(xué)第四章課件

1、計(jì)算機(jī)圖形學(xué)第四章第四章第四章 窗口與裁剪技術(shù)窗口與裁剪技術(shù)教學(xué)目的：教學(xué)目的： 通過本章的學(xué)習(xí)，應(yīng)讓學(xué)生掌通過本章的學(xué)習(xí)，應(yīng)讓學(xué)生掌握窗口與視區(qū)的概念以及它們之間的轉(zhuǎn)握窗口與視區(qū)的概念以及它們之間的轉(zhuǎn)換過程；熟練掌握二維直線段的裁剪算換過程；熟練掌握二維直線段的裁剪算法及多邊形的裁剪。法及多邊形的裁剪。本章重點(diǎn)：本章重點(diǎn)： 二維直線段的裁剪算法及多邊形的裁二維直線段的裁剪算法及多邊形的裁剪剪本章難點(diǎn)：本章難點(diǎn)： 逐次多邊形裁剪算法，中點(diǎn)再分直線逐次多邊形裁剪算法，中點(diǎn)再分直線法法計(jì)算機(jī)圖形學(xué)第四章內(nèi)內(nèi) 容容4.1 4.1 坐標(biāo)系統(tǒng)坐標(biāo)系統(tǒng)4.2 4.2 窗口窗口- -視區(qū)變換視區(qū)變換4.3

2、4.3 圖形裁剪圖形裁剪 直線段裁剪直線段裁剪 多邊形裁剪多邊形裁剪 字符裁剪字符裁剪計(jì)算機(jī)圖形學(xué)第四章4.14.1 坐標(biāo)系統(tǒng)坐標(biāo)系統(tǒng)在計(jì)算機(jī)圖形學(xué)中，常使用以下幾種直角坐標(biāo)系：在計(jì)算機(jī)圖形學(xué)中，常使用以下幾種直角坐標(biāo)系：一、世界坐標(biāo)系一、世界坐標(biāo)系wc wc （world coordinateworld coordinate）（用戶坐標(biāo)系）（用戶坐標(biāo)系）圖形學(xué)中常用的坐標(biāo)系統(tǒng)，是右手三維直角坐標(biāo)系圖形學(xué)中常用的坐標(biāo)系統(tǒng)，是右手三維直角坐標(biāo)系 ，長(zhǎng)，長(zhǎng)度單位由用戶自定，取值范圍是整個(gè)實(shí)數(shù)域度單位由用戶自定，取值范圍是整個(gè)實(shí)數(shù)域二、目標(biāo)系二、目標(biāo)系ecec（eye coordinateeye c

3、oordinate）（觀察坐標(biāo)法）（觀察坐標(biāo)法）是左手三維直角坐標(biāo)系是左手三維直角坐標(biāo)系ecec三、設(shè)備坐標(biāo)系三、設(shè)備坐標(biāo)系dc dc （device coordinatedevice coordinate）是關(guān)于圖形設(shè)備用的坐標(biāo)，一般都采用二維直角坐標(biāo)系，是關(guān)于圖形設(shè)備用的坐標(biāo)，一般都采用二維直角坐標(biāo)系，但坐標(biāo)原點(diǎn)及坐標(biāo)軸方向都因具體設(shè)備的不同而不同。取值范但坐標(biāo)原點(diǎn)及坐標(biāo)軸方向都因具體設(shè)備的不同而不同。取值范圍是整數(shù)的有限區(qū)域。圍是整數(shù)的有限區(qū)域。 四、規(guī)格化設(shè)備坐標(biāo)系四、規(guī)格化設(shè)備坐標(biāo)系ndcndc（normalized device coordinatenormalized devic

4、e coordinate）是一種虛擬的坐標(biāo)系統(tǒng)，它與具體的設(shè)備無關(guān)，通過它可是一種虛擬的坐標(biāo)系統(tǒng)，它與具體的設(shè)備無關(guān)，通過它可以把以把wcwc與與dcdc聯(lián)系起來，聯(lián)系起來，ndcndc的坐標(biāo)值在的坐標(biāo)值在0101之間。之間。計(jì)算機(jī)圖形學(xué)第四章三種坐標(biāo)系間的關(guān)系三種坐標(biāo)系間的關(guān)系dcdcdcpn（xn，yn）ndc11wcpw（xw，yw）hwww（wxl，wyb）計(jì)算機(jī)圖形學(xué)第四章坐標(biāo)系統(tǒng)坐標(biāo)系統(tǒng)通過通過ndcndc，可以建立兩種坐標(biāo)系之間一一對(duì)應(yīng)的相互關(guān)系，可以建立兩種坐標(biāo)系之間一一對(duì)應(yīng)的相互關(guān)系，使用戶在用使用戶在用wcwc描述物體圖形時(shí)，能在具體的物理圖形設(shè)備上正描述物體圖形時(shí)，能在具

5、體的物理圖形設(shè)備上正取輸出。這兩種坐標(biāo)系的轉(zhuǎn)換分別為：取輸出。這兩種坐標(biāo)系的轉(zhuǎn)換分別為：（1 1）wcwc到到dncdnc的轉(zhuǎn)換的轉(zhuǎn)換如上圖，從如上圖，從wcwc中一點(diǎn)中一點(diǎn)p pw w（x xw w，y yw w）變換到）變換到ndcndc中一點(diǎn)中一點(diǎn)pnpn（xnxn，ynyn）的關(guān)系為）的關(guān)系為xn=(xw-wxl)/wwxn=(xw-wxl)/wwyn=(yw-wyb)/hwyn=(yw-wyb)/hw（2 2）ndcndc到到dcdc的轉(zhuǎn)換的轉(zhuǎn)換實(shí)際上，對(duì)每一個(gè)具體設(shè)備而言，這兩種坐標(biāo)系的坐標(biāo)值實(shí)際上，對(duì)每一個(gè)具體設(shè)備而言，這兩種坐標(biāo)系的坐標(biāo)值也僅差一個(gè)比例因子，把前者的坐標(biāo)值乘上這

6、一比例因子即可也僅差一個(gè)比例因子，把前者的坐標(biāo)值乘上這一比例因子即可得后者的坐標(biāo)值。得后者的坐標(biāo)值。計(jì)算機(jī)圖形學(xué)第四章4.24.2 窗口視區(qū)變換窗口視區(qū)變換一、用戶域和窗口一、用戶域和窗口用戶域是指整個(gè)自然空間，實(shí)數(shù)域，連續(xù)的，無用戶域是指整個(gè)自然空間，實(shí)數(shù)域，連續(xù)的，無限的。限的。窗口是其中的一部分（子集）一般為矩形。窗口是其中的一部分（子集）一般為矩形。二、屏幕域和視圖區(qū)屏幕域和視圖區(qū)：屏幕域是設(shè)備輸出的最大區(qū)域，整數(shù)域，有限的。屏幕域是設(shè)備輸出的最大區(qū)域，整數(shù)域，有限的。視區(qū)只是其中的一部分。視區(qū)只是其中的一部分。三、窗口與視區(qū)：三、窗口與視區(qū)：視區(qū)是窗口影射到顯示設(shè)備上的（矩形）區(qū)域。

7、視區(qū)是窗口影射到顯示設(shè)備上的（矩形）區(qū)域。計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換四、窗口四、窗口- -視區(qū)的變換視區(qū)的變換：1 1、變換的意義：、變換的意義：用戶在用戶在wcwc中繪圖時(shí)，可以選擇不同的度量單位，中繪圖時(shí)，可以選擇不同的度量單位，而顯示屏上的圖形是以屏幕為坐標(biāo)系，使用整數(shù)而顯示屏上的圖形是以屏幕為坐標(biāo)系，使用整數(shù)坐標(biāo)的象素來度量的。對(duì)某種顯示器來說，顯示坐標(biāo)的象素來度量的。對(duì)某種顯示器來說，顯示數(shù)據(jù)的范圍是固定的。所以，在將窗口的原始圖數(shù)據(jù)的范圍是固定的。所以，在將窗口的原始圖形變換到視區(qū)顯示時(shí)，必須進(jìn)行此變換。形變換到視區(qū)顯示時(shí)，必須進(jìn)行此變換。 計(jì)算機(jī)圖形學(xué)第四章窗口視

8、區(qū)變換窗口視區(qū)變換2 2、變換公式：、變換公式： 計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換變換應(yīng)在保持一定比例關(guān)系的前提下進(jìn)行，即：變換應(yīng)在保持一定比例關(guān)系的前提下進(jìn)行，即：整理，化簡(jiǎn)得：整理，化簡(jiǎn)得： ybytybsybytybwxlxrxlsxlxrxlwvvvywwwyvvvxwwwx dcyybaxxwsws 計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換其中：其中：ybytyxlxrxybytyxlxrxyyybybyyxxxlxlxxvvvvvvwwswwssvwvdsvcsvwvbsva,a,c分別反映了視區(qū)和窗口在x和y方向上的伸縮比c,d則分別反映了定位點(diǎn)在x和y方向上的偏移量

9、計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換五、窗口五、窗口-ndc-視區(qū)變換視區(qū)變換 系統(tǒng)有多系統(tǒng)有多個(gè)輸出設(shè)個(gè)輸出設(shè)備時(shí)采用備時(shí)采用計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換考慮到輸出設(shè)備的分辨率，為了使圖形程序設(shè)計(jì)考慮到輸出設(shè)備的分辨率，為了使圖形程序設(shè)計(jì)與設(shè)備無關(guān)，將視區(qū)設(shè)置在規(guī)格化設(shè)備坐標(biāo)中，用戶與設(shè)備無關(guān)，將視區(qū)設(shè)置在規(guī)格化設(shè)備坐標(biāo)中，用戶設(shè)計(jì)的圖形首先變換到規(guī)格化設(shè)備坐標(biāo)上，它能適應(yīng)設(shè)計(jì)的圖形首先變換到規(guī)格化設(shè)備坐標(biāo)上，它能適應(yīng)任何一種具體的圖形輸出設(shè)備。任何一種具體的圖形輸出設(shè)備。變換公式為：變換公式為： x xs s= =（x xw w-w-wxlxl）/s/sx x y ys

10、 s= =（y yw w-w-wybyb）/s/sy y（因?yàn)椋海ㄒ驗(yàn)椋簐 vx x=v=vy y=1=1， v vxlxl=v=vybyb=0=0）然后，根據(jù)物理輸出設(shè)備坐標(biāo)或具體顯示器屏幕然后，根據(jù)物理輸出設(shè)備坐標(biāo)或具體顯示器屏幕尺寸和分辨率，再將規(guī)格化設(shè)備坐標(biāo)變換到具體視區(qū)尺寸和分辨率，再將規(guī)格化設(shè)備坐標(biāo)變換到具體視區(qū)上，顯示輸出圖形（教材上，顯示輸出圖形（教材p364p364）計(jì)算機(jī)圖形學(xué)第四章窗口視區(qū)變換窗口視區(qū)變換六、窗口六、窗口- -視區(qū)的變換過程：視區(qū)的變換過程：用戶坐標(biāo)系統(tǒng)用戶坐標(biāo)系統(tǒng) 相對(duì)窗口相對(duì)窗口 將窗口內(nèi)圖形將窗口內(nèi)圖形 將規(guī)格化將規(guī)格化 輸出輸出下設(shè)計(jì)的圖形下設(shè)計(jì)的

11、圖形 作裁剪作裁剪 變換成規(guī)格化變換成規(guī)格化 坐標(biāo)變換坐標(biāo)變換 圖形圖形 設(shè)備坐標(biāo)設(shè)備坐標(biāo) 成設(shè)備坐標(biāo)成設(shè)備坐標(biāo) 開窗變換開窗變換 視區(qū)變換視區(qū)變換 窗口到視區(qū)的映射結(jié)果，視區(qū)中顯示的只是窗口內(nèi)部的那窗口到視區(qū)的映射結(jié)果，視區(qū)中顯示的只是窗口內(nèi)部的那部分圖景，窗口外的所有部分都被去掉了。把位于給定區(qū)域外部分圖景，窗口外的所有部分都被去掉了。把位于給定區(qū)域外的所有圖形部分全部刪除的過程稱為裁剪。窗口變換的過程通的所有圖形部分全部刪除的過程稱為裁剪。窗口變換的過程通常是先對(duì)窗口進(jìn)行裁剪，然后把窗口內(nèi)部映象到視區(qū)中。常是先對(duì)窗口進(jìn)行裁剪，然后把窗口內(nèi)部映象到視區(qū)中。計(jì)算機(jī)圖形學(xué)第四章4.34.3 圖

12、形裁剪圖形裁剪一、一、 裁剪的基本概念裁剪的基本概念二、二、 點(diǎn)的裁剪點(diǎn)的裁剪三、三、 線段裁剪線段裁剪cohen-sutherlandcohen-sutherland算法；算法；中點(diǎn)算法中點(diǎn)算法參數(shù)化裁剪算法（略）參數(shù)化裁剪算法（略）四、四、 多邊形裁剪多邊形裁剪sutlerland_hodgmansutlerland_hodgman算法算法五、五、 字符裁剪字符裁剪計(jì)算機(jī)圖形學(xué)第四章一、一、 裁剪的基本概念裁剪的基本概念 裁剪的目的裁剪的目的 判斷圖形元素是否落在裁判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于剪窗口之內(nèi)并找出其位于內(nèi)部的部分內(nèi)部的部分 裁剪的處理的基礎(chǔ)裁剪的處理的基礎(chǔ) 圖元

13、關(guān)于窗口內(nèi)外關(guān)系的圖元關(guān)于窗口內(nèi)外關(guān)系的判別判別 圖元與窗口的求交圖元與窗口的求交 假定條件假定條件 矩形裁剪窗口：矩形裁剪窗口：wwxlxl , w , wxrxr &w &wybyb , w , wytyt 計(jì)算機(jī)圖形學(xué)第四章二、二、 點(diǎn)的裁剪點(diǎn)的裁剪點(diǎn)點(diǎn)(x, y)(x, y)在窗口內(nèi)的充分必要條件是：在窗口內(nèi)的充分必要條件是： w wxlxlxwxwxrxr w wybybywywytyt問題：對(duì)于任何多邊形窗口，如何判別？問題：對(duì)于任何多邊形窗口，如何判別？計(jì)算機(jī)圖形學(xué)第四章三、線段裁剪三、線段裁剪 假定條件假定條件 待裁剪線段：待裁剪線段： 裁剪的任務(wù)裁剪的任務(wù) 要求確定這條直線是

14、完全可見、部要求確定這條直線是完全可見、部分可見或完全不可見分可見或完全不可見 若完全可見：輸出其已知的兩個(gè)端點(diǎn)坐標(biāo)，若完全可見：輸出其已知的兩個(gè)端點(diǎn)坐標(biāo)，并顯示該直線并顯示該直線 若部分可見：輸出可見部分的兩個(gè)端點(diǎn)，若部分可見：輸出可見部分的兩個(gè)端點(diǎn)，并顯示該線段并顯示該線段 若完全不可見：則不顯示若完全不可見：則不顯示),(),(111000yxpyxp計(jì)算機(jī)圖形學(xué)第四章待裁剪線段和窗口的關(guān)系待裁剪線段和窗口的關(guān)系 要判斷一條直線的可見性，必須根據(jù)直要判斷一條直線的可見性，必須根據(jù)直線的兩個(gè)端點(diǎn)與窗口的相對(duì)位置來進(jìn)行判斷。線的兩個(gè)端點(diǎn)與窗口的相對(duì)位置來進(jìn)行判斷。計(jì)算機(jī)圖形學(xué)第四章待裁剪線段

15、和窗口的關(guān)系待裁剪線段和窗口的關(guān)系直線相對(duì)于窗口位置的五種情況：直線相對(duì)于窗口位置的五種情況： 1 1）兩端點(diǎn)均在窗口內(nèi)）兩端點(diǎn)均在窗口內(nèi)直線直線abab（應(yīng)全保留）（應(yīng)全保留） 2 2）兩端點(diǎn)均在窗口同側(cè)）兩端點(diǎn)均在窗口同側(cè)直線直線efef（全舍棄）（全舍棄） 3 3）一個(gè)端點(diǎn)在窗口內(nèi)，一個(gè)在窗口外）一個(gè)端點(diǎn)在窗口內(nèi)，一個(gè)在窗口外直線直線dcdc（分段討論）（分段討論） 4 4）直線貫穿窗口與窗口的兩條邊線相交）直線貫穿窗口與窗口的兩條邊線相交直線直線ghgh（分段討論）（分段討論） 5 5）直線與窗口邊線的交點(diǎn)均在窗口外）直線與窗口邊線的交點(diǎn)均在窗口外直線直線ijij（分段討論）（分段討論

16、）為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：(一）快速判斷情形1），2）；(二) 設(shè)法減少情形3）5）求交次數(shù)和每次求交時(shí)所需的計(jì)算量。計(jì)算機(jī)圖形學(xué)第四章（一）（一）cohen-sutherland cohen-sutherland 算算法法 該算法是用區(qū)域檢查的辦法有效的該算法是用區(qū)域檢查的辦法有效的識(shí)別可以直接接受或直接舍棄的線段，只有識(shí)別可以直接接受或直接舍棄的線段，只有不屬于這兩種情況的線段才需要計(jì)算交點(diǎn)。不屬于這兩種情況的線段才需要計(jì)算交點(diǎn)。 特點(diǎn)：用編碼方法可快速判斷線段特點(diǎn)：用編碼方法可快速判斷線段-完完全可見和顯然不可見。全可見和顯然不可見。 特別適用二種場(chǎng)合：特別適用二種場(chǎng)合：大窗口場(chǎng)合

17、和窗口特別小的場(chǎng)合大窗口場(chǎng)合和窗口特別小的場(chǎng)合( (如如, , 光標(biāo)拾光標(biāo)拾取圖形時(shí)取圖形時(shí), ,光標(biāo)看作小的裁剪窗口。）光標(biāo)看作小的裁剪窗口。）( (編碼算法編碼算法) )計(jì)算機(jī)圖形學(xué)第四章算法原理算法原理 對(duì)于每條線段對(duì)于每條線段p p1 1p p2 2分為三種情況處理：分為三種情況處理： 若若p p1 1，p p2 2完全在窗口內(nèi)，則完全在窗口內(nèi)，則“取取”之之 ，即，即 線段完全可見，否則進(jìn)入線段完全可見，否則進(jìn)入2 2）；）；若若p p1 1，p p2 2明顯在窗口外，則明顯在窗口外，則 “ “棄棄”之，即線之，即線段顯然不可見，裁剪結(jié)束，否則進(jìn)行段顯然不可見，裁剪結(jié)束，否則進(jìn)行3

18、3）；）；1)1) 若不滿足上述兩條件，則求線段與窗口邊延若不滿足上述兩條件，則求線段與窗口邊延長(zhǎng)線的交點(diǎn)，把線段分為兩段，其中一段顯長(zhǎng)線的交點(diǎn)，把線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新重復(fù)然不可見，丟棄。對(duì)余下的另一段重新重復(fù)上述處理直到全保留或全舍棄。上述處理直到全保留或全舍棄。裁剪過程是遞歸的裁剪過程是遞歸的計(jì)算機(jī)圖形學(xué)第四章具體實(shí)現(xiàn)具體實(shí)現(xiàn)編碼方法編碼方法 為了使計(jì)算機(jī)能夠快速的判斷一條線段與為了使計(jì)算機(jī)能夠快速的判斷一條線段與窗口何種關(guān)系，采用編碼方法：由窗口四條邊所在窗口何種關(guān)系，采用編碼方法：由窗口四條邊所在直線把二維平面分成直線把二維平面分成9 9個(gè)區(qū)域，每

19、個(gè)區(qū)域賦予一個(gè)個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，四位編碼，c ct tc cb bc cr rc cl l （上下右左）（上下右左）elseyyct0max1當(dāng)elseyycb0min1當(dāng)elsexxcr0max1當(dāng)elsexxcl0min1當(dāng)計(jì)算機(jī)圖形學(xué)第四章具體實(shí)現(xiàn)具體實(shí)現(xiàn)算法步驟算法步驟算法步驟：算法步驟： 裁剪一條線段時(shí)，先求出端點(diǎn)裁剪一條線段時(shí)，先求出端點(diǎn)p p1 1p p2 2所所在的區(qū)號(hào)在的區(qū)號(hào)code1code1和和code2 code2 若若code1=0code1=0且且code2=0 code2=0 則說明則說明p p1 1和和p p2 2均在窗均在窗口內(nèi)，全保留口內(nèi)，全

20、保留 若若code10 code20code10 code20且且code1code20code1code20則說明則說明p p1 1和和p p2 2均在窗口外側(cè)，全舍棄均在窗口外側(cè)，全舍棄1)1) 若上述兩條件均不成立，則求出線段與窗若上述兩條件均不成立，則求出線段與窗口某邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，口某邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，其中必有一段完全在窗口外，可以棄之，其中必有一段完全在窗口外，可以棄之，再對(duì)另一段重復(fù)進(jìn)行上述處理。再對(duì)另一段重復(fù)進(jìn)行上述處理。 計(jì)算機(jī)圖形學(xué)第四章具體實(shí)現(xiàn)具體實(shí)現(xiàn)求交點(diǎn)求交點(diǎn) 求交運(yùn)算是計(jì)算機(jī)圖形學(xué)求交運(yùn)算是計(jì)算機(jī)圖形學(xué)中比較復(fù)雜的一個(gè)算法，現(xiàn)中比較

21、復(fù)雜的一個(gè)算法，現(xiàn)通過右圖簡(jiǎn)單推導(dǎo)出交點(diǎn)的通過右圖簡(jiǎn)單推導(dǎo)出交點(diǎn)的坐標(biāo)。坐標(biāo)。已知線段已知線段p p1 1p p2 2，現(xiàn)欲求其與現(xiàn)欲求其與窗口左邊線的交點(diǎn)窗口左邊線的交點(diǎn)s s（x x，y y）如圖所示：如圖所示：pp1 1sbpsbp1 1p p2 2a asb/psb/p2 2a=pa=p1 1b/pb/p1 1a a即：即：211121xxwxyyyyxl稍稍加加整整理理即即可可得得，左左交交點(diǎn)點(diǎn)為為： 111212)(yxwxxyyywxxlxl計(jì)算機(jī)圖形學(xué)第四章具體實(shí)現(xiàn)具體實(shí)現(xiàn)求交點(diǎn)求交點(diǎn)同同理理，可可推推導(dǎo)導(dǎo)出出： 右右交交點(diǎn)點(diǎn)為為： 111212)(yxwxxyyywxxrxr

22、 下下交交點(diǎn)點(diǎn)為為： ybybwyxywyyxxx111212)( 上上交交點(diǎn)點(diǎn)為為： ytytwyxywyyxxx111212)( 對(duì)于那些非完全可見、對(duì)于那些非完全可見、又非顯然不可見的線段，需又非顯然不可見的線段，需要求交，求交前先測(cè)試與窗要求交，求交前先測(cè)試與窗口哪條邊所在直線有交？口哪條邊所在直線有交？( (按序判斷端點(diǎn)編碼中各位按序判斷端點(diǎn)編碼中各位的值的值c cl lc ct tc cr rc cb b）求交測(cè)試順序固定求交測(cè)試順序固定( (左上右左上右下）下）最壞情形，線段求交四次。最壞情形，線段求交四次。計(jì)算機(jī)圖形學(xué)第四章done=0done=0accept=0accept=

23、0reject=0reject=0退出退出初始化初始化求求p1p1，p2p2的編碼的編碼c1c1，c2c2c1c2=0c1c2=0？c1=0c1=0且且c2=0c2=0c1=0?c1=0?p1p1與與p2p2交換交換done=1?done=1?accept=1?accept=1?顯示顯示 p1p2p1p2開始開始y yn再分割再分割n ny yp1p1在窗口內(nèi)在窗口內(nèi) n nyyn np1p1在在w w之之 求交求交 （丟棄）（丟棄）reject=1reject=1 done=1 done=1（接受）（接受）accept=1accept=1 done=1 done=1p1p1、p2p2均在均在

24、w w內(nèi)內(nèi) y yn np1p1、p2p2均在均在w w外外y1=wyty1=wytx1=x1=y1=wyby1=wybx1=x1=x1=wxrx1=wxry1=y1=x1=wxlx1=wxly1=y1=左左上上右右下下新新p1p1說明：在線段再分割求交的過程中，說明：在線段再分割求交的過程中，保證保證p1p1始終在窗口之外，得到的交始終在窗口之外，得到的交點(diǎn)（邊界上的點(diǎn)）為新的點(diǎn)（邊界上的點(diǎn)）為新的p1p1，重復(fù)，重復(fù)判斷判斷p1p1、p2p2的代碼，舍棄在窗口外的代碼，舍棄在窗口外的，顯示在窗口內(nèi)的線段。的，顯示在窗口內(nèi)的線段。計(jì)算機(jī)圖形學(xué)第四章nicholl-lee-nicholl算法

25、消除c-s算法中多次求交的情況。 基本想法：對(duì)2d平面的更細(xì)的劃分。計(jì)算機(jī)圖形學(xué)第四章nicholl-lee-nicholl算法假定待裁剪線段p0p1為非完全可見且非顯然不可見。 步驟：步驟：第一步，窗口四邊所在的直線將二維平面劃分成第一步，窗口四邊所在的直線將二維平面劃分成9 9個(gè)區(qū)域，假定個(gè)區(qū)域，假定 落在區(qū)域落在區(qū)域0 0、4 4、5 5 p0計(jì)算機(jī)圖形學(xué)第四章nicholl-lee-nicholl算法第二步：從第二步：從p p0 0點(diǎn)向窗口點(diǎn)向窗口的四個(gè)角點(diǎn)發(fā)出射的四個(gè)角點(diǎn)發(fā)出射線，這四條射線和線，這四條射線和窗口的四條邊所在窗口的四條邊所在的直線一起將二維的直線一起將二維平面劃分為更

26、多的平面劃分為更多的小區(qū)域小區(qū)域 。此時(shí)此時(shí)p1p1的位置決定了的位置決定了p p0 0p p1 1和和窗口邊的相交關(guān)系。窗口邊的相交關(guān)系。計(jì)算機(jī)圖形學(xué)第四章nicholl-lee-nicholl算法第三步，確定第三步，確定p p1 1所在的區(qū)域所在的區(qū)域（判斷p1所在區(qū)域位置，可判定p0、p1與窗口那條邊求交) 。根據(jù)窗口四邊的坐標(biāo)值及p p0 0p p1 1和各射線的斜率可確定p1所在的區(qū)域。第四步，求交點(diǎn)，確定第四步，求交點(diǎn)，確定p p0 0p p1 1的可見部分的可見部分 。特點(diǎn)：效率較高，但僅適合二維矩形窗口。計(jì)算機(jī)圖形學(xué)第四章（二）中點(diǎn)分割法（二）中點(diǎn)分割法原理：原理： 與與csc

27、s算法一樣對(duì)線段端點(diǎn)進(jìn)行編碼，算法一樣對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系一樣分為三種情并把線段與窗口的關(guān)系一樣分為三種情況，并對(duì)當(dāng)前兩種情況進(jìn)行一樣的處理。況，并對(duì)當(dāng)前兩種情況進(jìn)行一樣的處理。對(duì)于第三種情況，則簡(jiǎn)單的把線段等分對(duì)于第三種情況，則簡(jiǎn)單的把線段等分為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直至每條線段完全在窗口內(nèi)或完全在窗口至每條線段完全在窗口內(nèi)或完全在窗口外。外。計(jì)算機(jī)圖形學(xué)第四章中點(diǎn)分割法中點(diǎn)分割法如圖所示，為求線段如圖所示，為求線段p1p2p1p2的的看見部分看見部分abab，算法可分為兩個(gè)過，算法可分為兩個(gè)過程平行進(jìn)行，即：程平行進(jìn)行，即：（1

28、 1）從）從p1p1出發(fā)，找出離出發(fā)，找出離p1p1最遠(yuǎn)最遠(yuǎn)的可見點(diǎn)的可見點(diǎn)b b（2 2）從）從p2p2出發(fā)，找出離出發(fā)，找出離p2p2最遠(yuǎn)最遠(yuǎn)的可見點(diǎn)的可見點(diǎn)a a算法對(duì)兩個(gè)端點(diǎn)的處理是相算法對(duì)兩個(gè)端點(diǎn)的處理是相同的。同的。算法實(shí)質(zhì)：用對(duì)分的方法不斷排算法實(shí)質(zhì)：用對(duì)分的方法不斷排除線段的不可見部分，即處于窗除線段的不可見部分，即處于窗口同側(cè)外面的部分，目的是用中口同側(cè)外面的部分，目的是用中點(diǎn)逼近線段與窗口邊的交點(diǎn)點(diǎn)逼近線段與窗口邊的交點(diǎn)p1p2ab計(jì)算機(jī)圖形學(xué)第四章具體實(shí)現(xiàn)具體實(shí)現(xiàn) 在編碼時(shí)，應(yīng)避免把線段裁剪在編碼時(shí)，應(yīng)避免把線段裁剪成許多零碎的小段，這可以通過求成許多零碎的小段，這可以通

29、過求可見線段的端點(diǎn)來實(shí)現(xiàn)。可見線段的端點(diǎn)來實(shí)現(xiàn)。對(duì)線段對(duì)線段p p1 1p p2 2：1 1）若）若p p2 2可見，則可見，則p p2 2就是離就是離p p1 1最遠(yuǎn)的最遠(yuǎn)的可見點(diǎn)。可見點(diǎn)。2 2）對(duì)兩端點(diǎn)的區(qū)號(hào)作按位與運(yùn)算，）對(duì)兩端點(diǎn)的區(qū)號(hào)作按位與運(yùn)算，若結(jié)果不為若結(jié)果不為0 0，則全棄之，否則繼續(xù)。，則全棄之，否則繼續(xù)。3 3）在中點(diǎn)）在中點(diǎn)p pm m處把線段處把線段p p1 1p p2 2分為兩段，分為兩段，若若p pm m 可見，把原問題轉(zhuǎn)化為對(duì)可見，把原問題轉(zhuǎn)化為對(duì)p pm mp p2 2求離求離p1p1最遠(yuǎn)的可見點(diǎn)。若最遠(yuǎn)的可見點(diǎn)。若p pm m不可見，不可見，則把原問題轉(zhuǎn)化為

30、求則把原問題轉(zhuǎn)化為求p p1 1p pm m上離上離p1p1最遠(yuǎn)最遠(yuǎn)的可見點(diǎn)。重復(fù)執(zhí)行的可見點(diǎn)。重復(fù)執(zhí)行2 2），），3 3），直），直到分點(diǎn)與線段端點(diǎn)距離達(dá)到分辨率到分點(diǎn)與線段端點(diǎn)距離達(dá)到分辨率精度為止。精度為止。p1 p2 pm 待求點(diǎn) p1 p2 pm 待求點(diǎn) 計(jì)算機(jī)圖形學(xué)第四章中點(diǎn)分割法中點(diǎn)分割法計(jì)算機(jī)圖形學(xué)第四章四、四、 多邊形裁剪多邊形裁剪 錯(cuò)覺：直線段裁剪的組合？錯(cuò)覺：直線段裁剪的組合？ 新的問題新的問題： 1 1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？來封閉它，如何確定其邊界？計(jì)算機(jī)圖形學(xué)第四章四、多邊形裁剪四、

31、多邊形裁剪2 2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？如何確定這些小多邊形的邊界？計(jì)算機(jī)圖形學(xué)第四章sutherland-hodgmansutherland-hodgman算法算法（rpcrpc算法，逐邊裁剪算法）算法，逐邊裁剪算法）原理：原理： 一次用窗口的一條邊裁剪多邊形，一次用窗口的一條邊裁剪多邊形，輸出是一個(gè)頂點(diǎn)序列，再將其中作為下輸出是一個(gè)頂點(diǎn)序列，再將其中作為下一條裁剪邊處理過程的輸入，直至幾條一條裁剪邊處理過程的輸入，直至幾條邊線全部處理完。邊線全部處理完。 計(jì)算機(jī)圖形學(xué)第四章sutherland-hodg

32、mansutherland-hodgman算法算法 分割處理策略分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。為多邊形關(guān)于窗口四邊所在直線的裁剪。 流水線過程流水線過程( (左上右下左上右下) )：左邊的結(jié)果是上邊的開始左邊的結(jié)果是上邊的開始。計(jì)算機(jī)圖形學(xué)第四章sutherland-hodgmansutherland-hodgman算法算法 內(nèi)側(cè)空間與外側(cè)空間內(nèi)側(cè)空間與外側(cè)空間 多邊形的邊與半空間的關(guān)系多邊形的邊與半空間的關(guān)系輸出：輸出：p p點(diǎn)點(diǎn) （1 1個(gè)）個(gè)）輸出：交點(diǎn)輸出：交點(diǎn)i i（1 1個(gè)）個(gè)）輸出：輸出：0 0個(gè)頂個(gè)

33、頂點(diǎn)點(diǎn)輸出：輸出：i i點(diǎn)，點(diǎn)，p p點(diǎn)點(diǎn) （2 2個(gè)）個(gè)）計(jì)算機(jī)圖形學(xué)第四章sutherland-hodgmansutherland-hodgman算法算法 裁剪結(jié)果的頂點(diǎn)構(gòu)成裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多 邊形的邊與裁剪邊的交邊形的邊與裁剪邊的交點(diǎn)。點(diǎn)。 順序連接順序連接幾點(diǎn)說明：幾點(diǎn)說明：l裁剪算法采用流水線方式，裁剪算法采用流水線方式， 適合硬件實(shí)現(xiàn)。適合硬件實(shí)現(xiàn)。l可推廣到任意凸多邊形裁剪可推廣到任意凸多邊形裁剪 窗口窗口計(jì)算機(jī)圖形學(xué)第四章算法示例算法示例頂點(diǎn)序列頂點(diǎn)序列裁剪前：裁剪前：p p1 1，p p2 2，p p3 3，p p4 4，p p5

34、 5，p p6 6，p p7 7，p p1 1相對(duì)于左邊線裁剪：相對(duì)于左邊線裁剪：i i1 1，i i2 2，p p3 3，p p4 4，p p5 5，p p6 6，p p7 7，p p1 1相對(duì)于下邊線裁剪：相對(duì)于下邊線裁剪：i i2 2，p p3 3，i i3 3，i i4 4，p p6 6，p p7 7，p p1 1，i i1 1相對(duì)于右邊線裁剪：相對(duì)于右邊線裁剪：p p3 3，i i3 3，i i4 4，p p6 6，i i5 5，i i6 6，p p1 1，i i1 1，i i2 2相對(duì)于上邊線裁剪：相對(duì)于上邊線裁剪：i i3 3，i i4 4，p p6 6，i i5 5，i i6

35、6，i i7 7，i i8 8，i i1 1，i i2 2，p p3 3計(jì)算機(jī)圖形學(xué)第四章weiler-athentonweiler-athenton算法算法裁剪窗口為任意多邊形（裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：的情況： 主多邊形：被裁剪多邊形，記為主多邊形：被裁剪多邊形，記為a a 裁剪多邊形：裁剪窗口，記為裁剪多邊形：裁剪窗口，記為b b 計(jì)算機(jī)圖形學(xué)第四章 主多邊形和裁剪多邊形把二維平面分成兩部分。 內(nèi)裁剪內(nèi)裁剪：ab 外裁剪外裁剪：a-bweiler-athentonweiler-athenton算法算法裁剪結(jié)果區(qū)域的邊界由裁剪結(jié)果區(qū)域的邊界由a a的部分的部分邊界和邊界

36、和b b的部分邊界兩部分構(gòu)成，的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，并且在交點(diǎn)處邊界發(fā)生交替，即由即由a a的邊界轉(zhuǎn)至的邊界轉(zhuǎn)至b b的邊界，或的邊界，或由由b b的邊界轉(zhuǎn)至的邊界轉(zhuǎn)至a a的邊界的邊界 計(jì)算機(jī)圖形學(xué)第四章weiler-athentonweiler-athenton算法算法 如果主多邊形與裁剪多邊形有交點(diǎn)，則交點(diǎn)成對(duì)出如果主多邊形與裁剪多邊形有交點(diǎn)，則交點(diǎn)成對(duì)出現(xiàn)，它們被分為如下兩類：現(xiàn)，它們被分為如下兩類： 進(jìn)點(diǎn)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi)進(jìn)點(diǎn)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi) 如，如，i i1,1,i i3, 3, i i5, 5, i i7, 7, i i9, 9, i i1111 出點(diǎn)：主多邊形邊界由出點(diǎn)：主多邊形邊界由此離開裁剪多邊形區(qū)域此離開裁剪多邊形區(qū)域. . 如，如， i i0,0,i i2, 2, i i4, 4, i i6, 6, i i8, 8, i i1010 計(jì)算機(jī)圖形學(xué)第四章weiler-athentonweiler-athenton算法算法1）建頂點(diǎn)表；2）求交點(diǎn)；3）裁剪 weiler_athentonweiler_athenton