計(jì)算機(jī)圖形學(xué)第6章二維圖形的裁剪(1).ppt

《計(jì)算機(jī)圖形學(xué)第6章二維圖形的裁剪(1).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第七章二維圖形的裁剪重點(diǎn)：掌握二維圖形點(diǎn)、線段、多邊形和字符的裁剪算法。難點(diǎn)：理解二維圖形的裁剪算法思想并且用C語(yǔ)言進(jìn)行算法的實(shí)現(xiàn)。一、裁剪的意義為了描述圖形對(duì)象，我們必須存儲(chǔ)它的全部信息，但有時(shí)為了達(dá)到分區(qū)描述或重點(diǎn)描述某一部分的目的，往往將要描述的部分置于一個(gè)窗口內(nèi)，而將窗口外的部分“剪掉”，這個(gè)處理過(guò)程叫做裁剪，裁剪在計(jì)算機(jī)圖形處理中具有十分重要的意義。裁剪實(shí)質(zhì)上是從數(shù)據(jù)集合中抽取信息的過(guò)程，這個(gè)過(guò)程是通過(guò)一定的計(jì)算方法來(lái)實(shí)現(xiàn)。裁剪就是將指定窗口作為圖形邊界，將窗口內(nèi)的圖形保留，而窗口外的圖形則被舍棄。二、裁剪的

2、目的裁剪的基本目的是判斷某個(gè)圖形元素是否落在窗口之內(nèi)，如落在窗口之內(nèi)則進(jìn)一步求出位于窗口內(nèi)的部分。三、裁剪處理涉及1、圖元在窗口內(nèi)外的判別；2、圖形元素與窗口的求交。7.1點(diǎn)的裁剪先看簡(jiǎn)單的點(diǎn)圖元裁剪，它是線段裁剪以及后面的多邊形裁剪的基礎(chǔ)。如果矩形窗口的左、右橫坐標(biāo)為：xmin、xmax；　　　　　　　上、下縱坐標(biāo)為：ymin，ymax。某點(diǎn)（x，y）在窗口內(nèi)的充分必要條件是：如果上面四個(gè)不等式中任何一個(gè)不滿足，則點(diǎn)（x，y）位于窗口之外。對(duì)于任意多邊形窗口，需要根據(jù)多邊形內(nèi)點(diǎn)的判別準(zhǔn)則進(jìn)行判斷。7.2線段的裁剪直線段

3、的裁剪比點(diǎn)復(fù)雜，其裁剪方法又是多邊形裁剪和三維圖形裁剪的基礎(chǔ)。一、直線裁剪的基本思想判斷直線與窗口的位置關(guān)系：1．確定直線是完全可見(jiàn)；2．部分可見(jiàn)；3．還是完全不可見(jiàn)。對(duì)部分可見(jiàn)線段，求出它與窗口邊界的交點(diǎn)，并將窗口內(nèi)的線段輸出。五種位置關(guān)系??二、裁剪線段和窗口的關(guān)系假定窗口左下角坐標(biāo)為(xmin，ymin)，右上角坐標(biāo)為(xmax，ymax)，待裁剪線段和窗口的關(guān)系如圖所示，這五種位置關(guān)系存在下面三種情況：7.2線段的裁剪1、直線的兩個(gè)端點(diǎn)均在窗口內(nèi)，如圖中AB線。這時(shí)直線完全可見(jiàn)，可被簡(jiǎn)單接受。2、直線的兩個(gè)端點(diǎn)都在

4、窗口外，并且位于窗口某一邊界的同一外側(cè)，如圖中EF線。則直線完全不可見(jiàn)，可被簡(jiǎn)單舍棄。3、除此之外需要求交點(diǎn)，以確定直線在窗口某一邊界內(nèi)是否有可見(jiàn)部分,并裁掉外部線段，顯示內(nèi)部線段。如CD、GH、IJ線。為了提高裁剪效率，算法設(shè)計(jì)一般可從下面兩方面作出考慮：(1)快速判斷情況1和情況2。(2)在情況3中，設(shè)法減少求交的次數(shù)和每次求交時(shí)所需的計(jì)算量。7.2線段的裁剪三、直線求交計(jì)算當(dāng)線段P1P2穿過(guò)某邊界L時(shí)，交點(diǎn)P的計(jì)算如圖中所示。根據(jù)直線兩點(diǎn)式方程：整理后得通用交點(diǎn)公式：7.2線段的裁剪1、與上邊界的求交公式：2、與下邊

5、界的求交公式：3、與右邊界的求交公式：4、與左邊界的求交公式：7.2線段的裁剪四、直線裁剪的常用算法直線1．Cohen－Sutherland算法2．中點(diǎn)分割算法3．梁友棟-Barsky裁剪算法7.2.1Cohen－Sutherland算法一、Cohen－Sutherland算法思想：該算法也稱為編碼算法，首先對(duì)線段的兩個(gè)端點(diǎn)按所在的區(qū)域進(jìn)行分區(qū)編碼，根據(jù)編碼可以迅速地判明全部在窗口內(nèi)的線段和全部在某邊界外側(cè)的線段。只有不屬于這兩種情況的線段，才需要求出線段與窗口邊界的交點(diǎn)，求出交點(diǎn)后，舍去窗外部分。對(duì)剩余部分，把它作為新的

6、線段看待，又從頭開(kāi)始考慮。兩遍循環(huán)之后，就能確定該線段是部分截留下來(lái)，還是全部舍棄。Cohen-Sutherland算法(編碼算法)算法思想：第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見(jiàn)；否則進(jìn)入第二步；第二步判別線段是否為顯然不可見(jiàn)，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見(jiàn)，丟棄。對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束裁剪過(guò)程是遞歸的。7.2.1Cohen－Sutherland算法二、Cohen－Sutherland算法步

7、驟：1、分區(qū)編碼延長(zhǎng)裁剪邊框?qū)⒍S平面分成九個(gè)區(qū)域，每個(gè)區(qū)域各用一個(gè)四位二進(jìn)制代碼標(biāo)識(shí)。各區(qū)代碼值如圖中所示。四位二進(jìn)制代碼的編碼規(guī)則是：(1)第一位置1：區(qū)域在左邊界外側(cè)(2)第二位置1：區(qū)域在右邊界外側(cè)(3)第三位置1：區(qū)域在下邊界外側(cè)(4)第四位置1：區(qū)域在上邊界外側(cè)裁剪窗口內(nèi)（包括邊界上）的區(qū)域，四位二進(jìn)制代碼均為0。設(shè)線段的兩個(gè)端點(diǎn)為P1（x1，y1）和P2（x2，y2），根據(jù)上述規(guī)則，可以求出P1和P2所在區(qū)域的分區(qū)代碼C1和C2。7.2.1Cohen－Sutherland算法2、判別根據(jù)C1和C2的具體值，可

8、以有三種情況：（1）C1=C2＝0，表明兩端點(diǎn)全在窗口內(nèi)，因而整個(gè)線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C2≠0（兩端點(diǎn)代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時(shí)為1，表明兩端點(diǎn)必定處于某一邊界的同一外側(cè)，因而整個(gè)線段全在窗外，應(yīng)予舍棄。（3）不屬于上面兩種情況，均需要求交點(diǎn)。3、求交點(diǎn)假設(shè)算