編碼裁減法的實(shí)現(xiàn).doc

編碼裁減法的實(shí)現(xiàn)一、 實(shí)驗(yàn)原理當(dāng)用戶在平面上定義了一個(gè)窗口后，總是希望把落在窗口內(nèi)的部分圖形映象到視圖區(qū)中，而把窗口以外的圖形運(yùn)用裁減方法統(tǒng)統(tǒng)裁掉，不予輸出。這種平面上的圖形受該平面上的矩形窗口的裁減稱為二維裁減。裁減的基本目的是判斷圖形元素是否在所考慮的區(qū)域內(nèi)。如果在區(qū)域內(nèi)，則進(jìn)一步求出在區(qū)域內(nèi)的那一部分。因此裁減處理包含兩部分內(nèi)容：（1） 點(diǎn)在區(qū)域內(nèi)外的判斷，即看點(diǎn)是否滿足：；（2） 計(jì)算圖形元素與區(qū)域邊界的交點(diǎn)。編碼裁減法是一種基本的二維裁減算法。它是用區(qū)域檢查的辦法有效的識(shí)別可以直接接受或直接舍棄的線段，只有不屬于這兩種情況的線段才需要計(jì)算交點(diǎn)。二、 基本算法與實(shí)現(xiàn)如圖一所示，其中為窗口的四條邊界。任何以條線段的端點(diǎn)，根據(jù)其坐標(biāo)所在的區(qū)域都可以賦予4位二進(jìn)制代碼。設(shè)最左邊的位為第一位，則其含義如下：第一位為1，表示端點(diǎn)在上方；第二位為1，表示端點(diǎn)在下方；第三位為1，表示端點(diǎn)在右方；第四位為1，表示端點(diǎn)在左方；否則相應(yīng)位置零。各區(qū)域編碼如圖一所示。 1001（9） 1000（8） 1010（A） 0001（1） 0000 0010（2） 0101（5） 0100（4） 0110（6） 圖一由圖可知，如果線段兩個(gè)端點(diǎn)的4位編碼全為零，則此線段全部在窗口內(nèi)，可直接接收（accept=1）；如果對(duì)線段的兩個(gè)端點(diǎn)的4位編碼進(jìn)行邏輯與（按位乘）運(yùn)算，結(jié)果為非零，則此線段全部在窗口之外，可直接舍棄；否則，這條線段既不能直接接受，也不能直接舍棄，它可能與窗口相交。此時(shí)，需要對(duì)線段進(jìn)行再分割，即找到與窗口一個(gè)邊框的交點(diǎn)。根據(jù)交點(diǎn)位置，也賦予4位代碼，并對(duì)分割后的線段進(jìn)行檢查：或者接受，或者舍棄，或者再次進(jìn)行分割。重復(fù)這一過(guò)程，直到全部線段均被舍棄或被接受為止。設(shè)兩端分別為，核心程序?qū)崿F(xiàn)如下（源程序見附錄）：while(done!=1) c1=0,c2=0; /初始編碼置零 if(x1XR) c1=c1|2; /在右方，第三位置1 if(y1YT) c1=c1|8; / 在上方，第一位置1 if(x2XR) c2=c2|2; /類似 if(y2YT) c2=c2|8; if(c1&c2)!=0) done=1; /線段在窗口之外，舍棄 else if(c1=0 & c2=0) done=1; accept=1; /均在窗口內(nèi) else if(c1=0) /在窗口內(nèi) xchange=x1; x1=x2; x2=xchange; /交換點(diǎn)坐標(biāo)及編碼 ychange=y1; y1=y2; y2=ychange; c=c1; c1=c2; c2=c; if(c1&4)=4) /求交點(diǎn)，點(diǎn)在窗口之下 x=x1-(y1-YB)*(x1-x2)/(y1-y2); y=YB; else if (c1&8)=8) /點(diǎn)在窗口之上 x=x1-(y1-YT)*(x1-x2)/(y1-y2); y=YT; else if( (c1&1)=1) /點(diǎn)在窗口之左 x=XL; y=y1-(x1-XL)*(y1-y2)/(x1-x2); else if(c1&2)=2) /點(diǎn)在窗口之右 x=XR; y=y1-(x1-XR)*(y1-y2)/(x1-x2); x1=x;y1=y; /else /while三、 算法流程圖開始 初始化done=0,accept=0 求編碼，編碼 （邏輯與）=0 否 丟棄done=1 是且， 是 接受done=1，accept=1 否 ？ 否是在窗口內(nèi) 與交換 求交 在窗口之 上 下 左 右 Y1=YT，X1= Y1=YB，X1= X1=XL,Y1= X1=XR,Y1=否 done=1 ? 是 accept=1 ? 否 是 顯示- 退出四、 實(shí)驗(yàn)結(jié)果 兩端點(diǎn)坐標(biāo)分別為（5，2），（260，200）的直線裁減前后的圖形如下：兩端點(diǎn)坐標(biāo)分別為（30，50），（160，250）的直線裁減前后的圖形如下：五、 總結(jié) 通過(guò)對(duì)這次計(jì)算機(jī)圖形學(xué)的實(shí)驗(yàn)，我不僅深刻的掌握了編碼裁減法的基本原理和算法，還學(xué)習(xí)了c+builder中多種組件的使用，例如Image組件、TCanvas組件、Edit、Label等的使用，使我對(duì)該軟件有了更深的認(rèn)識(shí)。附錄： int x,y,x1,y1,x2,y2,xchange,ychange; bool done=0,accept=0; char c,c1,c2; int XL=20,XR=150,YB=20,YT=180; / 定義窗口區(qū)大小 Image1-Canvas-Rectangle(0,0,Image1-Width,Image1-Height); Image1-Canvas-Rectangle(XL,YB,XR,YT); Image2-Canvas-Rectangle(XL,YB,XR,YT); x1=StrToInt(X1-Text); y1=StrToInt(Y1-Text); x2=StrToInt(X2-Text); y2=StrToInt(Y2-Text); Image1-Canvas-MoveTo(x1,y1); Image1-Canvas-LineTo(x2,y2); while(done!=1) c1=0,c2=0; if(x1XR) c1=c1|2; if(y1YT) c1=c1|8; if(x2XR) c2=c2|2; if(y2YT) c2=c2|8; if(c1&c2)!=0) done=1; else if(c1=0 & c2=0) done=1; accept=1; /p1,p2均在窗口內(nèi) else if(c1=0) xchange=x1; x1=x2; x2=xchange; /交換p1,p2點(diǎn) ychange=y1; y1=y2; y2=ychange; c=c1; c1=c2; c2=c; if(c1&4)=4) x=x1-(y1-YB)*(x1-x2)/(y1-y2); y=YB; else if (c1&8)=8) x=x1-(y1-YT)*(x1-x2)/(y1-y2); y=YT; else if( (c1&1)=1) x=XL; y=y1-(x1-XL)*(y1-y2)/(x1-x2); e