計(jì)算機(jī)圖形學(xué)裁剪算法

1、1、 實(shí)驗(yàn)?zāi)繕?biāo)1.了解Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法的基本思想；2.掌握Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法的算法實(shí)現(xiàn)；二、實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)主要是實(shí)現(xiàn)Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法。Cohen-sutherland線段裁剪算法思想：該算法也稱為編碼算法，首先對(duì)線段的兩個(gè)端點(diǎn)按所在的區(qū)域進(jìn)

2、行分區(qū)編碼，根據(jù)編碼可以迅速地判明全部在窗口內(nèi)的線段和全部在某邊界外側(cè)的線段。只有不屬于這兩種情況的線段，才需要求出線段與窗口邊界的交點(diǎn)，求出交點(diǎn)后，舍去窗外部分。對(duì)剩余部分，把它作為新的線段看待，又從頭開始考慮。兩遍循環(huán)之后，就能確定該線段是部分截留下來，還是全部舍棄。Cohen-sutherland線段裁剪算法步驟：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è)裁剪窗

3、口內(nèi)（包括邊界上）的區(qū)域，四位二進(jìn)制代碼均為0。設(shè)線段的兩個(gè)端點(diǎn)為P1（x1，y1）和P2（x2，y2），根據(jù)上述規(guī)則，可以求出P1和P2所在區(qū)域的分區(qū)代碼C1和C2。2、判別根據(jù)C1和C2的具體值，可以有三種情況：（1）C1=C20，表明兩端點(diǎn)全在窗口內(nèi)，因而整個(gè)線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C20（兩端點(diǎn)代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時(shí)為1，表明兩端點(diǎn)必定處于某一邊界的同一外側(cè)，因而整個(gè)線段全在窗外，應(yīng)予舍棄。（3）不屬于上面兩種情況，均需要求交點(diǎn)。3、求交點(diǎn)假設(shè)算法按照：左、右、下、上邊界的順序進(jìn)行求交處理，對(duì)每一個(gè)邊界求完交點(diǎn)，并相關(guān)處理后，算法轉(zhuǎn)向第2步，

4、重新判斷，如果需要接著進(jìn)入下一邊界的處理。為了規(guī)范算法，令線段的端點(diǎn)P1為外端點(diǎn)，如果不是這樣，就需要P1和P2交換端點(diǎn)。當(dāng)條件(C1&00010)成立時(shí)，表示端點(diǎn)P1位于窗口左邊界外側(cè)，按照求交公式，進(jìn)行對(duì)左邊界的求交運(yùn)算。依次類推，對(duì)位于右、下、上邊界外側(cè)的判別，應(yīng)將條件式中的0001分別改為0010、0100、1000即可。求出交點(diǎn)P后，用P1=P來舍去線段的窗外部分，并對(duì)P1重新編碼得到C1，接下來算法轉(zhuǎn)回第2步繼續(xù)對(duì)其它邊界進(jìn)行判別。Liang-Barsky線段裁剪算法思想：我們知道，一條兩端點(diǎn)為P1（x1，y1）、P2（x2，y2）的線段可以用參數(shù)方程形式表示： x= x1+ u（

5、x2-x1）= x1+ ux y= y1+ u（y2-y1）= y1+ uy 0u1式中，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-xwmin p2= x ，

6、 q2=xwmax-x1 p3=-y ， q3=y1-ywmin p4= y ， q4=ywmax-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)，見圖中所示。上式還告訴我們：1、當(dāng)pk0時(shí)，線段從裁剪邊界延長(zhǎng)線的內(nèi)部延伸到外部；對(duì)于每條直線，可以計(jì)算出參數(shù)u1和u2，該值定義了位于窗口內(nèi)的線段部分：1、u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（pk0），對(duì)這些邊界計(jì)算rk=qk/pk，u2取0和各個(gè)r值

7、之中的最小值。3、如果u1u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點(diǎn)可以由u1和u2計(jì)算出來。Liang-Barsky線段裁剪算法實(shí)現(xiàn)：1、初始化線段交點(diǎn)的參數(shù)：u1=0，u2=1；2、計(jì)算出各個(gè)裁剪邊界的p、q值；3、根據(jù)p、q來判斷：是舍棄線段還是改變交點(diǎn)的參數(shù)。（1） 當(dāng)p0時(shí)，參數(shù)r用于更新u2。 （u2=minu2，rk）（3）如果更新了u1或u2后，使u1u2，則舍棄該線段。（4）當(dāng)p=0且qOpen-cgdemo.sln二、添加菜單1.左側(cè)視圖欄中有三個(gè)視圖：ClassView、ResourceView、FileView，點(diǎn)擊 ResourceView

8、2.展開cgdemo，展開Menu，雙擊IDR_MAINFRAME 3.在右側(cè)窗口菜單欄中找到“基本圖形生成”菜單項(xiàng)，在該菜單項(xiàng)中添加“Cohen-SutherLand線段裁剪算法”，在“Cohen-SutherLand線段裁剪算法”屬性框中找到ID框填：ID_Cohen_SutherLand。在該菜單項(xiàng)中添加“Liang-Barsky線段裁剪算法”，在“Liang-Barsky線段裁剪算法”屬性框中找到ID框填：ID_Liang_Barsky。在該菜單項(xiàng)中添加“SutherLand-Hodgeman多邊形裁剪算法”，在“SutherLand-Hodgeman多邊形裁剪算法”屬性框中找到ID框

9、填：ID_SutherLand_Hodgeman。三、創(chuàng)建、編輯函數(shù) 1.打開cgdemoView.h頭文件，在cgdemoView類枚舉類型成員變量m_drawstyle中添加CUT_CSL,CUT_LB,CUT_SLH。2.給菜單項(xiàng)“Cohen-SutherLand線段裁剪算法”添加命令消息響應(yīng)函數(shù)OnCohenSutherland()在該函數(shù)中添加以下程序代碼。void CcgdemoView:OnCohenSutherland()/ TODO: Add your command handler code herem_drawstyle=CUT_CSL;Invalidate(true);

10、給菜單項(xiàng)“Liang-Barsky線段裁剪算法”添加命令消息響應(yīng)函數(shù)OnLiangBarsky()在該函數(shù)中添加以下程序代碼。void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code herem_drawstyle=CUT_LB;Invalidate(true);給菜單項(xiàng)“SutherLand-Hodgeman多邊形裁剪算法”添加命令消息響應(yīng)函數(shù)OnSutherlandHodgeman()在該函數(shù)中添加以下程序代碼。void CcgdemoView:OnSutherlandHodgeman()/ TODO: Ad

11、d your command handler code herem_drawstyle=CUT_SLH;Invalidate(true); 3.在鼠標(biāo)右鍵按下消息響應(yīng)函數(shù)中添加如下所示代碼。void CcgdemoView:OnRButtonDown(UINT nFlags, CPoint point)switch(m_drawstyle) case CUT_CSL: case CUT_LB: case CUT_SLH: b_inputcomplete=1; Invalidate(true);break; 4. 在鼠標(biāo)移動(dòng)消息響應(yīng)函數(shù)中添加如下所示代碼。void CcgdemoView:OnM

12、ouseMove(UINT nFlags, CPoint point)switch(m_drawstyle) case CUT_CSL: case CUT_LB:5. 在cgdemoView.h頭文件類中分別添加成員函數(shù)void Cohen_SutherLand(CDC* pDC,int x0,int y0,int x1,int y1); 并在cgdemoView.cpp源文件中void Cohen_SutherLand(CDC* pDC,int x0,int y0,int x1,int y1);并在cgdemoView.cpp為其添加編寫的Cohen-SutherLand線段裁剪算法；Lia

13、ng-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法按Cohen-SutherLand線段裁剪算法類似添加代碼。在cgdemoView.cpp源文件中void CcgdemoView:OnDraw(CDC* pDC)添加m_drawstyle分別為選中三種裁剪算法所執(zhí)行的代碼。四、編譯，運(yùn)行。四、實(shí)驗(yàn)遇到的問題及其解決方法（重點(diǎn)）1.在編譯運(yùn)行Cohen-SutherLand線段裁剪算法時(shí)出現(xiàn)如下錯(cuò)誤：error LNK2001: unresolved external symbol public: void _thiscall CcgdemoView:OnCo

14、henSutherland(void)(?OnCohenSutherlandCcgdemoViewQAEXXZ)錯(cuò)誤原因CcgdemoView類的OnCohenSutherland函數(shù)，只有在類中的聲明，沒有找到具體的函數(shù)實(shí)現(xiàn)。菜單項(xiàng)“Cohen-SutherLand線段裁剪算法”添加命令消息響應(yīng)函數(shù)時(shí)更換了Cohen-SutherLand線段裁剪算法的ID名稱，從而產(chǎn)生新的命令相應(yīng)函數(shù)。只是刪去了原來的函數(shù)體，函數(shù)聲明沒有刪除，從而導(dǎo)致錯(cuò)誤。刪除下列函數(shù)聲明部分和消息隊(duì)列部分，編譯成功。afx_msg void OnCohenSutherland();ON_COMMAND(ID_Cohen_

15、SutherLand, &CcgdemoView:OnCohenSutherland) 2.在SutherLand-Hodgeman多邊形裁剪算法遇到的錯(cuò)誤 圖一 圖二圖一所示是在定義窗口上畫多邊形的圖，圖二是畫多邊形后點(diǎn)擊右鍵開始裁剪，通過點(diǎn)擊右鍵發(fā)現(xiàn)沒有裁剪多邊形，程序有誤。pDC-Rectangle(300,100,500,300); pDC-Rectangle(500,300,300,100);這兩個(gè)畫矩形是一樣的，通過MSDN查找Rectangle的用法發(fā)現(xiàn)，它的坐標(biāo)單位都是邏輯單位，邏輯坐標(biāo)是獨(dú)立于設(shè)備的，它與設(shè)備點(diǎn)的大小無(wú)關(guān)。在調(diào)用時(shí)Windows將GDI函數(shù)中指定的邏輯坐標(biāo)映射

16、為設(shè)備坐標(biāo)，所以，兩個(gè)畫矩形都是一樣的。Clip_Polygon(CDC* pDC,int xmin,int ymin,int xmax,int ymax)SutherLand-Hodgeman多邊形裁剪算法中要滿足xmin小于xmax，ymin小于ymax。由于該pDC-Rectangle(500,300,300,100)畫矩形不滿足條件，導(dǎo)致最終多邊形裁剪有誤，通過改正畫矩形參數(shù)值，程序運(yùn)行成功。五、實(shí)驗(yàn)結(jié)論和收獲通過Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法，使我了解到了Cohen-SutherLand線段裁剪算法、Liang-