圖形的觀察運算

圖形的觀察運算1第一頁，共六十三頁，編輯于2023年，星期五問題的提出坐標用于決定圖形顯示的位置。但圖形學中有許多名字：邏輯坐標，設備坐標、用戶坐標、世界坐標、屏幕坐標、窗口、視圖。第二頁，共六十三頁，編輯于2023年，星期五§1、二維圖形的顯示流程圖（1）1。用戶坐標系：建立了圖形與數之間的對應聯(lián)系用戶坐標系(usercoordinate)世界坐標系(worldcoordinate)局部坐標系(localcoordinate)用戶定義原始圖形的坐標系極坐標系直角坐標系（也稱世界坐標系）球面坐標系等局部坐標系(localcoordinate)建立于物體上的坐標如圓第三頁，共六十三頁，編輯于2023年，星期五（2）設備坐標系設備坐標系(devicecoordinate)屏幕坐標系(screencoordinate)設備坐標系：圖形顯示器或繪圖紙上的坐標是2-D的直角坐標。在顯示器上的也稱屏幕坐標原點（也有在左下的）坐標軸的方向（y也有向上的）坐標軸的刻度坐標軸的取值范圍第四頁，共六十三頁，編輯于2023年，星期五(3）窗口在世界坐標系中指定的矩形區(qū)域用來指定要顯示圖形的范圍放在窗口內的圖形是要在屏幕上顯示的（裁剪）

(4）視區(qū)在設備坐標系（屏幕或繪圖紙)上指定的矩形區(qū)域

用來指定窗口內的圖形在屏幕上顯示的大小及位置用戶可以在屏幕上同時顯示多個視區(qū)窗口和視區(qū)的關系：有聯(lián)系也有區(qū)別窗口內的圖形只有送到視區(qū)才能顯示出來窗口和視區(qū)一一對應窗口可以重疊，視區(qū)不可以窗口可以幾何變換，視區(qū)不可以P70/圖4。4：1，2，3，4四個窗口第五頁，共六十三頁，編輯于2023年，星期五（4）變換及顯示流程第六頁，共六十三頁，編輯于2023年，星期五§2、窗口到視區(qū)的變換（1）

目標:將窗口之中的圖形變換到視區(qū)中變換的求法:變換的分解與合成

Muv=T(-xmin

–ymin)*S(a,c)*T(unimvmin)

第七頁，共六十三頁，編輯于2023年，星期五

Muv=T(-xmin

–ymin)*S(a,c)*T(unimvmin)a000c0-aXmin+Umin-cYmin+Vmin1a=Eu/Exc=Ev/EyEx=Xmax-XminEy=Ymax-YminEu=Umax-UminEv=Vmax=Vmin這和書上p714-3/4-4是一致的這里的x==Xwy==Ywu==Xvv==Yv第八頁，共六十三頁，編輯于2023年，星期五（2）第九頁，共六十三頁，編輯于2023年，星期五復習：位運算字符：有8位111111118421所以用一個字符的前4位就可以表示：10種狀態(tài)1:00011+2:00012:00100010-------------00111|2=0001|0010=00111|4=0001|0100=01011|8=0001|1000=10011&2=0001&0010=00001&3=0001&0011=0001

第十頁，共六十三頁，編輯于2023年，星期五§3、圖形的裁剪(clipping)（二維裁剪)裁剪：顯示指定的部分圖形裁剪窗口：該窗口內的圖形將被顯示，窗口外的圖形將被掉

[xmin,xmax]X[ymin,ymax]裁剪的方法很多，其效率高低和硬件水平和圖形的復雜程度有關裁剪的目的判斷圖形元素是否落在裁剪窗口之內并找出其位于內部的部分裁剪的處理的基礎圖元關于窗口內外關系的判別圖元與窗口的求交裁剪的圖形可以是：點陣圖形，也可以是參數表示的圖形第十一頁，共六十三頁，編輯于2023年，星期五內容：3.1直線段裁剪直接求交算法；Cohen-Sutherland算法； 中點算法3.2多邊形裁剪

Sutlerland_Hodgman算法3.3字符裁剪第十二頁，共六十三頁，編輯于2023年，星期五3.1直線段裁剪待裁剪線段和窗口的關系線段完全可見顯然不可見非顯然不可見第十三頁，共六十三頁，編輯于2023年，星期五點裁剪:線段和多邊形裁剪的基礎點(x,y)在窗口內的充分必要條件是：

xmin<=x<=xmaxymin<=y<=ymax

注意：窗口的邊界上的點是屬于窗口內的

第十四頁，共六十三頁，編輯于2023年，星期五直接求交算法1.直線整條在視區(qū)內：顯示2.直線整條在視區(qū)外:

不顯示3.部分在視區(qū)內,部分在視區(qū)外:

裁剪掉在外部分

p0p1第十五頁，共六十三頁，編輯于2023年，星期五為提高效率，算法設計時應考慮：(一）快速判斷情形(1)(2)；(完全可見,完全不可見)(二)設法減少情形(3)求交次數和每次求交時所需的計算量第十六頁，共六十三頁，編輯于2023年，星期五Cohen-Sutherland算法(編碼算法)第一步判別線段兩端點是否都落在窗口內，如果是，則線段完全可見；否則進入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結束；否則進行第三步；第三步求線段與窗口邊延長線的交點，這個交點將線段分為兩段，其中一段顯然不可見，丟棄。對余下的另一段重新進行第一步，第二步判斷，直至結束第十七頁，共六十三頁，編輯于2023年，星期五分析：1。兩個點同時在：左||右||上||下顯然不可見例：同時在左

2。兩個點不同時在：

!左&&!右&&!上&&!下：完全可見3.非顯然不可見，如：

HG,iJ,DC

如HG就有可能和邊相交

iJ也有可能，要求交來確定第十八頁，共六十三頁，編輯于2023年，星期五

編碼方法：由窗口四條邊所在直線把二維平面分成9個區(qū)域一個字符性的變量的前四位可以表示：

“上下右左”四種狀態(tài)一個四位編碼CtCbCrCl（上下右左）可以表示一個點處于9個區(qū)域的位置狀況；第十九頁，共六十三頁，編輯于2023年，星期五解釋圖第二十頁，共六十三頁，編輯于2023年，星期五試著給圖中線段標碼？EF:1001,0001AB:0000,0000iJ:0100,0010DC:1000,0000HG:0010,0100EF:1001&0001=0001iJ:0100&0010=0AB：0000&0000=0HG:0010&0100=0DC:1000&0000=0結論：1.線段的兩個端點的編碼的邏輯“與”非零:顯然不可見

2.為零為非顯然不可見（或完全可見）第二十一頁，共六十三頁，編輯于2023年，星期五對于那些非完全可見、又非顯然不可見的線段，需要求交（如，線段AD)，

0。先測試與窗口哪條邊所在直線有交？

(按序判斷端點編碼中各位的值ClCtCrCb）

1。和邊或邊的延長求交點

2。求交時邊的次序：左上右下步驟：先測知D在窗口外

DA和左邊交于C,DC’:1001&1001顯然不可見丟掉

CA在和邊求交，交于BCB’:1000&1000=1

顯然不可見,丟掉

BA0000&0000=0第二十二頁，共六十三頁，編輯于2023年，星期五

程序clipline分析：p731。測定點的狀態(tài)

clipstate(floatx,floaty);2。判斷和畫線:畫出裁剪出來的線段

lineclipout(floatx1,floaty1，floatx2,floaty2）第二十三頁，共六十三頁，編輯于2023年，星期五24程序4—1直線的編碼裁剪算法floatxwmin，ywmin，xwmax，ywmax；floatxvmin，yvmin，xvmax，yvmax；unsignedcharclipstate(floatx，floaty)//測試端點狀態(tài)代碼{unsignedcharc=0；．

if(x<xwmin){c=1；goto11；}//c=0001在左邊

elseif(x>xwmax)c=2：//c=0010在右邊11:if(y<ywmin){c=c|4；goto12：}//0101or0110elseif(y>ywmax)c=c|8;//1001or101012：returnc；}第二十四頁，共六十三頁，編輯于2023年，星期五intlineclipout(floatx1，floaty1，floatx2，floaty2){unsignedcharc1，c2，c3；a=(xvmax-xvmin)/(xwmax-xwmin);b=xvmin-xwmin*a;//見公式（4-3）c=((xvmax-xvmin)/(xwmax-xwmin);d=yvmin-ywmin*c;c1=clipstate(x1,y1);c2=clipstate(x2,y2);l3：if(c1!=0)gotol6//進行排斥試驗14:if(c2!=0)gotol6//0000在窗口內,進行窗口和視口變換后畫圖(4-4)71頁x1=a*x1+b；y1=c*y1+d;x2=a*x2+b;y2=c*y2+d;dda_line(x1,y1,x2,y2);//見程序1-1//a,b,c,d是窗口和視口的變化參數//c1,c2是起點和終點的狀態(tài)碼

//C1=1001c2=0000gotol6第二十五頁，共六十三頁，編輯于2023年，星期五調畫線程序L3,,C1!=0gotoL6L4c2!=0gotoL6

否則畫線(0000在窗口內,)L5return0(返回、)L6:c1&c2!=0都在同一邊gotoL5出口

c1!=0X2,y2x3,y3(c3中存放窗口外的C1的點:)

求交點L9:c3==c1(c1是窗口外部點)(裁剪c1點(用交點替換))

否則裁剪c2點(用交點替換)GotoL3,或L4第二十六頁，共六十三頁，編輯于2023年，星期五l5:return0;l6:if((c1&c2)!=0)gotol5;//點的碼c1為非零進入l6,//((c1&c2)!=0,窗口外在同一邊,exitif(c1!=0)c3=c1;elsec3=c2;//c3中放窗口外面的點

if(c3&1)==1){x=xwmn;//求線和邊的交點,得交點c’gotol9l7:y=(y2-y1)*(x-x1)/(x2-x1)+y1;gotol9}if(c3&2)==2){x=xwmax;gotol7;}if(c3&4)==4){y=ywmin;l8:x=(x2-x2)*(y-y1)/(y2-y1)+x1;gotol9;}y=ywmax;gotol8;l9:if(c3==c1){c1=clipstate(x,y);x1=x;y1=y;gotol3;}//把交點變成線的新端點,c2=clipstate(x,y);x2=x;y2=y;gotol4;//在外面的點到交點部分丟掉(交點留下),}//回到l3orl4重新(開始)測試//對于c點1000,c3&1!=1c3&2!=2,c3&4!=4,只能和上邊的得交點B,//再到l9把cb’丟掉,再gotol3,因為b為0,進入畫圖第二十七頁，共六十三頁，編輯于2023年，星期五Voidclipline()//直線的編碼裁剪算法入口{xwmin=0;ywmin=0;xwmax=400;ywmax=400;//設置窗口參數

xvmin=10;yvmin=10;xvmax=400;yvmax=400;//設置視口參數

Lineclipout(500,600,200,300);//直線裁剪輸出,從這里開始調用}

總之:測的點的狀態(tài)碼兩點都在窗口外丟掉兩點都在窗口內畫線求交用交點替換(裁剪)

第二十八頁，共六十三頁，編輯于2023年，星期五簡化第二十九頁，共六十三頁，編輯于2023年，星期五程序4-1直線編碼裁剪算法修改如下：intlineclipout(floatx1,floaty1,floatx2,floaty2){floatxwmin,ywmin,xwmx,ywmax,d;floatxvmin,yvmin,xvmx,yvmax;d=(y2-y1)/(x2-x1);c1=clipstate(x1,y1);c2=clipstate(x2,y2);L:if(c1==0&&c2==0)畫線；

elseif((c1&c2)==0)//非顯然不可見{if(c1!=0)c3=c1;elsec3=c2;//c3中放窗口外面的點if((c3&1)==1){x=xwmin;y=y1+d*(x-x1);}//求交elseif(c3&2)==2){x=xwmax;y=y1+d*(x-x1);}if((c3&4)==4){y=ywmin;x=x1+d(y-y1);}else{y=ymax;x=x1+d*(y-y1);}//裁剪if(c3==c1){c1=clipstate(x,y);x1=x;y1=y;}else{c2=clipstate(x,y);x2=x;y2=y;}gotoL;}

另外兩個函數:clipstate(),clipline(),可以和書上一樣第三十頁，共六十三頁，編輯于2023年，星期五直線的中點對分裁剪算法原理與直線的編碼裁剪算法原理類似，也是用直線的端點狀態(tài)編碼判斷其端點位于窗口內外，以便能先對直線進行直接地舍取處理，只有對那些不能通過測試的直線段才去求窗口與直線的交點想法：求窗口與直線的交點，用中點代替交點.

反復運用用直線的中點逐次逼近交點，且求中點的次數不趕過log2n次，其中n=rnax{|?x|,|?y|},?x,△y是直線兩端點在X，y方向上的增量.第三十一頁，共六十三頁，編輯于2023年，星期五a點為(窗口外部點)<—>c1b為(窗口內部點)<—>c2（用x3,y3記住內部點b）c1!=0,c1&c2!=0.不畫,否則(cl&c2)==0

三種可能,應該求交點L15:否則C1==0x1,y1->x2,y2(a,b互換保證非0點在外部)L1:x3,y3x1,y1若C2==0畫線elsec2!=0是b2的情況(要完成a,b互換,還要x2,y2x3,y3)c1,c2也要換:所以c1=c2,c2=0L15:求中點：m1-c若中點等于x1,y1或,x2,y2,L1(求得一個和邊的交點,若原來x2,y2是內部點,可畫)c1&c==0要繼續(xù)求交,

求交前:b或b2要丟掉,b=m1否則和a在同一邊,要丟掉a,a=m1c1

對新a和b求中點：m2-cL14或L15第三十二頁，共六十三頁，編輯于2023年，星期五對于a2,b2,,則丟掉b2時,等于先求a2到m的交點，設a=a2,b=m1:…..求到a=m=b時再把b2作a:(x3,y3)->(x1,y1),把新交點作b:(X2,y2)送(x3,y3),

包括點的狀態(tài)c2->c1，c2=0;開始新的一根線的裁剪第三十三頁，共六十三頁，編輯于2023年，星期五算法核心:c1是非0

14：if((cl&c2)!=0)goto13；//不可見

//(cl&c2)==0應該求交點

15：x=(x1+x2)/2;y=(y1+y2)/2；

//取中點p=(P1+P2)/2

if(x==x1&&y==y1)16：{x2=x；y2=y；gotol1;}if(x==x2&&y==y2)gotol6；

c=clipstate(x,y);//得到中點的狀態(tài)

//(c&c1)==0,c2對應的點(x2,y2)丟掉

if((c&c1)==0){x2=x；y2=y；goto5；}else{x1=x；y1=y；c1=c；gotol4；}//否則(x1,y1)丟掉第三十四頁，共六十三頁，編輯于2023年，星期五裁剪函數:c1=clipstate(x1,y1);c2=clipstate(x2,y2);x3=x2；y3=y2；k=0；//記住x2,y2

if(c1!=0)goto14；//可能要丟掉或求交

x2=x1；y2=y1；//c1==0,則x1,y1和x2,y2互換11：x1=x3；y1=y3；//保證非0點在窗口外

if(c2==0)goto12；//c1c2都為內部點,畫線,否則

k=1；x3=x2；y3=y2；c1=c2；c2=0；gotol5；

//繼續(xù)計算這部分是c2!=0的情況:b212：A=(xvmax-xvmin)/(xwmax-xwmin)；B=xvmin-xwmin*A；

C=(yvmax-yvmin)/(ywmax-ywmin)；D=yvmin-ywmin*C；

x1=A*x1+B：yl=C*yl+D；x2=A*x2+B；y2=C*y2+D；

if(k==1)dda_line(x1,y1,x2,y2);elsedda_line(x2,y2,xl,y1)；//dda算法有方向性13：return0；14：if(c1&c2)!=0)goto13；//都在窗口同一邊,不可見

//否則要求交:見上一頁第三十五頁，共六十三頁，編輯于2023年，星期五實面積多邊形的裁剪實面積多邊形被裁剪之后仍為實面積圖形，這就要求裁剪之后多邊形的邊界是自然封閉的它和裁剪直線的算法不同。錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？第三十六頁，共六十三頁，編輯于2023年，星期五2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第三十七頁，共六十三頁，編輯于2023年，星期五

2．多邊形的逐邊裁剪算法---個通用的方法,原理簡單,實現方便1974年由Sutherland和H。dgman提出出發(fā)點是把復雜問題的分解成幾個簡單的過程，使問題簡化分割處理策略：將多邊形關于矩形窗口的裁剪分解為：多邊形關于窗口四邊所在的直線的裁剪。即逐邊裁剪方法：

1。用窗口一條邊對多邊形裁剪，保留余下的多邊形（得到一個或若干個新的封閉的多邊形）

2。再用下一條邊對新的多邊形裁剪…..即:當用窗口的第一條邊框裁剪處理完之后，再用第二條邊框對那些新生成的多邊形進行裁剪，如此下去，直至窗口的四條邊框都裁剪完畢。第三十八頁，共六十三頁，編輯于2023年，星期五裁剪過程(左上右下)：裁剪次序:左上右下.先用左邊裁剪,左邊的結果是上邊的開始,……。所以是逐邊裁剪裁剪結果的頂點構成：

1.裁剪邊內側的原頂點；

2.多邊形的邊與裁剪邊的交點。應該有一個頂點棄舍的規(guī)則:

具體到用邊裁剪時如何決定取舍問題考慮一個點,實際上和線有關,所以下面把p作為考慮的點,s作為它的前一點第三十九頁，共六十三頁，編輯于2023年，星期五第四十頁，共六十三頁，編輯于2023年，星期五裁剪規(guī)則:窗邊與多邊形的邊線之問的關系:1：頂點S,P位于窗口邊框ek的可見側，保留S，P2:邊形的邊sp與窗口邊框ek相交，且交點為i，頂點s位于可見側，保留(頂點S,)交點i3.頂點s，P均位于窗口邊框ek的不可見側.

把S，P點都丟掉

4.多邊形的邊SP與窗口邊框ek相交于i，

P點位于窗口邊框的可見側，保留交點i和P點

第四十一頁，共六十三頁，編輯于2023年，星期五5:邊SP與窗邊ek完全重合，則s，P點坐標都丟掉6:邊的兩點s，P，其中一點位于可見側，另一點正好位于窗口邊框上,則(s，)P(都)保留如果s，P兩點中一點位于不可見側，另一點正好位于窗口邊框上,則s，P都不保留第四十二頁，共六十三頁，編輯于2023年，星期五處理方法：(cj)

多邊形被一條邊處理，下一次處理留下的for(e=0;e<4;e++)//被窗口的4條邊,逐邊裁剪{//temp[]用于暫時存放交點

s=p[n-1];最后一點作起點

for(i=0;i<n;i++){s,p都可見:temp[j++]=pp[i];//情況1

若只s不可見:{intersect(s,pp[i],Eb[e]);//情況4temp[j++]=jop;temp[j++]=pp[i];}

若只p不可見:{intersect(s,pp[i],Eb[e]);//情況2temp[j++]=jop;}

情況3:無輸出

s=pp[i];//考察點作為下一個起點

}temp[]送pp[],j送n,j=0;//pp[]準備下一輪裁剪用,j是余下的交點數

}第四十三頁，共六十三頁，編輯于2023年，星期五程序:classpoint1{public:intx,y;intk;};typedefclasspoint1Edge[2];//Edge是邊類型,有兩個點Edgeedge[4];floatD;D是斜率CPointpp[100],temp[100],jop;intj;j用于temp[100]臨時存放輸出點voidintersect(point1s,point1p,EdgeEb);intinside(point1p,EdgeEb);voidfun(intj,point1temp[]);用temp[]重寫pp[]voidprint(intn,point1pp[]);第四十四頁，共六十三頁，編輯于2023年，星期五intmain(intargc,char*argv[]){point1s,outp[10];intj=0,i,k=1,m1,m2,mi;EdgeEb[4];//次序：0下1右2上3左

Eb[0][0].x=10;Eb[0][0].y=10;Eb[0][1].x=20;Eb[0][1].y=10;Eb[1][0].x=20;Eb[1][0].y=10;Eb[1][1].x=20;Eb[1][1].y=25;Eb[2][0].x=20;Eb[2][0].y=25;Eb[2][1].x=10;Eb[2][1].y=25;Eb[3][0].x=10;Eb[3][0].y=25;Eb[3][1].x=10;Eb[3][1].y=10;//4點

pp[0].x=5;pp[0].y=22;pp[1].x=15;pp[1].y=12;pppp[2].x=25,pp[2].y=17;pp[3].x=15;pp[3].y=27;

第四十五頁，共六十三頁，編輯于2023年，星期五inte,n=4;print(n,pp);for(e=0;e<4;e++)//用一條邊裁剪多邊形，留下的點在temp[j]中{s=pp[n-1];//最后一點作起點

for(i=0;i<n;i++)//pp[0]到pp[n-1]{if(inside(pp[i],Eb[e])==1)//pp[i]是Eb[e]的內部點

if(inside(s,Eb[e])==1)outp[j++]=pp[i];//情況1else{intersect(s,pp[i],Eb[e]);//情況4得到交點jopoutp[j++]=jop;outp[j++]=pp[i];}//pp[i]可見第四十六頁，共六十三頁，編輯于2023年，星期五

elseif(inside(s,Eb[e])==1)//p不是內部,s是

{intersect(s,pp[i],Eb[e]);//情況2,得到交點jopoutp[j++]=jop;}//情況3無輸出

s=pp[i];//一個點查完

}//forendn=j;fun(n,outp);j=0;//把outp作為新的pp[]}//forendprint(n,pp); printf("HelloWorld!\n"); return0;}第四十七頁，共六十三頁，編輯于2023年，星期五intinside(CPointp,EdgeEbb){printf("\ninside:p:%d%de:%d%d%d%d",p.x,p.y,Ebb[0].x,Ebb[0].y,Ebb[1].x,Ebb[1].y);

if(Ebb[1].x>Ebb[0].x)//下邊{if(p.y>=Ebb[0].y){printf("下邊");return1;}}elseif(Ebb[1].x<Ebb[0].x)//上邊

{if(p.y<=Ebb[0].y){printf("上邊");return1;}}if(Ebb[1].y>Ebb[0].y)//右邊

{if(p.x<=Ebb[0].x){printf("右邊：%d<%d",p.x,Ebb[0].x);return1;}}elseif(Ebb[1].y<Ebb[0].y)//左邊

{if(p.x>=Ebb[0].x){printf("左邊：%d>%d",p.x,Ebb[0].x);return1;}}return0;}

第四十八頁，共六十三頁，編輯于2023年，星期五voidintersect(point1s,point1p,EdgeEbb){intm=0;floattx,ty;D=?//把D求出來

if(Ebb[0].y==Ebb[1].y)//水平裁剪

{jop.y=Ebb[0].y;jop.x=s.x+D*(Ebb[0].y-s.y);}else{//垂直裁剪

jop.x=Ebb[0].x;jop.y=s.y+(Ebb[0].x-s.x)/D;}

}第四十九頁，共六十三頁，編輯于2023年，星期五voidfun(intj,point1outp[]){inti;for(i=0;i<j;i++) {pp[i]=outp[i];outp[i].x=0;outp[i].y=0;}}

voidprint(intj,point1pp[]){inti;

補上}第五十頁，共六十三頁，編輯于2023年，星期五問題：如何才能適合硬件實現如多邊形被左邊裁剪后留下的，被上邊裁剪。每次留下的中間結果，硬件不易實現。遞歸方法：

1。按多邊形的頂點次序依次裁剪多邊形的每條邊（被窗口的邊依次（左上右下））被左邊裁剪:如vov3,vov1被裁剪,

v1v2,v2v3都可見

2。對于每一條邊：被第一條邊通過的邊被第二條裁剪……

被所有邊通過的邊顯示。對于每一條邊的處理見下面的框圖：第五十一頁，共六十三頁，編輯于2023年，星期五結點的數據結構:p77(坐標,標志位)標志位:0:頂點

1:交點

2:見p78表4-1第五十二頁，共六十三頁，編輯于2023年，星期五對于第一個點,不處理,而作為s點,若該點可見,還要被其它邊裁剪多邊形的每一點,被窗口的每一條邊裁剪,然后,去下一點第五十三頁，共六十三頁，編輯于2023年，星期五遞歸示意：classpoint1{public:intx,y;intk;};point1f;edge(intk,point1s,point1p)//如：第k條邊s是3點，p是4點{if(p是第一點)f=p;elseif(p.k==2)bh();//進入閉合處理

elseif(sp和第k條邊相交）

{求交點i；i.k=1;edge(k+1,s,i);}//處理交點(形成的邊si)if(p位于E的不可見側）{s=p;淘汰p;}else//sp(即p)被k+1邊裁剪,if(k++<4)edge(k,s,p);else{輸出p;s=p;}returns;}將交點I被另一條邊裁剪處理p點第五十四頁，共六十三頁，編輯于2023年，星期五幾點分析：1。Sp和E1相交，判完交點si’后，繼續(xù)判p(i’p)和E2,E3,E42.求交：多邊形的邊和窗口的邊的直線（可延長）3.裁剪窗口一般是矩形，和一個邊的交點對另外3邊是否一定可見？

第五十五頁，共六十三頁，編輯于2023年，星期五外環(huán)連接規(guī)則(略)1。依次連接交點-頂點，頂點-頂點，頂點-交點：1‘-4，4-2’，5‘-7，7-6’2。依次連接不在同一條邊框上的交點-交點：

3‘-4’3。對每條邊框上的交點,按環(huán)行方向（逆）。成對連線：e1:8’,3’,2’,1’8’-3’,2’-1’e2:6’-5’,4’-8’4.首尾連接：第五十六頁，共六十三頁，編輯于2023年，星期五而1’分別位于e2,e3,e4的可見側，所以l’交點最后輸出，即步驟⑥、(7)步驟⑧．這些步驟之后,l’交點處理完備.

流程返回e1裁剪流程，再繼續(xù)處理頂點4.

因頂點4位于e1的可見側，步驟(9)把頂點4送人e2的裁剪流程，在e2的裁剪