《線上線下混合式計(jì)算機(jī)圖形學(xué)基礎(chǔ)實(shí)驗(yàn)教程》課件-第6章

第6章直線段和多邊形裁剪6.1實(shí)驗(yàn)內(nèi)容簡(jiǎn)述和實(shí)驗(yàn)?zāi)繕?biāo)6.2

Cohen-Sutherland直線段裁剪6.3

Sutherland-Hodgman多邊形裁剪6.4

Weiler-Atherton多邊形裁剪6.5課外拓展性實(shí)驗(yàn)

6.1實(shí)驗(yàn)內(nèi)容簡(jiǎn)述和實(shí)驗(yàn)?zāi)繕?biāo)

基本實(shí)驗(yàn)內(nèi)容包括：Cohen-Sutherland直線段裁剪、Sutherland-Hodgman多邊形裁剪、Weiler-Atherton多邊形裁剪。

完成本實(shí)驗(yàn)后，讀者能夠：

(1)熟記和描述Cohen-Sutherland直線段裁剪的原理和過程(布魯姆知識(shí)模型：記憶和理解)；

(2)熟記和描述Sutherland-Hodgman多邊形裁剪的原理和過程(布魯姆知識(shí)模型：記憶和理解)；

(3)熟記和描述Weiler-Atherton多邊形裁剪的原理和過程(布魯姆知識(shí)模型：記憶和理解)；

(4)判斷交點(diǎn)是出點(diǎn)還是入點(diǎn)(布魯姆知識(shí)模型：應(yīng)用)；

(5)判斷點(diǎn)(累積角度法)是在多邊形內(nèi)部還是在多邊形外部(布魯姆知識(shí)模型：應(yīng)用)；

(6)結(jié)合OpenGL編程實(shí)現(xiàn)——Cohen-Sutherland直線段裁剪、Sutherland-Hodgman多邊形裁剪和Weiler-Atherton多邊形裁剪(布魯姆知識(shí)模型：應(yīng)用)。

6.2Cohen-Sutherland直線段裁剪

Cohen-Sutherland直線段裁剪算法的核心思想是：將每條線段P1P2分為以下三種情況來處理。

(1)若線段P1P2完全在裁剪多邊形內(nèi)，則完整保留該線段。

(2)若線段P1P2明顯在裁剪多邊形外，則直接丟棄該線段。

(3)若線段P1P2不滿足(1)、(2)條件，則求出線段與裁剪多邊形的交點(diǎn)，將該線段分成兩段，丟棄完全在裁剪多邊形外的線段，然后對(duì)另一段迭代上述處理。

為了快速判斷一條直線段與裁剪多邊形的位置關(guān)系，可采用的編碼方法是：延長(zhǎng)裁剪多邊形的邊，將二維平面分成9個(gè)區(qū)域，給每個(gè)區(qū)域賦予4位編碼(見圖6-1)。

圖6-1多邊形裁剪區(qū)域編碼

裁剪一條線段時(shí)(見圖6-2)，先求出線段兩端點(diǎn)P1、P4的編碼code1、code2。若code1=0、code2=0，則線段P1P2完全在裁剪多邊形內(nèi)，直接完整保留該線段。若編碼按位與運(yùn)算code1&code20，則說明兩個(gè)端點(diǎn)同在裁剪多邊形的上方、下方、左方或右方，可判斷線段完全在裁剪多邊形外，丟棄整條線段；否則求出線段與裁剪多邊形的交點(diǎn)，將直線段分成兩段，先丟棄完全在裁剪多邊形外的線段，再對(duì)剩下的另一段線段迭代開展上述操作。

圖6-2線段裁剪

1.關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

自定義如下數(shù)據(jù)結(jié)構(gòu)用以表示三維齊次坐標(biāo)下的點(diǎn)(頂點(diǎn)或者交點(diǎn))。該數(shù)據(jù)結(jié)構(gòu)應(yīng)用于本書隨后所有章節(jié)的實(shí)驗(yàn)中。

2.關(guān)鍵函數(shù)代碼實(shí)現(xiàn)

3.案例效果

圖6-3(a)顯示了直線和裁剪多邊形的初始狀態(tài)，平移裁剪多邊形，用Cohen-Sutherland算法執(zhí)行裁剪，最終效果如圖6-3(b)所示。

圖6-3用Cohen-Sutherland算法執(zhí)行裁剪示意圖

6.3Sutherland-Hodgman多邊形裁剪

Sutherland-Hodgman多邊形裁剪算法的基本思想是：遍歷裁剪多邊形的每一條邊，用逐條邊去裁剪被裁剪多邊形。因此，在算法的每一步中，僅需考慮裁剪多邊形的一條邊及其延長(zhǎng)線構(gòu)成的裁剪線。該裁剪線把平面分成兩個(gè)部分：可見一側(cè)(即包含裁剪多邊形的一側(cè))和不可見一側(cè)(即不包含裁剪多邊形的一側(cè))。

按序考慮被裁剪多邊形每條邊端點(diǎn)S、P與裁剪線的位置關(guān)系，有以下四種情況：

(1)若S、P均在可見一側(cè)，則保留點(diǎn)P(見圖6-4(a))。

(2)若S、P均在不可見一側(cè)，則保留0個(gè)點(diǎn)(見圖6-4(b))。

(3)若S可見，P不可見，則保留SP與裁剪線的交點(diǎn)I(見圖6-4(c))。

(4)若S不可見，P可見，則保留SP與裁剪線的交點(diǎn)I和點(diǎn)P(見圖6-4(d))。

圖6-4

S、P與裁剪線的四種位置關(guān)系

1.關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

自定義點(diǎn)相對(duì)于多邊形的空間位置關(guān)系，其數(shù)據(jù)結(jié)構(gòu)如下：

2.關(guān)鍵函數(shù)代碼實(shí)現(xiàn)

3.案例效果

圖6-5(a)給定了裁剪多邊形(粗線)和被裁剪多邊形(細(xì)線)的初始狀態(tài)，用Sutherland-

Hodgman算法執(zhí)行裁剪，最終效果如圖6-5(b)所示。

圖6-5用Sutherland-Hodgman算法執(zhí)行裁剪示意圖

6.4Weiler-Atherton多邊形裁剪

Weiler-Atherton多邊形裁剪算法能有效開展凹多邊形的裁剪。假設(shè)被裁剪多邊形和裁剪多邊形的頂點(diǎn)都按逆時(shí)針方向排列。當(dāng)上述兩個(gè)多邊形相交時(shí)，交點(diǎn)通常成對(duì)出現(xiàn)，即存在多對(duì)“入點(diǎn)”和“出點(diǎn)”，沿著被裁剪多邊形的邊逆時(shí)針游走，通過入點(diǎn)進(jìn)入裁剪多邊形內(nèi)部；沿著被裁剪多邊形的邊逆時(shí)針游走，通過出點(diǎn)離開裁剪多邊形內(nèi)部。根據(jù)上述現(xiàn)象，Weiler-Atherton多邊形裁剪算法從被裁剪多邊形中選擇一個(gè)未被訪問的入點(diǎn)，沿著該點(diǎn)所在的邊逆時(shí)針游走。

其算法步驟如下：

(1)定義裁剪多邊形clip_polygon和被裁剪多邊形subject_polygon，它們均為my_homogeneous_point_EX數(shù)組。同時(shí)，定義三個(gè)帶頭指針的循環(huán)鏈表plist、clip_polygonlist和subject_polygonlist，分別用來存儲(chǔ)交點(diǎn)、插入交點(diǎn)的裁剪多邊形和插入交點(diǎn)的被裁剪多邊形。

(2)定義一個(gè)多邊形求交函數(shù)generateIntersectPoints，實(shí)現(xiàn)兩個(gè)多邊形的所有交點(diǎn)存儲(chǔ)在plist鏈表中，在此過程中，將上述每一交點(diǎn)按序(相交邊的兩端點(diǎn)之間)插入subject_polygonlist和clip_polygonlist。

(3)定義函數(shù)用來確定每個(gè)交點(diǎn)為出點(diǎn)或入點(diǎn)。

(4)定義生成所有裁剪結(jié)果區(qū)域的函數(shù)generateClipArea，其具體步驟如下：

①定義記錄裁剪結(jié)果的臨時(shí)數(shù)組subject_polygonClip。

②從頭指針開始順序遍歷subject_polygonlist，尋找第一個(gè)未被訪問過的入點(diǎn)，若存在，則將該入點(diǎn)設(shè)為當(dāng)前點(diǎn)，并記錄到subject_polygonClip中，進(jìn)入步驟③，否則進(jìn)入步驟⑤。

③從當(dāng)前點(diǎn)開始遍歷subject_polygonlist，將下一個(gè)被訪問的點(diǎn)PC設(shè)為當(dāng)前點(diǎn)，并記錄到subject_polygonClip中。若PC為subject_polygonClip的第一個(gè)點(diǎn)，則將subject_polygonClip數(shù)據(jù)輸出，即找到一個(gè)裁剪結(jié)果區(qū)域，之后清空subject_polygonClip，并進(jìn)入步驟②；而若PC不是出點(diǎn)，則繼續(xù)步驟③操作，否則在clip_polygonlist中找到PC，并進(jìn)入步驟④。

④從當(dāng)前點(diǎn)開始遍歷clip_polygonlist，將下一個(gè)被訪問的點(diǎn)PN設(shè)為當(dāng)前點(diǎn)，并記錄到subject_polygonClip中。若PN不是入點(diǎn)，則繼續(xù)步驟④操作，否則進(jìn)入步驟③。

⑤退出函數(shù)，裁剪完成。

1.關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

2.關(guān)鍵代碼實(shí)現(xiàn)

3.案例效果

如圖6-6(a)所示為裁剪多邊形(粗線)和被裁剪多邊形(細(xì)線)的初始狀態(tài)，用