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

計(jì)算機(jī)圖形學(xué)課程內(nèi)容緒論介紹計(jì)算機(jī)圖形學(xué)的含義、研究內(nèi)容、應(yīng)用及發(fā)展情況基本圖形生成算法介紹有關(guān)在圖形終端上顯示圖形的算法圖形變換介紹二維、三維的幾何變換及三維投影變換課程內(nèi)容--續(xù)二維圖形的運(yùn)算二維圖形裁減、添充及求交高級(jí)話題曲線、曲面消隱幾何造型附加內(nèi)容及應(yīng)用實(shí)踐AUTOCAD入門、上機(jī)操作主要參考書、期刊孫家廣、楊長貴，計(jì)算機(jī)圖形學(xué)（新版），清華大學(xué)出版社，1995謝步瀛，計(jì)算機(jī)繪圖教程，上海同濟(jì)大學(xué)出版社，1995計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)第一章緒論一、計(jì)算機(jī)圖形學(xué)的含義

ISO的定義：

計(jì)算機(jī)圖形學(xué)是研究通過計(jì)算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在專門的顯示設(shè)備上顯示的原理、方法和技術(shù)的學(xué)科

數(shù)據(jù)圖形顯示模型

二、計(jì)算機(jī)圖形學(xué)的發(fā)展及應(yīng)用1.發(fā)展情況50年代：誕生MIT旋風(fēng)I號(hào)、CALCOMP滾筒繪圖儀、GERBER的平板繪圖儀60年代：確立并蓬勃發(fā)展MIT的IvanE.Sutherland--”Sketchpad--一個(gè)人機(jī)通信的圖形系統(tǒng)“博士論文拉開圖形學(xué)研究的序幕；大公司開展大規(guī)模研究（通用、AT&T、BELL）70、80年代：進(jìn)入實(shí)用化更完備的硬件系統(tǒng)，個(gè)人計(jì)算機(jī)、工作站系統(tǒng)大量圖形應(yīng)用軟件出現(xiàn)90年代：廣泛深入的應(yīng)用標(biāo)準(zhǔn)化、集成化、智能化多媒體技術(shù)、人工智能、科學(xué)計(jì)算可視化、虛擬現(xiàn)實(shí)三維造型技術(shù)2.應(yīng)用用戶接口：人機(jī)界面CAD/CAM：機(jī)械、電子、汽車、飛機(jī)等辦公自動(dòng)化、電子印刷、管理繪圖繪制勘探、測量圖形：地理、地形模擬現(xiàn)實(shí)：藝術(shù)、工業(yè)、農(nóng)業(yè)科學(xué)計(jì)算可視化：天氣預(yù)報(bào)，過程模擬，CAI：計(jì)算機(jī)輔助教學(xué)、幼兒教育其它：醫(yī)療、刑偵三、計(jì)算機(jī)圖形學(xué)的研究內(nèi)容基本圖素的生成點(diǎn)、線、圓、字符的生成圖形的基本操作和處理并、交、差、裁減、填充、變換圖形的輸入輸出交互輸入、掃描輸入、圖形終端顯示、圖紙輸出三維幾何造型實(shí)體造型、曲面造型、特征造型真實(shí)感圖形生成消隱、濃淡圖、光照模型科學(xué)計(jì)算可視化分析數(shù)據(jù)的圖形描述四、計(jì)算機(jī)圖形系統(tǒng)的組成

計(jì)算機(jī)圖形系統(tǒng)是計(jì)算機(jī)硬件（包括中央處理機(jī)、圖形輸入輸出設(shè)備），以及軟件（包括系統(tǒng)軟件和圖形軟件）的集合。（一）基本功能要求計(jì)算功能：點(diǎn)、線、面的表示，求交，變換等存儲(chǔ)功能：在計(jì)算機(jī)中存儲(chǔ)圖形數(shù)據(jù)對(duì)話功能：實(shí)時(shí)顯示出用戶操作結(jié)果輸入功能：輸入用戶的設(shè)計(jì)、繪制要求輸出功能：顯示、保存（二）組成硬件及軟件硬件1.輸入設(shè)備鼠標(biāo)器：光電式、光機(jī)式、機(jī)械式光筆觸摸屏：電阻式、電容式、紅外線式坐標(biāo)數(shù)字化儀圖形掃描儀

2.顯示設(shè)備陰極射線管式隨機(jī)掃描(60年代中期）存儲(chǔ)管式（60年代后期）光柵掃描式（70年代中期）液晶顯示器（LCD）等離子顯示器3.繪圖設(shè)備圖形打印機(jī)針式打印機(jī)噴墨打印機(jī)激光打印機(jī)繪圖機(jī)靜電繪圖儀筆式繪圖儀：平板式、滾筒式軟件系統(tǒng)軟件：操作系統(tǒng)（UNIX，WINDOWS）、語言系統(tǒng)（C，C++）圖形系統(tǒng)軟件：圖形支撐軟件（OpenGL,PHIGS,etc.)、系統(tǒng)軟件(AutoCAD,Pro/Engineer,UGII,I-DEAS,Alias/Wavefront,AVS,etc.)(三）常用計(jì)算機(jī)圖形系統(tǒng)個(gè)人計(jì)算機(jī)圖形系統(tǒng)：是由個(gè)人計(jì)算機(jī)（PC）加上圖形輸入輸出設(shè)備和有關(guān)圖形支撐軟件集成起來的系統(tǒng)。價(jià)格便宜、功能及性能不強(qiáng)工作站圖形系統(tǒng)：UNIX、OPENGL，圖形系統(tǒng)軟件著名工作站：HP、SGI、SUN價(jià)格較昂貴、功能強(qiáng)大、性能良好兩種系統(tǒng)的比較光柵掃描圖形顯示器原理幀緩沖器顯示控制器D/A轉(zhuǎn)換器CRT返回連續(xù)存儲(chǔ)器,每個(gè)象素需一個(gè)存儲(chǔ)位PC計(jì)算機(jī)鼠標(biāo)鍵盤彩色圖形顯示器(TVGA)打印機(jī)繪圖機(jī)個(gè)人計(jì)算機(jī)圖形系統(tǒng)硬件組成返回特征PC機(jī)工作站處理器總線虛擬存儲(chǔ)網(wǎng)絡(luò)操作系統(tǒng)整數(shù)處理速度(MIPS)尺寸圖形價(jià)格CISC,C/RRISCAT,EISASBUS,MBUS

無有選擇有OS/2,WINDOWSUNIX1-1005-20012-17

16-27二維三維300-50005000-10萬

性質(zhì)CRTLCD等離子顯示器功耗大小中屏幕大小中平面度一般好中分辯率中一般好視角大一般中色彩豐富中中亮度好中好價(jià)格低低中第二章基本圖形生成算法本章將主要研究在光柵顯示器上的直線、圓的生成算法。

幾何圖形Ｇ＝｛Ｐi|

Pi最接近圖形的象素

｝基本圖形的生成算法任務(wù)之一就是找出所有的Ｐi.第二章基本圖形生成算法本章將主要研究在光柵顯示器上的直線、圓的生成算法。

幾何圖形Ｇ＝｛Ｐi|

Pi最接近圖形的象素

｝基本圖形的生成算法任務(wù)之一就是找出所有的Ｐi.一、直線的生成算法

即是找出逼近直線的一組象素，按掃描線順序，對(duì)這些象素進(jìn)行寫操作。1.數(shù)值微分法（ＤＤＡ）

假定直線的起點(diǎn)、終點(diǎn)分別為：（X0,Y0),(X1,Y1)，且都為整數(shù)。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)柵格交點(diǎn)表示象素點(diǎn)位置。。。。直線的斜率：

k=(Y1-Y0)/(X1-X0)

為討論方便，假定|k|<=1

直線方程：Ｙ=k*X+B設(shè)Ｘ的增量為Ｄx=１，可得如下Ｙ的增量方程：

Yi+1=kXi+1+B=k(Xi+Dx)+B=kXi+B+kDx=Yi+kDx=Yi+k程序?qū)崿F(xiàn)：DDALine(X0,Y0,X0,Y0,Color)intX0,Y0,X1,Y1,Color;{intXfloatdx,dy,k,ydx=x1-x0;dy=y1-y0;k=dy/dx;y=Y0;for(x=X0;x<=X1;x++){drawpixel(x,int(y+0.5),Color);y=y+k;}}缺點(diǎn)：浮點(diǎn)運(yùn)算、取整－－》廢時(shí)，且不利于硬件實(shí)現(xiàn)。問題：為什么｜k｜《１？，若｜k｜>１，上述算法會(huì)出現(xiàn)什么情況？應(yīng)如何處理？2.中點(diǎn)畫線法原理：假定直線斜率K<1，且已確定點(diǎn)亮象素點(diǎn)P（Xp,Yp

）M為中點(diǎn)，Q為交點(diǎn)現(xiàn)需確定下一個(gè)點(diǎn)亮的象素。P（Xp,Yp)MQP2P1顯然可得出如下結(jié)論：若M在Q的下方，選P2，否則選P1算法實(shí)現(xiàn)：假設(shè)直線的起點(diǎn)、終點(diǎn)分別為：（X0,Y0),(X1,Y1)

該直線方程可表示為：

F(x,y)=a*x+b*y+c（1）

其中：

a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0

當(dāng)：

F(Xt,Yt)=0++>(Xt,Yt)在直線上

F(Xt,Yt)<0++>(Xt,Yt)在直線下方

F(Xt,Yt)>0++>(Xt,Yt)在直線上方因此：將中點(diǎn)M坐標(biāo)代入（1）式，并判斷其符號(hào)即可確定象素點(diǎn)的選取。構(gòu)造如下判別式：

d=F(M)=F(Xp+1,Yp+0.5)=a(Xp+1)+b(Yp+0.5)+c

由上式可看出，d是x,y線性函數(shù)，可推導(dǎo)d的增量公式。當(dāng)d>=0時(shí)，取象素P1，此時(shí)再下一個(gè)象素的判別式為：

d’=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=a(Xp+1)+b(Yp+0.5)+c+a=d+a;當(dāng)d<0時(shí)，取象素P2，此時(shí)再下一個(gè)象素的判別式為：

d’=F(Xp+2,Yp+1.5)=a(Xp+2)+b(Yp+1.5)+c=a(Xp+1)+b(Yp+0.5)+c+a+b=d+a+b;d的初始值可按下式計(jì)算：

d0=F(X0+1,Y0+0.5)=a(X0+1)+b(Y0+0.5)+c=F(X0,Y0)+a+0.5b=a+0.5b

由于只用d的符號(hào)作判斷，為了只包含整數(shù)運(yùn)算,可取2d

代替d，這樣可得如下中點(diǎn)算法程序：

MidpointLine(X0,Y0,X1,Y1,Color)intX0,Y0,X1,Y1,Color;{inta,b,d1,d2,d,x,y;a=Y0-Y1;b=X1-X0;d=a+a+b;d1=a+a;d2=a+b+a+b;x=X0;y=Y0; drawpixle(x,y,Color);while(x<X1){if(d<0){x++;y++;d+=d2;}

else{x++;d+=d1;}drawpixle(x,y,Color);}/*while*/}/*MidPointLine*/

習(xí)題：按照中點(diǎn)劃線算法，確定直線（0，0）（5，3）的點(diǎn)亮象素。列出計(jì)算過程，并列出所選象素坐標(biāo)。

3.Bresenham畫線算法原理：dddd假定直線斜率,0<k<1,起點(diǎn)坐標(biāo)為(x,y);下一個(gè)點(diǎn)亮象素可能是：(x+1,y)或(x+1,y+1)。這可通過d值的大小來確定:d=d+k,當(dāng)d>1時(shí)d=d-1;當(dāng)d<0.5取(x+1,y)，否則取(x+1,y+1)。令e=d-0.5,顯然e的初值為-0.5。這樣可用e的符號(hào)來進(jìn)行判斷。程序如下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;inte;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;for(i=0;i<=dx;i++){drawpixel(x,y,color);x++;e=e+k;e1=e-0.5;e=e+2*dy;e1=e-dx;if(e1>0)e=e-1;e=e-2*dx;if(e>=0)y++;}}

思考題：如何去除上述程序中的浮點(diǎn)運(yùn)算、乘除法？就是要使得e值為整數(shù)

e’=2*dx*ee>0==>e’>0;e<0==>e’<0

二、圓的生成算法

即是找出逼近圓的一組象素，按掃描線順序，對(duì)這些象素進(jìn)行寫操作。

下面僅以圓心在原點(diǎn)的圓為例，討論圓的生成算法。1.圓弧掃描算法

X2+Y2=R2Y=Sqrt(R2-X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時(shí)，Y須圓整。缺點(diǎn)：浮點(diǎn)運(yùn)算，開方，圓整，不均勻。2.角度DDA法

x=x0+Rcosy=y0+Rsindx=-Rsinddy=Rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d

顯然，確定x,y的初值及d值后，即可以增量方式獲得圓周上的坐標(biāo)，然后取整可得象素坐標(biāo)。但要采用浮點(diǎn)運(yùn)算、乘法運(yùn)算。3.中點(diǎn)法利用圓的對(duì)稱性，只須討論1/8圓。MP1P2P（Xp，Yp）P為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。

構(gòu)造一函數(shù)：

F（X，Y）=X2+Y2-R2F（X，Y）=0（X，Y）在圓上；

F（X，Y）<0（X，Y）在圓內(nèi)；

F（X，Y）>0（X，Y）在圓外。M為P1、P2間的中點(diǎn)，M=(Xp+1,Yp-0.5)有如下結(jié)論：

F（M）<0取P1F（M）>=0取P2為此，可采用如下判別式：

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,則P1為下一個(gè)象素，那么再下一個(gè)象素的判別式為：

d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3

即d的增量為2xp+3.

若d>=0,則P2為下一個(gè)象素，那么再下一個(gè)象素的判別式為：

d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+2(xp-yp)+5

即d的增量為2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMidpointCircle(r,color)intr,color;{intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}}}習(xí)題：在上述程序基礎(chǔ)之上，寫出一新程序，使其僅為整數(shù)運(yùn)算，且不含乘除法。光柵掃描圖形顯示器原理幀緩沖器顯示控制器D/A轉(zhuǎn)換器CRT返回連續(xù)存儲(chǔ)器,每個(gè)象素需一個(gè)存儲(chǔ)位第三章圖形變換圖形變換是計(jì)算機(jī)圖形學(xué)基礎(chǔ)內(nèi)容之一。幾何變換，投影變換，視窗變換線性變換，屬性不變，拓?fù)潢P(guān)系不變。作用：把用戶坐標(biāo)系與設(shè)備坐標(biāo)系聯(lián)系起來；可由簡單圖形生成復(fù)雜圖形；可用二維圖形表示三維形體；動(dòng)態(tài)顯示。內(nèi)容：以下幾方面的內(nèi)容：數(shù)學(xué)基礎(chǔ)：矢量、矩陣及運(yùn)算二維幾何變換三維幾何變換投影變換視窗變換裁剪一、矢量、矩陣及運(yùn)算1.矢量的含義矢量：是由n個(gè)實(shí)數(shù)組成的集合。如：二維矢量(x,y)，三維矢量(x,y,z)(x,y)XYXYZ(x,y,z)2.矢量運(yùn)算假定：V1(x1,y1,z1),V2(x2,y2,z2)為兩個(gè)矢量，則有：矢量和

V1+V2=(x1+x2,y1+y2,z1+z2)矢量點(diǎn)積

V1·V2=x1*x2+y1*y2+z1*z2矢量叉積

V1×V2=(y1z2-y2z1,z1x2-z2x1,x1y2-x2y1)矢量長度

|V1|=(V1·V1)1/2=(x1*x1+y1*y1+z1*z1)1/2

3.矩陣的含義矩陣：由m×n個(gè)數(shù)按一定位置排列的一個(gè)整體，簡稱m×n矩陣。A=其中，aij稱為矩陣A的第i行第j列元素4.矩陣運(yùn)算加法設(shè)A，B為兩個(gè)具有相同行和列元素的矩陣A+B=數(shù)乘kA=[k*aij]|i=1..m,j=1,n乘法設(shè)A為3×2矩陣，B為避免2×3矩陣

C=A·B=C=Cm×p=Am×n·Bn×pcij=∑aik*bkj單位矩陣在一矩陣中，其主對(duì)角線各元素aii=1,其余皆為0的矩陣稱為單位矩陣。n階單位矩陣通常記作InAm×n=Am×n·Ink=1,n逆矩陣若矩陣A存在A·A-1=A-1·A=I，則稱A-1為A的逆矩陣矩陣的轉(zhuǎn)置把矩陣A=(aij)m×n的行和列互換而得到的n×m矩陣稱為A的轉(zhuǎn)置矩陣,記作AT

。

(AT)T=A(A+B)T=AT+BT(aA)T=aAT(A·B)T=BT·AT

當(dāng)A為n階矩陣，且A=AT，則

A是對(duì)稱矩陣。5.矩陣運(yùn)算的基本性質(zhì)交換律與結(jié)合律師

A+B=B+A;A+(B+C)=(A+B)+C數(shù)乘的分配律及結(jié)合律

a(A+B)=aA+aB;a(A·B)=(aA)·B=A·(aB)(a+b)A=aA+bAa(bA)=(ab)A矩陣乘法的結(jié)合律及分配律

A(B·C)=(A·B)C(A+B)·C=A·C+B·CC·(A+B)=C·A+C·B矩陣的乘法不適合交換律二、變換的一般流程二維變換的一般流程：三維變換的一般流程：基本元素幾何圖形屏幕窗口區(qū)幾何變換開窗與裁剪視窗變換基本體素幾何圖形屏幕窗口區(qū)幾何變換變換、裁剪視窗變換觀察空間投影變換三、二維圖形變換1.平移變換從點(diǎn)P[x,y]平移到點(diǎn)P’[x’,y’]x’=x+my’=y+nP(x,y)P’(x’y’)mnXY2旋轉(zhuǎn)變換αθρ(x,y)(x’,y’)一個(gè)點(diǎn)繞原點(diǎn)的旋轉(zhuǎn)，逆時(shí)針方向?yàn)檎?比例變換P(x,y)P’(x’,y’)x’=x*sxy’=y*sySx=Sy：均勻縮放。Sx=Sy>1，放大Sx=Sy<1，縮小Sx不等于Sy時(shí)，沿坐標(biāo)軸方向伸展和壓縮YX4.對(duì)稱變換關(guān)于X軸的對(duì)稱變換

P(x,y)對(duì)稱點(diǎn)為P’(x,-y)關(guān)于Y軸的對(duì)稱變換

P(x,y)對(duì)稱點(diǎn)為P’(-x,y)關(guān)于坐標(biāo)原點(diǎn)的對(duì)稱變換

P(x,y)關(guān)于原點(diǎn)的對(duì)稱點(diǎn)為P’(-x,-y)5錯(cuò)切變換(SHEAR)(1)沿x方向產(chǎn)生錯(cuò)切

x’=x+y*tag(θ) y’=y(2)沿y方向產(chǎn)生錯(cuò)切

x’=x y’=y+x*tag(θ)θ(x,y)(x’,y’)θ(x,y)(x’,y’)YXYX1.齊次坐標(biāo)

齊次坐標(biāo)就是一個(gè)n維矢量的(n+1)維矢量表示。例如：二維坐標(biāo)點(diǎn)P(x,y)的齊次坐標(biāo)為：(H*x,H*y,H)。

二維坐標(biāo)與齊次坐標(biāo)是一對(duì)多的關(guān)系。通常都采用規(guī)格化的齊次坐標(biāo)，即取H=1。(x,y)的規(guī)格化齊次坐標(biāo)為(x,y,1)。

齊次坐標(biāo)的幾何意義：可理解為在三維空間上第三維為常數(shù)的一平面上的二維向量。四、二維圖形變換的矩陣表示齊次坐標(biāo)的作用：

1.將各種變換用階數(shù)統(tǒng)一的矩陣來表示。提供了用矩陣運(yùn)算把二維、三維甚至高維空間上的一個(gè)點(diǎn)從一個(gè)坐標(biāo)系變換到另一坐標(biāo)系的有效方法。2.便于表示無窮遠(yuǎn)點(diǎn)。例如：（x*H,y*H,H)，令H等于0，1.恒等變換2.比例變換3.對(duì)稱變換關(guān)于X軸的對(duì)稱變換

關(guān)于Y軸的對(duì)稱變換

關(guān)于坐標(biāo)原點(diǎn)的對(duì)稱變換

習(xí)題：請(qǐng)寫出二維錯(cuò)切變換的變換矩陣。5.旋轉(zhuǎn)變換其矩陣表示為：αθρ(x,y)(x’,y’)6.平移變換P(x,y)P’(x’y’)mnXY7.繞任一點(diǎn)的旋轉(zhuǎn)變換假定該任一點(diǎn)為P(m,n),旋轉(zhuǎn)角為θ變換過程如下：(m,n)(x,y)θ(x’,y’)(x1,y1)θ(x2,y2)mn123(x’,y’)T1T2T3T=T1T2T3

稱為矩陣級(jí)聯(lián)，也稱復(fù)合變換。問題：如何將平面上一正方形繞原點(diǎn)進(jìn)行旋轉(zhuǎn)變換？對(duì)圓又如何變換？習(xí)題：

1請(qǐng)寫出二維錯(cuò)切變換的變換矩陣。

2試推導(dǎo)將二維平面上任一條直線P(x1,y1),Q(x2,y2)變換成與坐標(biāo)軸X重合的變換矩陣。

第四章二維圖形的運(yùn)算

在本章將主要介紹一些二維圖形的常用運(yùn)算方法。包括交點(diǎn)計(jì)算、幾何圖形的關(guān)系判別及線段裁剪等。一、交點(diǎn)計(jì)算1.兩直線段的交點(diǎn)設(shè)有兩線段S1，S2。S1的端點(diǎn)分別為P1(x1,y1),P2(x2,y2),S2的端點(diǎn)分別為P3(x3,y3),P4(x4,y4).則兩直線段的參數(shù)方程為：討論：無解，此時(shí)意味兩線段平行或重合；有唯一解，但不一定是有效解，有效解應(yīng)該是交點(diǎn)必須位于兩直線段上。此時(shí)應(yīng)滿足如下條件：

0≤u≤1.00≤v≤1.0根據(jù)u,v的值，即可獲得交點(diǎn)的坐標(biāo)。2.直線段與圓弧的交點(diǎn)討論：無解，第一種情況；一解，第三種情況；兩解，第二種情況。當(dāng)有解時(shí)，還須進(jìn)一步判斷：0≤t≤1.0,αs≤α≤αe12312343.兩圓弧的交點(diǎn)設(shè)有兩段圓弧A，B。A圓弧的圓心坐標(biāo)(xa,ya),半徑為ra,B圓弧的圓心坐標(biāo)(xb,yb),半徑為rb。

則有如下方程：如果兩圓相交，則應(yīng)有：討論：兩圓之間的關(guān)系存在以上三種。而對(duì)圓弧來說，有效解應(yīng)在圓弧的定義域內(nèi)：即：二、關(guān)系判別1.點(diǎn)的包含性檢驗(yàn)點(diǎn)的包含性檢驗(yàn)是指：判斷一個(gè)點(diǎn)是否被包含在某一個(gè)區(qū)域內(nèi)。為討論方便，我們定義該區(qū)域?yàn)橐欢噙呅?。但所采用的方法可推廣到曲線邊界。夾角和法設(shè)有一個(gè)點(diǎn)P和多邊形ABCDE，如下圖所示：ABCDE

若依次將P點(diǎn)與多邊形各頂點(diǎn)相連，且令αi為多邊形各相鄰頂點(diǎn)與點(diǎn)P相連所形成的夾角。則有如下結(jié)論：若∑αi=0,則點(diǎn)P在多邊形之外；

若∑αi=±2π,則點(diǎn)P在多邊形之內(nèi)；夾角αi的計(jì)算可采用余弦定理獲得。而其方向則可按右手法則確定，用公式表示如下：連線為兩矢量Vi,Vi+1,,則Vi×Vi+1=因此，可用如下判別式判斷夾角的方向：當(dāng)T>0時(shí)，為逆時(shí)針方向；當(dāng)T<0時(shí)，為順時(shí)針方向。交點(diǎn)數(shù)判別法

ABCDEABCDE交點(diǎn)數(shù)法所利用的原理：由P點(diǎn)向任一方向作一條射線，然后求出該射線與多邊形邊的交點(diǎn)數(shù)。則有：

1）當(dāng)交點(diǎn)數(shù)為偶數(shù)（0）時(shí)，則說明點(diǎn)P在多邊形外；

2）當(dāng)交點(diǎn)數(shù)為奇數(shù)時(shí)，則說明點(diǎn)P在多邊形內(nèi)。

為處理簡單，通常射線的與坐標(biāo)軸平行。奇異情況處理：即當(dāng)射線穿過多邊形頂點(diǎn)時(shí)的特殊處理。

當(dāng)射線穿過的頂點(diǎn)兩邊在射線兩側(cè)，此時(shí)認(rèn)為相交一次。而在同側(cè)時(shí)，則認(rèn)為相交兩次。ABCDE122.多邊形重疊性檢驗(yàn)通常采用“最小最大試驗(yàn)法”，也稱為“排斥試驗(yàn)法”。這種方法可迅速排除掉不可能相互重疊的情況，從而減少計(jì)算工作量，加快圖形處理速度。1）多邊形的最小包含矩形是指平面上能包含多邊形的最小的矩形。如下圖所示。

最小包含矩形2）重疊性檢驗(yàn)利用最小包含矩形，可排除兩個(gè)多邊形不重疊情況。

如果兩個(gè)多邊形的最小包含矩形，不發(fā)生重疊，則這兩個(gè)多邊形必不重疊。123

假定兩個(gè)多變形的最小矩形為a和b,左下角和右上角的坐標(biāo)分別為：

則當(dāng)a,b兩矩形滿足下列條件之一時(shí)，a和b不重疊

Xamax<=XbminYamax<=YbminXamin>=XbmaxYamin>=Ybmaxab(Xamin,Yamin)(Xamax,Yamax)(Xbmin,Ybmin)(Xbmax,Ybmax)XY

當(dāng)a、b兩矩形不滿足上述條件，即意味兩多邊形可能重疊。此時(shí)需通過兩多邊形的邊邊求交來判斷是否重疊。當(dāng)存在交點(diǎn)時(shí)，既表明兩多邊形重疊，否則不重疊。四、幾何圖形的裁剪

就是在一個(gè)圖形的整體中，把窗口的內(nèi)部分和窗口外部分正確地分離開來。這種技術(shù)稱為裁剪。1.線段裁剪線段和窗口的關(guān)系

要確定一條直線段上位于窗口內(nèi)的可見段，只須求出它的兩個(gè)位于窗口內(nèi)的可見端點(diǎn)即可。 算法的基本思想 把所有的直線按照它和窗口的關(guān)系分類，不同的直線使用不同的處理方法確定其可見部分。矢量裁剪算法用窗口的四條邊界的直線將窗口分為9個(gè)區(qū)。012345678(x1,y1)(x2,y2)ybytxlxr排斥性測試若線段滿足下述四個(gè)條件之一時(shí)：max(x1,x2)≤xlmin(x1,x2)≥xrmax(y1,y2)≤ybmin(y1,y2)≥yt則線段必定位于窗口之外，無輸出線段。包含性測試若線段滿足：xl≤x1≤xr,yb≤y1≤yt,則線段的始點(diǎn)在0區(qū)，也即線段可見段的起點(diǎn)為：

xs=x1,

ys=y1求交點(diǎn)，并判斷I.若x1＜xl,則：線段的起點(diǎn)坐標(biāo)可能位于3區(qū)、4區(qū)、5區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上直線x=xl和線段的交點(diǎn)上012345678(x1,y1)(x2,y2)ybytxlxr第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第三種情況：此時(shí)，若yb≤ys≤yt則(xsys)為有效新起點(diǎn)。三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。II.若x1>xr

線段的起點(diǎn)坐標(biāo)可能位于6區(qū)、7區(qū)、8區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上直線x=xr和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第三種情況：

此時(shí)，若yb≤ys≤yt則(xsys)為有效新起點(diǎn)。若此三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。若Xl<=X<=Xr線段的起點(diǎn)坐標(biāo)可能位于1區(qū)和2區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：

此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。若此二種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。

使用同樣的方法，可得到直線在窗口的另一個(gè)可見端點(diǎn)。編碼法該法的基本思想是：1)首先判斷線段是否完全位于窗口內(nèi)，如果是，則輸出原線段，如果不是，那么再進(jìn)而判斷是否完全位于窗口外，若是，則排除該線段，無輸出。2)如果以上測試都不滿足的話，那么就將該線段用窗口邊線分割為二段，然后再回到1)進(jìn)行上述測試。實(shí)現(xiàn)方法：將窗口邊線兩邊沿長，得到九個(gè)區(qū)域，每一個(gè)區(qū)域都用一四位二進(jìn)制數(shù)標(biāo)識(shí)，直線的端點(diǎn)都按其所處區(qū)域賦予相應(yīng)的標(biāo)識(shí)碼。100100010101100000000100101000100110ABCD第一位1：點(diǎn)處于左邊框線的左邊；第二位1：點(diǎn)處于右邊框線的右邊；第三位1：點(diǎn)處于下邊框線的下邊；第四位1：點(diǎn)處于上邊框線的上邊；顯然： 如果某線段的兩端點(diǎn)的兩個(gè)四位代碼全為零時(shí)那么該線段完全位于窗口內(nèi)；如果兩端點(diǎn)的標(biāo)識(shí)碼的邏輯乘不為零，那么該線段必位于窗口外。如果線段被分割，端點(diǎn)有了新的代碼，然后再進(jìn)行上述測試，測試結(jié)果是必有一段在窗口之外，可被排除，另一段再重復(fù)上述處理過程。如何判定該與窗口的哪條邊求交呢？ 編碼中對(duì)應(yīng)位為1的邊。中點(diǎn)分割算法定義：線段端點(diǎn)的最遠(yuǎn)可見點(diǎn)是指任一線段被窗口裁剪后所得兩個(gè)新端點(diǎn)中離該端點(diǎn)較遠(yuǎn)的一個(gè)點(diǎn)。如下圖所示。

A的最遠(yuǎn)可見點(diǎn)為a,B的最遠(yuǎn)可見點(diǎn)為b.ABab中點(diǎn)分割法的基本思想即是：不斷地用對(duì)分方法，舍去線段的不可見部分，用中點(diǎn)去逼近線段與窗口邊界的交點(diǎn)。

實(shí)現(xiàn)算法：（以A點(diǎn)為例說明）

1)排斥性測試，測試線段是否完全被排斥在窗口之外，若是，則無線段輸出，算法結(jié)束。否則執(zhí)行下一步；

2)包含性測試，測試B點(diǎn)是否包含在窗口內(nèi)，如果是，則B點(diǎn)即為A的最遠(yuǎn)可件點(diǎn)，算法結(jié)束，否則，執(zhí)行下一步；

3)將直線段AB于中點(diǎn)M處分割，則分如下幾種情況處理：線段MB完全在窗口之外，那么便以線段AM為新的線段AB，然后返回算法的第一步重新開始測試；如果線段MB沒有被完全排斥在窗口之外，那么便以線段MB作為新線段AB，然后返回算法的第一步1）。ABMABMABMABM

#defineTRUE1#defineFALSE0intmid_trim(p1,p2,xmin,ymin,xmax,ymax,a)floatp1[3],p2[3],xmin,ymin,xmax,ymax,a[3];{floatA[3],B[3],M[3];set_point(p1,A);set_point(p2,B);while(TRUE){