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

1、<p><b>　　河南理工大學(xué)</b></p><p><b>　　萬方科技學(xué)院</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2011 — 2012學(xué)年第二學(xué)期</p><p>　　課程名稱 計(jì)算機(jī)圖形學(xué) <

2、/p><p>　　設(shè)計(jì)題目 計(jì)算機(jī)圖形學(xué)基本算法 </p><p>　　演示系統(tǒng)設(shè)計(jì) </p><p>　　學(xué)生姓名 </p><p>　　學(xué) 號(hào) </p><p>　　專業(yè)班級 網(wǎng)絡(luò)11升—1班 </p><p&g

3、t;　　指導(dǎo)教師 徐 文 鵬 </p><p>　　2012 年 5 月 28 日</p><p><b>　　目 錄</b></p><p>　　第1章 設(shè)計(jì)內(nèi)容與要求1</p><p>　　1.1總體目標(biāo)和要求1</p><p>　　1.2內(nèi)容與要求 1&l

4、t;/p><p>　　1.2.1 直線的生成1</p><p>　　1.2.2 圓弧的生成1</p><p>　　1.2.3 線段裁剪2</p><p>　　1.2.4 多邊形裁剪2</p><p>　　1.2.5 綜合2</p><p>　　第2章 總體設(shè)計(jì)3</p>&

5、lt;p>　　2.1 Bresenham算法畫直線3</p><p>　　2.1.1 Bresenham算法畫直線理論基礎(chǔ)3</p><p>　　2.1.2 Bresenham算法畫直線原理3</p><p>　　2.2 Bresenham算法畫圓4</p><p>　　2.2.1 Bresenham算法畫圓理論基礎(chǔ)4<

6、/p><p>　　2.2.2 Bresenham算法畫圓原理5</p><p>　　2.3 梁友棟-Barsky算法進(jìn)行線段裁剪6</p><p>　　2.3.1梁友棟-Barsky算法進(jìn)行線段裁剪基本原理6</p><p>　　2.4 Sutherland-Hodgman算法進(jìn)行多邊形裁剪8</p><p>　　

7、2.4.1 Sutherland—Hodgman多邊形裁剪算法思想8</p><p>　　2.4.2 點(diǎn)在邊界內(nèi)側(cè)的判斷方法8</p><p>　　2.4.4 Sutherland-Hodgeman多邊形裁剪算法特點(diǎn)8</p><p>　　第3章 詳細(xì)設(shè)計(jì)9</p><p>　　3.1 Bresenham算法畫直線9</p&g

8、t;<p>　　3.1.1 Bresenham 算法畫線算法具體實(shí)現(xiàn)過程9</p><p>　　3.2 Bresenham算法畫圓9</p><p>　　3.2.1 Bresenham 算法畫圓核心代碼9</p><p>　　3.3 梁友棟-Barsky算法進(jìn)行線段裁剪10</p><p>　　3.3.1梁友棟-Bars

9、ky算法推導(dǎo)過程10</p><p>　　3.3.2梁友棟-Barsky算法進(jìn)行線段裁剪的步驟11</p><p>　　3.4 Sutherland-Hodgman算法進(jìn)行多邊形裁剪11</p><p>　　3.4.1 Sutherland—Hodgman多邊形裁剪算法步驟11</p><p>　　3.5將畫線、畫圓、線段裁剪和多邊形

10、裁剪綜合12</p><p>　　第4章 功能實(shí)現(xiàn)14</p><p>　　4.1用Bresenham算法畫線測試結(jié)果14</p><p>　　4.2用Bresenham算法畫圓測試結(jié)果14</p><p>　　4.3梁友棟-Barsky算法進(jìn)行線段裁剪測試結(jié)果15</p><p>　　4.4 Sutherl

11、and-Hodgman算法進(jìn)行多邊形裁剪測試結(jié)果16</p><p>　　4.5將四種算法綜合測試結(jié)果16</p><p><b>　　第5章 總結(jié)17</b></p><p><b>　　參考文獻(xiàn)18</b></p><p><b>　　設(shè)計(jì)內(nèi)容與要求</b><

12、;/p><p><b>　　總體目標(biāo)和要求</b></p><p>　　目標(biāo)：以圖形學(xué)算法為目標(biāo)，深入研究。繼而策劃、設(shè)計(jì)并實(shí)現(xiàn)一個(gè)能夠表現(xiàn)計(jì)算機(jī)圖形學(xué)算法原理的或完整過程的演示系統(tǒng)，并能從某些方面作出評價(jià)和改進(jìn)意見。通過完成一個(gè)完整程序，經(jīng)歷策劃、設(shè)計(jì)、開發(fā)、測試、總結(jié)和驗(yàn)收各階段，達(dá)到：</p><p>　　鞏固和實(shí)踐計(jì)算機(jī)圖形學(xué)課程中的理論和

13、算法；</p><p>　　學(xué)習(xí)表現(xiàn)計(jì)算機(jī)圖形學(xué)算法的技巧；</p><p>　　培養(yǎng)認(rèn)真學(xué)習(xí)、積極探索的精神。</p><p>　　總體要求：策劃、設(shè)計(jì)并實(shí)現(xiàn)一個(gè)能夠充分表現(xiàn)圖形學(xué)算法的演示系統(tǒng)，界面要求美觀大方，能清楚地演示算法執(zhí)行的每一個(gè)步驟。</p><p>　　開發(fā)環(huán)境：Viusal C++ 6.0，VC2005或其他你認(rèn)為比較熟悉

14、的環(huán)境。</p><p><b>　　內(nèi)容與要求</b></p><p><b>　　實(shí)驗(yàn)分為五項(xiàng)內(nèi)容。</b></p><p>　　1.2.1 直線的生成</p><p>　　內(nèi)容：用Bresenham算法畫直線</p><p><b>　　要求：</b&g

15、t;</p><p>　　鼠標(biāo)移動(dòng)時(shí)，顯示鼠標(biāo)當(dāng)前位置</p><p>　　顯示判別式的計(jì)算過程和下一點(diǎn)的選擇策略</p><p><b>　　記錄生成點(diǎn)的坐標(biāo)</b></p><p>　　圖形生成過程可以重復(fù)進(jìn)行</p><p>　　1.2.2 圓弧的生成</p><p>

16、;　　內(nèi)容：用Bresenham算法畫圓</p><p><b>　　要求：</b></p><p>　　鼠標(biāo)移動(dòng)時(shí)，顯示鼠標(biāo)當(dāng)前位置</p><p>　　顯示判別式的計(jì)算過程和下一點(diǎn)的選擇策略</p><p><b>　　記錄生成點(diǎn)的坐標(biāo)</b></p><p>　　圖形生

17、成過程可以重復(fù)進(jìn)行</p><p><b>　　橡皮筋技術(shù)實(shí)現(xiàn)</b></p><p>　　1.2.3 線段裁剪</p><p>　　內(nèi)容：用梁友棟-Barsky算法進(jìn)行線段裁剪</p><p><b>　　要求：</b></p><p>　　對于線段裁剪，線段被窗口的四條邊

18、裁剪的過程要顯示出來</p><p>　　用橡皮筋的形式輸入剪裁線段</p><p>　　1.2.4 多邊形裁剪</p><p>　　內(nèi)容：用Sutherland-Hodgman算法進(jìn)行多邊形裁剪</p><p><b>　　要求：</b></p><p>　　裁剪過程需先輸入一多邊形，然后用窗口

19、四邊裁剪的過程中要顯示頂點(diǎn)增刪過程。</p><p>　　用橡皮筋的形式輸入剪裁線段</p><p><b>　　1.2.5 綜合</b></p><p>　　內(nèi)容：把前四次的實(shí)驗(yàn)內(nèi)容整合到一起</p><p><b>　　要求：</b></p><p><b>　

20、　第2章 總體設(shè)計(jì)</b></p><p>　　2.1 Bresenham算法畫直線</p><p>　　2.1.1 Bresenham算法畫直線理論基礎(chǔ)</p><p>　　計(jì)算機(jī)是如何畫直線的？簡單來說，就是過各行各列像素中心構(gòu)造一組虛擬的網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算各直線與歌垂直網(wǎng)格線的交點(diǎn)，然后確定各列像素中與此交點(diǎn)最近的像素。真實(shí)的直線

21、是連續(xù)的，但我們的計(jì)算機(jī)顯示的精度有限，不可能真正顯示連續(xù)的直線，于是我們用一系列離散化后的點(diǎn)（像素）來近似表現(xiàn)這條直線。</p><p>　　2.1.2 Bresenham算法畫直線原理</p><p>　　接下來的問題就是如何盡可能高效地找到這些離散的點(diǎn)，Bresenham直線算法就是一個(gè)非常不錯(cuò)的算法。</p><p>　　Bresenham直線算法是用來描繪

22、由兩點(diǎn)所決定的直線的算法，它會(huì)算出一條線段在 n 維光柵上最接近的點(diǎn)。這個(gè)算法只會(huì)用到較為快速的整數(shù)加法、減法和位元移位，常用于繪制電腦畫面中的直線。是計(jì)算機(jī)圖形學(xué)中最先發(fā)展出來的算法。</p><p>　　這個(gè)算法的流程圖如下：</p><p>　　可以看到，算法其實(shí)只考慮了斜率在 0 ~ 1 之間的直線，也就是與 x 軸夾角在 0 度到 45 度的直線。只要解決了這類直線的畫法，其它角

23、度的直線的繪制全部可以通過簡單的坐標(biāo)變換來實(shí)現(xiàn)。</p><p>　　2.2 Bresenham算法畫圓</p><p>　　2.2.1 Bresenham算法畫圓理論基礎(chǔ)</p><p>　　Bresenham畫圓算法與Bresenham 直線算法一樣，其基本的方法是利用判別變量來判斷選擇最近的像素點(diǎn)，判別變量的數(shù)值僅僅用一些加、減和移位運(yùn)算就可以計(jì)算出來。為了

24、簡便起見，考慮一個(gè)圓心在坐標(biāo)原點(diǎn)的圓，而且只計(jì)算八分圓周上的點(diǎn)，其余圓周上的點(diǎn)利用對稱性就可得到。</p><p>　　為什么只計(jì)算八分圓周上的點(diǎn)就可以了呢？和上面的直線算法類似，圓也有一個(gè)“八對稱性”，如下圖所示。 </p><p>　　顯然，我們只需要知道了圓上的一個(gè)點(diǎn)的坐標(biāo) (x, y) ，利用八對稱性，我們馬上就能得到另外七個(gè)對稱點(diǎn)的坐標(biāo)。 </p><p>

25、;　　2.2.2 Bresenham算法畫圓原理</p><p>　　和直線算法類似，Bresenham畫圓算法也是用一系列離散的點(diǎn)來近似描述一個(gè)圓，如下圖。 </p><p>　　Bresenham畫圓算法的流程圖如下。 </p><p>　　可以看到，與畫線算法相比，畫圓的循環(huán)中用到了整數(shù)的乘法，相對復(fù)雜了一些。 </p><p>　　

26、2.3 梁友棟-Barsky算法進(jìn)行線段裁剪</p><p>　　2.3.1梁友棟-Barsky算法進(jìn)行線段裁剪基本原理</p><p>　　我們知道，一條兩端點(diǎn)為P1（x1，y1）、P2（x2，y2）的線段可以用參數(shù)方程形式表示：</p><p>　　x= x1+ u·（x2-x1）= x1+ u·Δx，y= y1+ u·（y2-y

27、1）= y1+ u·Δy　式中，Δx=x2-x1，Δy=y2-y1，參數(shù)u在0～1之間取值，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)，那么下式成立：xwmin≤x1+ u·Δx≤xwmax，ywmin≤y1+ u·

28、;Δy≤ywmax</p><p>　　這四個(gè)不等式可以表示為：u·pk ≤qk ， k=1，2，3，4</p><p>　　其中，p、q定義為p1=-Δx， q1=x1-xwmin</p><p>　　p2= Δx， q2=xwmax-x1</p><p>　　p3=-Δy， q3=y1-ywmin</p><

29、p>　　p4= Δy， q4=ywmax-y1</p><p>　　可以知道：任何平行于窗口某邊界的直線，其pk=0，k值對應(yīng)于相應(yīng)的邊界（k=1，2，3，4對應(yīng)于左、右、下、上邊界）。如果還滿足qk<0，則線段完全在邊界外，應(yīng)舍棄該線段。如果pk=0并且qk≥0，則線段平行于窗口某邊界并在窗口內(nèi)，見圖中所示。</p><p>　　1、當(dāng)pk<0時(shí)，線段從裁剪邊界延長線的

30、外部延伸到內(nèi)部；</p><p>　　2、當(dāng)pk>0時(shí)，線段從裁剪邊界延長線的內(nèi)部延伸到外部；</p><p>　　例如，當(dāng)Δx≥0時(shí)，對于左邊界p1<0（p1=-Δx），線段從左邊界的外部到內(nèi)部；對于右邊界p2>0（p2=Δx），線段從右邊界的內(nèi)部到外部。</p><p>　　當(dāng)Δy<0時(shí)，對于下邊界p3>0（p3=-Δy），線段從下

31、邊界的內(nèi)部到外部；對于上邊界p4<0（p4=Δy），線段從上邊界的外部到內(nèi)部。</p><p>　　當(dāng)pK≠0時(shí)，可以計(jì)算出參數(shù)u的值，它對應(yīng)于無限延伸的直線與延伸的窗口邊界k的交點(diǎn)，即：</p><p>　　對于每條直線，可以計(jì)算出參數(shù)u1和u2，該值定義了位于窗口內(nèi)的線段部分：</p><p>　　1、u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（pk<

32、;0），對這些邊界計(jì)算rk=qk/pk，u1取0和各個(gè)r值之中的最大值。</p><p>　　2、u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（pk>0），對這些邊界計(jì)算rk=qk/pk，u2取0和各個(gè)r值之中的最小值。</p><p>　　3、如果u1>u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點(diǎn)可以由u1和u2計(jì)算出來。</p><

33、p>　　2.4 Sutherland-Hodgman算法進(jìn)行多邊形裁剪</p><p>　　2.4.1 Sutherland—Hodgman多邊形裁剪算法思想</p><p>　　該算法的基本思想是每次用窗口的一條邊界及其延長線來裁剪多邊形的各邊。多邊形通常由它的頂點(diǎn)序列來表示，經(jīng)過裁剪規(guī)則針對某條邊界裁剪后，結(jié)果形成新的頂點(diǎn)序列，又留待下條邊界進(jìn)行裁剪，直到窗口的所有邊界都裁剪完

34、畢，算法形成最后的頂點(diǎn)序列，才是結(jié)果多邊形（它可能構(gòu)成一個(gè)或多個(gè)多邊形）。當(dāng)多邊形一個(gè)頂點(diǎn)Pi相對于窗口某條邊界及其延長線進(jìn)行剪裁時(shí)，不外乎下列四種情況（即裁剪規(guī)則）：</p><p>　　1、頂點(diǎn)Pi在內(nèi)側(cè)，前一頂點(diǎn)Pi-1也在內(nèi)側(cè)，則將Pi納入新的頂點(diǎn)序列；</p><p>　　2、頂點(diǎn)Pi在內(nèi)側(cè)，前一頂點(diǎn)Pi-1在外側(cè)，則先求交點(diǎn)Q，再將Q、Pi依次納入新的頂點(diǎn)序列；</p&g

35、t;<p>　　3、頂點(diǎn)Pi在外側(cè)，前一頂點(diǎn)Pi-1在內(nèi)側(cè)，則先求交點(diǎn)Q，再將Q納入新的頂點(diǎn)序列；</p><p>　　4、頂點(diǎn)Pi與前一頂點(diǎn)Pi-1均在外側(cè)，則頂點(diǎn)序列中不增加新的頂點(diǎn)。</p><p>　　2.4.2 點(diǎn)在邊界內(nèi)側(cè)的判斷方法</p><p>　　為了判斷點(diǎn)是否在邊界內(nèi)側(cè)可用坐標(biāo)比較法和更通用的向量叉積符號(hào)判別法。</p>

36、;<p><b>　　1、坐標(biāo)比較法</b></p><p>　　將點(diǎn)的某個(gè)方向分量與邊界進(jìn)行比較。例如，判斷某點(diǎn)是否在下邊界內(nèi)側(cè),用條件判別式： if(p[i][1]>=ymin) 即可。</p><p><b>　　2、向量叉積法</b></p><p>　　為簡單計(jì)，測試點(diǎn)表示為P點(diǎn)。假設(shè)窗口邊界

37、方向?yàn)轫槙r(shí)針，如圖中所示，對于其中任一邊界向量，從向量起點(diǎn)A向終點(diǎn)B看過去：如果被測試點(diǎn)P在該邊界線右邊(即內(nèi)側(cè))，AB×AP的方向與X-Y平面垂直并指向屏幕里面，即右手坐標(biāo)系中Z軸的負(fù)方向。反過來，如果P在該邊界線的左邊(即外側(cè))，這時(shí)AB×AP的方向與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)}，

38、向量AP={(x-xA)，(y-yA)}，那么AB×AP的方向可由下式的符號(hào)來確定：V=(x[B]-x[A])*(y-y[A])- (x-x[A])*(y[B]-y[A])) </p><p>　　因此，當(dāng)V≤0時(shí)，P在邊界線內(nèi)側(cè)；而V>0時(shí)，P在邊界線外側(cè)。</p><p>　　2.4.4 Sutherland-Hodgeman多邊形裁剪算法特點(diǎn)</p>

39、<p>　　Sutherland－Hodgeman多邊形裁剪算法具有一般性，被裁剪多邊形可以是任意凸多邊形或凹多邊形，裁剪窗口不局限于矩形，可以是任意凸多邊形。</p><p>　　上面的算法是多邊形相對窗口的一條邊界進(jìn)行裁剪的實(shí)現(xiàn)，對于窗口的每一條邊界依次調(diào)用該算法程序，并將前一次裁剪的結(jié)果多邊形作為下一次裁剪時(shí)的被裁剪多邊形，即可得到完整的多邊形裁剪程序。</p><p>&

40、lt;b>　　第3章 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 Bresenham算法畫直線</p><p>　　3.1.1 Bresenham 算法畫線算法具體實(shí)現(xiàn)過程</p><p>　　1、畫點(diǎn)(x1, y2); dx=x2-x1; dy=y2-y1；計(jì)算誤差初值P1=2dy-dx; i=1；</p><p>　

41、　2、求直線的下一點(diǎn)位置：</p><p>　　xi+1=xi+1；</p><p>　　if Pi>0 則yi+1=yi+1；</p><p>　　否則yi+1=yi；</p><p>　　3、畫點(diǎn)（xi+1, yi-1）；</p><p>　　4、求下一個(gè)誤差Pi+1；</p><p>

42、;　　if Pi>0 則Pi+1=Pi+2dy-2dx;</p><p>　　否則Pi+1=Pi+2dy；</p><p>　　5、i=i+1; if i<dx+1則轉(zhuǎn)2；否則end。</p><p>　　由上述算法思想編制算法程序。這個(gè)程序適用于所有8個(gè)方向的直線的生成。程序畫出一條端點(diǎn)為（x1, y1）和（x2, y2）的直線。其中變量的含義是：P是

43、誤差；const1和const2，是誤差的逐點(diǎn)變化量；inc是y的單位遞變量，值為1或-1；tmp是用作象限變換時(shí)的臨時(shí)變量。程序以判斷|dx|>|dy|為分支，并分別將2a, 3a象限的直線和3b, 4b象限的直線變換到1a, 4a和2b, 1b方向去，以求得程序處理的簡潔。</p><p>　　3.2 Bresenham算法畫圓</p><p>　　3.2.1 Bresenha

44、m 算法畫圓核心代碼</p><p>　　根據(jù)Bresenham算法思想編寫程序代碼，在Bresenham算法畫線的基礎(chǔ)上畫圓，程序代碼如下：</p><p>　　void BresenhamCircle(int x0,int y0,int R)//,int color) </p><p>　　{ int x,y,d;</p><p>

45、;<b>　　x=0;y=R;</b></p><p><b>　　d=3-2*R;</b></p><p>　　while(x<y) {glColor3f (0.0f, 1.0f, 0.0f); </p><p>　　putpixel(x0+x,y0+y);</p><p>　　putpix

46、el(x0+x,y0-y);</p><p>　　putpixel(x0-x,y0+y);</p><p>　　putpixel(x0-x,y0-y);</p><p>　　putpixel(x0+y,y0+x);</p><p>　　putpixel(x0+y,y0-x);</p><p>　　putpixel(x0

47、-y,y0+x);</p><p>　　putpixel(x0-y,y0-x);</p><p>　　if(d<0) d=d+4*x+6;</p><p>　　else{d=d+4*(x-y)+10;y=y-1; }</p><p><b>　　x++; </b></p><p><b

48、>　　}</b></p><p><b>　　}</b></p><p>　　3.3 梁友棟-Barsky算法進(jìn)行線段裁剪</p><p>　　3.3.1梁友棟-Barsky算法推導(dǎo)過程</p><p>　　情形一   pk=0</p><p><b&

49、gt;　　p1＝p2＝0</b></p><p>　　若q1<0或q2<0，則可刪除直線段 </p><p>　　若q1>=0且q2>=0,則進(jìn)一步判斷 </p><p>　　u=qk/pk（k=3,4） </p><p>　　令  u1=max(0,u|pk<0)

50、</p><p>　　u2=min(1,u|pk>0)</p><p>　　若u1>u2,則可刪除直線段</p><p>　　若u1<=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見端點(diǎn)。</p><p>　　p3＝p4＝0 </p><p>　　若q3<0或q4<0，則可刪除直

51、線段</p><p>　　若q3>=0且q4>=0,則進(jìn)一步判斷</p><p>　　u=qk/pk（k=1,2）</p><p>　　令  u1=max(0,u|pk<0)</p><p>　　u2=min(1,u|pk>0)</p><p>　　若u1>u2,則可刪

52、除直線段</p><p>　　若u1<=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見端點(diǎn)。</p><p>　　情形二   pk不為0</p><p>　　u=qk/pk（k=1,2,3,4）</p><p>　　令 u1=max(0,u|pk<0,u|pk<0)</p><p

53、>　　u2=min(1,u|pk>0, u|pk>0)</p><p>　　若u1>u2,則可刪除直線段</p><p>　　若u1<=u2,將u1,u2代入直線方程，得到直線段的兩個(gè)可見端點(diǎn)。</p><p>　　3.3.2梁友棟-Barsky算法進(jìn)行線段裁剪的步驟</p><p>　　輸入直線段的兩端點(diǎn)坐標(biāo)以

54、及窗口的四條邊界坐標(biāo)。</p><p>　　若Δx=0，則p1=p2=0。進(jìn)一步判斷是否滿足q1<0或q2<0，若滿足，則該直線段不在窗口內(nèi)，轉(zhuǎn)(7)。否則，滿足q1>0且q2>0，則進(jìn)一步計(jì)算u1和u2。轉(zhuǎn)(5)。 </p><p>　　若Δy=0，則p3=p4=0。進(jìn)一步判斷是否滿足q3<0或q4<0，若滿足，則該直線段不在窗口內(nèi)，轉(zhuǎn)(7)。否則，

55、滿足q1>0且q2>0，則進(jìn)一步計(jì)算u1和u2。轉(zhuǎn)(5)。</p><p>　　若上述兩條均不滿足,則有pk≠0(k=1,2,3,4)。此時(shí)計(jì)算u1和u2。</p><p>　　求得u1和u2后,進(jìn)行判斷：若u1>u2,則直線段在窗口外,轉(zhuǎn)(7)。若u1<u2,利用直線的參數(shù)方程求得直線段在窗口內(nèi)的兩端點(diǎn)坐標(biāo)。</p><p>　　利用直線的

56、掃描轉(zhuǎn)換算法繪制在窗口內(nèi)的直線段。</p><p><b>　　算法結(jié)束。</b></p><p>　　3.4 Sutherland-Hodgman算法進(jìn)行多邊形裁剪</p><p>　　3.4.1 Sutherland—Hodgman多邊形裁剪算法步驟</p><p>　　考慮多邊形相對于一條邊界及其延長線進(jìn)行裁剪的

57、算法：</p><p>　　從主函數(shù)得到待裁剪多邊形的頂點(diǎn)序列P[][2]、頂點(diǎn)序列數(shù)n、窗口一條邊界參數(shù)xl（假如為矩形窗口的左邊界）；</p><p>　　賦初值：將頂點(diǎn)序列中的最后一個(gè)頂點(diǎn)賦給前一頂點(diǎn)S；</p><p>　　設(shè)置初始標(biāo)志flag：</p><p>　　if(S在邊界內(nèi)側(cè))flag=0;</p><p

58、>　　else flag=1；</p><p>　　設(shè)新的頂點(diǎn)序列數(shù)j=0；</p><p>　　對多邊形各頂點(diǎn)進(jìn)行裁剪規(guī)則處理，結(jié)果放入新的多邊形頂點(diǎn)序列Q[][2]中： </p><p>　　for(對第一個(gè)頂點(diǎn)直到最后一個(gè)頂點(diǎn)，逐一處理）</p><p><b>　　{</b></p><

59、;p>　　if(Pi在邊界內(nèi)側(cè))</p><p><b>　　{</b></p><p>　　if(flag!=0)</p><p><b>　　{</b></p><p><b>　　flag=0;</b></p><p>　　求交點(diǎn)并放入新的多

60、邊形頂點(diǎn)序列Qj中；</p><p><b>　　j++；</b></p><p><b>　　}</b></p><p>　　將當(dāng)前頂點(diǎn)放入新的多邊形頂點(diǎn)序列Qj中：Qj=Pi；</p><p><b>　　j++；</b></p><p><b

61、>　　}</b></p><p><b>　　Else</b></p><p><b>　　{</b></p><p>　　if(flag==0)</p><p><b>　　{</b></p><p><b>　　flag=

62、1;</b></p><p>　　求交點(diǎn)并放入新的多邊形頂點(diǎn)序列Qj中；</p><p><b>　　j++；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　將當(dāng)前頂點(diǎn)賦給S：S=

63、Pi；</p><p><b>　　}</b></p><p><b>　　做返回準(zhǔn)備：</b></p><p>　　將新的多邊形頂點(diǎn)序列Q又逐一放回原多邊形頂點(diǎn)序列P中：P=Q；</p><p>　　將新的多邊形頂點(diǎn)數(shù)j放回原多邊形頂點(diǎn)數(shù)n中：n=j；</p><p>　　

64、3.5將畫線、畫圓、線段裁剪和多邊形裁剪綜合</p><p>　　在顯示函數(shù)中將各個(gè)算法添加到一個(gè)程序中，使用右鍵菜單的特殊功能實(shí)現(xiàn)畫線、畫圓、線段裁剪和多邊形裁剪，主要是processMenuEvents函數(shù)和createGLUTMenus函數(shù)的編寫。這兩個(gè)函數(shù)的程序代碼如下：</p><p>　　void processMenuEvents(int option)

65、 </p><p>　　{switch (option) { </p><p>　　case 1:select = 1;</p><p>　　glutPostRedisplay();</p><p><b>　　break;</b></p><p>　　case 2:

66、select = 2;</p><p>　　glutPostRedisplay();</p><p><b>　　break;</b></p><p>　　case 3:select = 3;</p><p>　　glutPostRedisplay();</p><p><b>　　br

67、eak;</b></p><p>　　case 4:select =4;</p><p>　　glutPostRedisplay();</p><p><b>　　break;</b></p><p>　　default: break;}</p><p><b>　　}<

68、;/b></p><p>　　void createGLUTMenus() </p><p>　　{int menu;</p><p>　　menu = glutCreateMenu(processMenuEvents);</p><p>　　glutAddMenuEntry("Bresenham Line&qu

69、ot;,1);</p><p>　　glutAddMenuEntry("Bresenham Circle",2);</p><p>　　glutAddMenuEntry("Liang-Barsky Cut",3);</p><p>　　glutAddMenuEntry("Sutherland-Hodgman Cut&

70、quot;,4);</p><p>　　glutAttachMenu(GLUT_RIGHT_BUTTON);</p><p>　　} </p><p>　　void Display() </p><p>　　{glClear(GL_COLOR_BUFFER_BIT);<

71、/p><p><b>　　Wangge();</b></p><p>　　glColor3f (0.0f, 0.0f, 0.0f); </p><p>　　glRectf(rect.xmin,rect.ymin,rect.xmax,rect.ymax);</p><p>　　if(select == 1) myDisplay

72、_Line();</p><p>　　else if(select==2) myDisplay_Circle();</p><p>　　else if(select==3) myDisplay_cut();</p><p>　　else if(select==4) myDisplay_cutGraphics();</p><p>　　glut

73、SwapBuffers();</p><p>　　glFlush();</p><p><b>　　}</b></p><p><b>　　第4章 功能實(shí)現(xiàn)</b></p><p>　　4.1用Bresenham算法畫線測試結(jié)果</p><p>　　打開vc++6.0,加載畫

74、線代碼并運(yùn)行，點(diǎn)擊畫線并輸入數(shù)據(jù)：</p><p>　　然后點(diǎn)擊Bresenham算法，就得到結(jié)果：</p><p>　　4.2用Bresenham算法畫圓測試結(jié)果</p><p>　　打開vc++6.0,加載畫圓代碼并運(yùn)行，然后測試結(jié)果如下：</p><p>　　4.3梁友棟-Barsky算法進(jìn)行線段裁剪測試結(jié)果</p>&l

75、t;p>　　打開vc++6.0,加載畫圓代碼并運(yùn)行，先點(diǎn)擊畫線：</p><p>　　然后點(diǎn)擊裁剪得到如下結(jié)果：</p><p>　　4.4 Sutherland-Hodgman算法進(jìn)行多邊形裁剪測試結(jié)果</p><p>　　Sutherland-Hodgman算法中來實(shí)現(xiàn)多邊形的裁剪，不同圖形裁剪的結(jié)果如圖所示。</p><p>　　

76、4.5將四種算法綜合測試結(jié)果</p><p>　　運(yùn)行該程序后，出現(xiàn)主界面，然后單擊鼠標(biāo)右鍵，出現(xiàn)4個(gè)菜單項(xiàng)，分別是Bresenham Line、Bresenham Circle、Liang-Barsky Cut、Sutherland-Hodgman Cut。單擊Bresenham Line項(xiàng)可以畫線，單擊Bresenham Circle項(xiàng)可以畫圓，單擊Liang-Barsky Cut項(xiàng)可以進(jìn)行線段裁剪，單擊Su

77、therland-Hodgman Cut項(xiàng)可以進(jìn)行多邊形裁剪。</p><p><b>　　第5章 總結(jié)</b></p><p>　　通過本次課程設(shè)計(jì)，使我進(jìn)一步深入了解了計(jì)算機(jī)圖形學(xué)和對vc的使用，也提高了我對程序的理解和調(diào)試能力。程序的編寫也經(jīng)歷了問題的提出及分析，簡化，再簡化，最終編程實(shí)現(xiàn)的過程。該設(shè)計(jì)過程中遇到了很多的問題，有些問題任然還沒有解決，程序也存在著

78、很大不足，但通過自己動(dòng)手，真正提高了我的動(dòng)手能力。同時(shí)也得到了同學(xué)的幫助使我學(xué)到了很多東西。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　【1】唐榮錫，等。計(jì)算機(jī)圖形學(xué)教程（修訂版）【M】北京：科學(xué)出版社，2000.</p><p>　　【2】唐澤圣，等。計(jì)算機(jī)圖形學(xué)基礎(chǔ)【M】北京：清華大學(xué)出版社，1995.</p&