Barsky直線裁剪算法計(jì)算機(jī)圖形學(xué)課程設(shè)計(jì)

1、河南理工大學(xué)萬(wàn)方科技學(xué)院課程設(shè)計(jì)報(bào)告2011 2012學(xué)年第二學(xué)期課程名稱 計(jì)算機(jī)圖形學(xué) 設(shè)計(jì)題目 計(jì)算機(jī)圖形學(xué)基本算法 演示系統(tǒng)設(shè)計(jì) 學(xué)生姓名 學(xué) 號(hào) 專業(yè)班級(jí) 網(wǎng)絡(luò)11升1班 指導(dǎo)教師 徐 文 鵬 2012 年 5 月 28 日18目 錄目 錄第1章 設(shè)計(jì)內(nèi)容與要求11.1總體目標(biāo)和要求11.2內(nèi)容與要求 11.2.1 直線的生成11.2.2 圓弧的生成11.2.3 線段裁剪21.2.4 多邊形裁剪21.2.5 綜合2第2章 總體設(shè)計(jì)32.1 bresenham算法畫直線32.1.1 bresenham算法畫直線理論基礎(chǔ)32.1.2 bresenham算法畫直線原理32.2 bresenh

2、am算法畫圓42.2.1 bresenham算法畫圓理論基礎(chǔ)42.2.2 bresenham算法畫圓原理52.3 梁友棟-barsky算法進(jìn)行線段裁剪62.3.1梁友棟-barsky算法進(jìn)行線段裁剪基本原理62.4 sutherland-hodgman算法進(jìn)行多邊形裁剪82.4.1 sutherlandhodgman多邊形裁剪算法思想82.4.2 點(diǎn)在邊界內(nèi)側(cè)的判斷方法82.4.4 sutherland-hodgeman多邊形裁剪算法特點(diǎn)8第3章 詳細(xì)設(shè)計(jì)93.1 bresenham算法畫直線93.1.1 bresenham 算法畫線算法具體實(shí)現(xiàn)過(guò)程93.2 bresenham算法畫圓93.2

3、.1 bresenham 算法畫圓核心代碼93.3 梁友棟-barsky算法進(jìn)行線段裁剪103.3.1梁友棟-barsky算法推導(dǎo)過(guò)程103.3.2梁友棟-barsky算法進(jìn)行線段裁剪的步驟113.4 sutherland-hodgman算法進(jìn)行多邊形裁剪113.4.1 sutherlandhodgman多邊形裁剪算法步驟113.5將畫線、畫圓、線段裁剪和多邊形裁剪綜合12第4章 功能實(shí)現(xiàn)144.1用bresenham算法畫線測(cè)試結(jié)果144.2用bresenham算法畫圓測(cè)試結(jié)果144.3梁友棟-barsky算法進(jìn)行線段裁剪測(cè)試結(jié)果154.4 sutherland-hodgman算法進(jìn)行多邊形

4、裁剪測(cè)試結(jié)果164.5將四種算法綜合測(cè)試結(jié)果16第5章 總結(jié)17參考文獻(xiàn)18第1章 基礎(chǔ)知識(shí)第1章 設(shè)計(jì)內(nèi)容與要求1.1 總體目標(biāo)和要求目標(biāo)：以圖形學(xué)算法為目標(biāo)，深入研究。繼而策劃、設(shè)計(jì)并實(shí)現(xiàn)一個(gè)能夠表現(xiàn)計(jì)算機(jī)圖形學(xué)算法原理的或完整過(guò)程的演示系統(tǒng)，并能從某些方面作出評(píng)價(jià)和改進(jìn)意見(jiàn)。通過(guò)完成一個(gè)完整程序，經(jīng)歷策劃、設(shè)計(jì)、開(kāi)發(fā)、測(cè)試、總結(jié)和驗(yàn)收各階段，達(dá)到：1) 鞏固和實(shí)踐計(jì)算機(jī)圖形學(xué)課程中的理論和算法；2) 學(xué)習(xí)表現(xiàn)計(jì)算機(jī)圖形學(xué)算法的技巧；3) 培養(yǎng)認(rèn)真學(xué)習(xí)、積極探索的精神?？傮w要求：策劃、設(shè)計(jì)并實(shí)現(xiàn)一個(gè)能夠充分表現(xiàn)圖形學(xué)算法的演示系統(tǒng)，界面要求美觀大方，能清楚地演示算法執(zhí)行的每一個(gè)步驟。開(kāi)發(fā)環(huán)

5、境：viusal c+ 6.0，vc2005或其他你認(rèn)為比較熟悉的環(huán)境。1.2 內(nèi)容與要求實(shí)驗(yàn)分為五項(xiàng)內(nèi)容。1.2.1 直線的生成內(nèi)容：用bresenham算法畫直線要求：1) 鼠標(biāo)移動(dòng)時(shí)，顯示鼠標(biāo)當(dāng)前位置2) 顯示判別式的計(jì)算過(guò)程和下一點(diǎn)的選擇策略3) 記錄生成點(diǎn)的坐標(biāo)4) 圖形生成過(guò)程可以重復(fù)進(jìn)行1.2.2 圓弧的生成內(nèi)容：用bresenham算法畫圓要求：1) 鼠標(biāo)移動(dòng)時(shí)，顯示鼠標(biāo)當(dāng)前位置2) 顯示判別式的計(jì)算過(guò)程和下一點(diǎn)的選擇策略3) 記錄生成點(diǎn)的坐標(biāo)4) 圖形生成過(guò)程可以重復(fù)進(jìn)行5) 橡皮筋技術(shù)實(shí)現(xiàn)1.2.3 線段裁剪內(nèi)容：用梁友棟-barsky算法進(jìn)行線段裁剪要求：1) 對(duì)于線段裁

6、剪，線段被窗口的四條邊裁剪的過(guò)程要顯示出來(lái)2) 用橡皮筋的形式輸入剪裁線段1.2.4 多邊形裁剪內(nèi)容：用sutherland-hodgman算法進(jìn)行多邊形裁剪要求：1) 裁剪過(guò)程需先輸入一多邊形，然后用窗口四邊裁剪的過(guò)程中要顯示頂點(diǎn)增刪過(guò)程。2) 用橡皮筋的形式輸入剪裁線段1.2.5 綜合內(nèi)容：把前四次的實(shí)驗(yàn)內(nèi)容整合到一起要求：第2章 總體設(shè)計(jì)第2章 總體設(shè)計(jì)2.1 bresenham算法畫直線2.1.1 bresenham算法畫直線理論基礎(chǔ)計(jì)算機(jī)是如何畫直線的？簡(jiǎn)單來(lái)說(shuō)，就是過(guò)各行各列像素中心構(gòu)造一組虛擬的網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算各直線與歌垂直網(wǎng)格線的交點(diǎn)，然后確定各列像素中與此

7、交點(diǎn)最近的像素。真實(shí)的直線是連續(xù)的，但我們的計(jì)算機(jī)顯示的精度有限，不可能真正顯示連續(xù)的直線，于是我們用一系列離散化后的點(diǎn)（像素）來(lái)近似表現(xiàn)這條直線。2.1.2 bresenham算法畫直線原理接下來(lái)的問(wèn)題就是如何盡可能高效地找到這些離散的點(diǎn)，bresenham直線算法就是一個(gè)非常不錯(cuò)的算法。bresenham直線算法是用來(lái)描繪由兩點(diǎn)所決定的直線的算法，它會(huì)算出一條線段在 n 維光柵上最接近的點(diǎn)。這個(gè)算法只會(huì)用到較為快速的整數(shù)加法、減法和位元移位，常用于繪制電腦畫面中的直線。是計(jì)算機(jī)圖形學(xué)中最先發(fā)展出來(lái)的算法。這個(gè)算法的流程圖如下：可以看到，算法其實(shí)只考慮了斜率在 0 1 之間的直線，也就是與

8、x 軸夾角在 0 度到 45 度的直線。只要解決了這類直線的畫法，其它角度的直線的繪制全部可以通過(guò)簡(jiǎn)單的坐標(biāo)變換來(lái)實(shí)現(xiàn)。 2.2 bresenham算法畫圓2.2.1 bresenham算法畫圓理論基礎(chǔ)bresenham畫圓算法與bresenham 直線算法一樣，其基本的方法是利用判別變量來(lái)判斷選擇最近的像素點(diǎn)，判別變量的數(shù)值僅僅用一些加、減和移位運(yùn)算就可以計(jì)算出來(lái)。為了簡(jiǎn)便起見(jiàn)，考慮一個(gè)圓心在坐標(biāo)原點(diǎn)的圓，而且只計(jì)算八分圓周上的點(diǎn)，其余圓周上的點(diǎn)利用對(duì)稱性就可得到。為什么只計(jì)算八分圓周上的點(diǎn)就可以了呢？和上面的直線算法類似，圓也有一個(gè)“八對(duì)稱性”，如下圖所示。 顯然，我們只需要知道了圓上的一

9、個(gè)點(diǎn)的坐標(biāo) (x, y) ，利用八對(duì)稱性，我們馬上就能得到另外七個(gè)對(duì)稱點(diǎn)的坐標(biāo)。 2.2.2 bresenham算法畫圓原理和直線算法類似，bresenham畫圓算法也是用一系列離散的點(diǎn)來(lái)近似描述一個(gè)圓，如下圖。 bresenham畫圓算法的流程圖如下。 可以看到，與畫線算法相比，畫圓的循環(huán)中用到了整數(shù)的乘法，相對(duì)復(fù)雜了一些。 2.3 梁友棟-barsky算法進(jìn)行線段裁剪2.3.1梁友棟-barsky算法進(jìn)行線段裁剪基本原理我們知道，一條兩端點(diǎn)為p1（x1，y1）、p2（x2，y2）的線段可以用參數(shù)方程形式表示：x= x1+ u（x2-x1）= x1+ ux，y= y1+ u（y2-y1）=

10、y1+ uy式中，x=x2-x1，y=y2-y1，參數(shù)u在01之間取值，p（x，y）代表了該線段上的一個(gè)點(diǎn)，其值由參數(shù)u確定，由公式可知，當(dāng)u=0時(shí)，該點(diǎn)為p1（x1，y1），當(dāng)u=1時(shí)，該點(diǎn)為p2（x2，y2）。如果點(diǎn)p（x，y）位于由坐標(biāo)（xwmin，ywmin）和（xwmax，ywmax）所確定的窗口內(nèi)，那么下式成立：xwminx1+ uxxwmax，ywminy1+ uyywmax這四個(gè)不等式可以表示為：upk qk ， k=1，2，3，4其中，p、q定義為p1=-x， q1=x1-xwminp2= x， q2=xwmax-x1p3=-y， q3=y1-ywminp4= y， q4=y

11、wmax-y1可以知道：任何平行于窗口某邊界的直線，其pk=0，k值對(duì)應(yīng)于相應(yīng)的邊界（k=1，2，3，4對(duì)應(yīng)于左、右、下、上邊界）。如果還滿足qk0，則線段完全在邊界外，應(yīng)舍棄該線段。如果pk=0并且qk0，則線段平行于窗口某邊界并在窗口內(nèi)，見(jiàn)圖中所示。1、當(dāng)pk0時(shí)，線段從裁剪邊界延長(zhǎng)線的內(nèi)部延伸到外部；例如，當(dāng)x0時(shí)，對(duì)于左邊界p10（p2=x），線段從右邊界的內(nèi)部到外部。當(dāng)y0（p3=-y），線段從下邊界的內(nèi)部到外部；對(duì)于上邊界p40（p4=y），線段從上邊界的外部到內(nèi)部。當(dāng)pk0時(shí)，可以計(jì)算出參數(shù)u的值，它對(duì)應(yīng)于無(wú)限延伸的直線與延伸的窗口邊界k的交點(diǎn)，即：對(duì)于每條直線，可以計(jì)算出參數(shù)u

12、1和u2，該值定義了位于窗口內(nèi)的線段部分：1、u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（pk0），對(duì)這些邊界計(jì)算rk=qk/pk，u2取0和各個(gè)r值之中的最小值。3、如果u1u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點(diǎn)可以由u1和u2計(jì)算出來(lái)。2.4 sutherland-hodgman算法進(jìn)行多邊形裁剪2.4.1 sutherlandhodgman多邊形裁剪算法思想該算法的基本思想是每次用窗口的一條邊界及其延長(zhǎng)線來(lái)裁剪多邊形的各邊。多邊形通常由它的頂點(diǎn)序列來(lái)表示，經(jīng)過(guò)裁剪規(guī)則針對(duì)某條邊界裁剪后，結(jié)果形成新的頂點(diǎn)序列，又留待下條邊界進(jìn)行裁剪，直到窗口的所有邊界都裁剪完

13、畢，算法形成最后的頂點(diǎn)序列，才是結(jié)果多邊形（它可能構(gòu)成一個(gè)或多個(gè)多邊形）。當(dāng)多邊形一個(gè)頂點(diǎn)pi相對(duì)于窗口某條邊界及其延長(zhǎng)線進(jìn)行剪裁時(shí)，不外乎下列四種情況（即裁剪規(guī)則）：1、頂點(diǎn)pi在內(nèi)側(cè)，前一頂點(diǎn)pi-1也在內(nèi)側(cè)，則將pi納入新的頂點(diǎn)序列；2、頂點(diǎn)pi在內(nèi)側(cè)，前一頂點(diǎn)pi-1在外側(cè)，則先求交點(diǎn)q，再將q、pi依次納入新的頂點(diǎn)序列；3、頂點(diǎn)pi在外側(cè)，前一頂點(diǎn)pi-1在內(nèi)側(cè)，則先求交點(diǎn)q，再將q納入新的頂點(diǎn)序列；4、頂點(diǎn)pi與前一頂點(diǎn)pi-1均在外側(cè)，則頂點(diǎn)序列中不增加新的頂點(diǎn)。2.4.2 點(diǎn)在邊界內(nèi)側(cè)的判斷方法為了判斷點(diǎn)是否在邊界內(nèi)側(cè)可用坐標(biāo)比較法和更通用的向量叉積符號(hào)判別法。1、坐標(biāo)比較法將

14、點(diǎn)的某個(gè)方向分量與邊界進(jìn)行比較。例如，判斷某點(diǎn)是否在下邊界內(nèi)側(cè),用條件判別式： if(pi1=ymin) 即可。2、向量叉積法為簡(jiǎn)單計(jì)，測(cè)試點(diǎn)表示為p點(diǎn)。假設(shè)窗口邊界方向?yàn)轫槙r(shí)針，如圖中所示，對(duì)于其中任一邊界向量，從向量起點(diǎn)a向終點(diǎn)b看過(guò)去：如果被測(cè)試點(diǎn)p在該邊界線右邊(即內(nèi)側(cè))，abap的方向與x-y平面垂直并指向屏幕里面，即右手坐標(biāo)系中z軸的負(fù)方向。反過(guò)來(lái)，如果p在該邊界線的左邊(即外側(cè))，這時(shí)abap的方向與x-y平面垂直并指向屏幕外面，即右手坐標(biāo)系中z軸的正方向。設(shè)：點(diǎn)p(x，y)、點(diǎn)a(xa，ya)、點(diǎn)b(xb，yb)，向量ab=(xb-xa)，(yb-ya)，向量ap=(x-xa)

15、，(y-ya)，那么abap的方向可由下式的符號(hào)來(lái)確定：v=(xb-xa)*(y-ya)- (x-xa)*(yb-ya) 因此，當(dāng)v0時(shí)，p在邊界線內(nèi)側(cè)；而v0時(shí)，p在邊界線外側(cè)。2.4.4 sutherland-hodgeman多邊形裁剪算法特點(diǎn)sutherlandhodgeman多邊形裁剪算法具有一般性，被裁剪多邊形可以是任意凸多邊形或凹多邊形，裁剪窗口不局限于矩形，可以是任意凸多邊形。上面的算法是多邊形相對(duì)窗口的一條邊界進(jìn)行裁剪的實(shí)現(xiàn)，對(duì)于窗口的每一條邊界依次調(diào)用該算法程序，并將前一次裁剪的結(jié)果多邊形作為下一次裁剪時(shí)的被裁剪多邊形，即可得到完整的多邊形裁剪程序。第3章 詳細(xì)設(shè)計(jì)第3章 詳

16、細(xì)設(shè)計(jì)3.1 bresenham算法畫直線3.1.1 bresenham 算法畫線算法具體實(shí)現(xiàn)過(guò)程1、畫點(diǎn)(x1, y2); dx=x2-x1; dy=y2-y1；計(jì)算誤差初值p1=2dy-dx; i=1；2、求直線的下一點(diǎn)位置：xi+1=xi+1；if pi0 則yi+1=yi+1；否則yi+1=yi；3、畫點(diǎn)（xi+1, yi-1）；4、求下一個(gè)誤差pi+1；if pi0 則pi+1=pi+2dy-2dx;否則pi+1=pi+2dy；5、i=i+1; if i|dy|為分支，并分別將2a, 3a象限的直線和3b, 4b象限的直線變換到1a, 4a和2b, 1b方向去，以求得程序處理的簡(jiǎn)潔。

17、3.2 bresenham算法畫圓3.2.1 bresenham 算法畫圓核心代碼根據(jù)bresenham算法思想編寫程序代碼，在bresenham算法畫線的基礎(chǔ)上畫圓，程序代碼如下：void bresenhamcircle(int x0,int y0,int r)/,int color) int x,y,d; x=0;y=r; d=3-2*r;while(xy) glcolor3f (0.0f, 1.0f, 0.0f); putpixel(x0+x,y0+y); putpixel(x0+x,y0-y); putpixel(x0-x,y0+y); putpixel(x0-x,y0-y); put

18、pixel(x0+y,y0+x); putpixel(x0+y,y0-x); putpixel(x0-y,y0+x); putpixel(x0-y,y0-x); if(d0) d=d+4*x+6; elsed=d+4*(x-y)+10;y=y-1; x+; 3.3 梁友棟-barsky算法進(jìn)行線段裁剪3.3.1梁友棟-barsky算法推導(dǎo)過(guò)程情形一 pk=0p1p20若q10或q2=0且q2=0,則進(jìn)一步判斷 u=qk/pk（k=3,4） 令u1=max(0,u|pk0)若u1u2,則可刪除直線段若u1=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見(jiàn)端點(diǎn)。p3p40 若q30或q4=0且

19、q4=0,則進(jìn)一步判斷 u=qk/pk（k=1,2）令u1=max(0,u|pk0)若u1u2,則可刪除直線段若u1=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見(jiàn)端點(diǎn)。情形二 pk不為0u=qk/pk（k=1,2,3,4）令 u1=max(0,u|pk0,u|pk0, u|pk0)若u1u2,則可刪除直線段若u1=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見(jiàn)端點(diǎn)。3.3.2梁友棟-barsky算法進(jìn)行線段裁剪的步驟(1) 輸入直線段的兩端點(diǎn)坐標(biāo)以及窗口的四條邊界坐標(biāo)。(2) 若x=0，則p1=p2=0。進(jìn)一步判斷是否滿足q10或q20且q20，則進(jìn)一步計(jì)算u1和u2。轉(zhuǎn)(5)。

20、 (3) 若y=0，則p3=p4=0。進(jìn)一步判斷是否滿足q30或q40且q20，則進(jìn)一步計(jì)算u1和u2。轉(zhuǎn)(5)。(4) 若上述兩條均不滿足,則有pk0(k=1,2,3,4)。此時(shí)計(jì)算u1和u2。(5) 求得u1和u2后,進(jìn)行判斷：若u1u2,則直線段在窗口外,轉(zhuǎn)(7)。若u1u2,利用直線的參數(shù)方程求得直線段在窗口內(nèi)的兩端點(diǎn)坐標(biāo)。(6) 利用直線的掃描轉(zhuǎn)換算法繪制在窗口內(nèi)的直線段。(7) 算法結(jié)束。3.4 sutherland-hodgman算法進(jìn)行多邊形裁剪3.4.1 sutherlandhodgman多邊形裁剪算法步驟考慮多邊形相對(duì)于一條邊界及其延長(zhǎng)線進(jìn)行裁剪的算法：1 從主函數(shù)得到待裁

21、剪多邊形的頂點(diǎn)序列p2、頂點(diǎn)序列數(shù)n、窗口一條邊界參數(shù)xl（假如為矩形窗口的左邊界）；2 賦初值：將頂點(diǎn)序列中的最后一個(gè)頂點(diǎn)賦給前一頂點(diǎn)s；設(shè)置初始標(biāo)志flag：if(s在邊界內(nèi)側(cè))flag=0;else flag=1；設(shè)新的頂點(diǎn)序列數(shù)j=0；3 對(duì)多邊形各頂點(diǎn)進(jìn)行裁剪規(guī)則處理，結(jié)果放入新的多邊形頂點(diǎn)序列q2中： for(對(duì)第一個(gè)頂點(diǎn)直到最后一個(gè)頂點(diǎn)，逐一處理）if(pi在邊界內(nèi)側(cè)) if(flag!=0) flag=0;求交點(diǎn)并放入新的多邊形頂點(diǎn)序列qj中； j+； 將當(dāng)前頂點(diǎn)放入新的多邊形頂點(diǎn)序列qj中：qj=pi； j+； elseif(flag=0) flag=1;求交點(diǎn)并放入新的多邊

22、形頂點(diǎn)序列qj中； j+； 將當(dāng)前頂點(diǎn)賦給s：s=pi； 4 做返回準(zhǔn)備：5 將新的多邊形頂點(diǎn)序列q又逐一放回原多邊形頂點(diǎn)序列p中：p=q；6 將新的多邊形頂點(diǎn)數(shù)j放回原多邊形頂點(diǎn)數(shù)n中：n=j；3.5將畫線、畫圓、線段裁剪和多邊形裁剪綜合在顯示函數(shù)中將各個(gè)算法添加到一個(gè)程序中，使用右鍵菜單的特殊功能實(shí)現(xiàn)畫線、畫圓、線段裁剪和多邊形裁剪，主要是processmenuevents函數(shù)和createglutmenus函數(shù)的編寫。這兩個(gè)函數(shù)的程序代碼如下：void processmenuevents(int option) switch (option) case 1:select = 1; glu

23、tpostredisplay(); break;case 2: select = 2; glutpostredisplay(); break;case 3:select = 3; glutpostredisplay(); break;case 4:select =4; glutpostredisplay(); break;default: break;void createglutmenus() int menu;menu = glutcreatemenu(processmenuevents);glutaddmenuentry(bresenham line,1);glutaddmenuentr

24、y(bresenham circle,2); glutaddmenuentry(liang-barsky cut,3);glutaddmenuentry(sutherland-hodgman cut,4);glutattachmenu(glut_right_button); void display() glclear(gl_color_buffer_bit); wangge();glcolor3f (0.0f, 0.0f, 0.0f); glrectf(rect.xmin,rect.ymin,rect.xmax,rect.ymax);if(select = 1) mydisplay_line();else if(select=2) mydisplay_circle(); else if(select=3) mydisplay_cut();else if(select=4) mydisplay_cutgraphics();glutswapbu