計(jì)算機(jī)圖形學(xué)教案(最終稿)

一.緒論課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：1.使學(xué)生了解計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容、應(yīng)用和研究前沿.2.使學(xué)生了解圖形設(shè)備.教學(xué)重點(diǎn)：圖形有關(guān)設(shè)備.教學(xué)難點(diǎn)：圖形系統(tǒng)及其標(biāo)準(zhǔn).教學(xué)過(guò)程：1計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容如何在計(jì)算機(jī)中表示圖形、以及利用計(jì)算機(jī)進(jìn)行圖形的計(jì)算、處理和顯示的相關(guān)原理與算法，構(gòu)成了計(jì)算機(jī)圖形學(xué)的主要研究?jī)?nèi)容。圖形硬件、圖形標(biāo)準(zhǔn)、圖形交互技術(shù)、光柵圖形生成算法、曲線曲面造型、實(shí)體造型、真實(shí)感圖形計(jì)算與顯示算法，以及科學(xué)計(jì)算可視化、計(jì)算機(jī)動(dòng)畫、自然景物仿真、虛擬現(xiàn)實(shí)等。2計(jì)算機(jī)圖形學(xué)的發(fā)展歷史50年代1950年，第一臺(tái)圖形顯示器作為美國(guó)麻省理工學(xué)院(MIT)旋風(fēng)I號(hào)(WhirlwindI)計(jì)算機(jī)的附件誕生。1958年，美國(guó)Calcomp公司由聯(lián)機(jī)的數(shù)字記錄儀發(fā)展成滾筒式繪圖儀，GerBer公司把數(shù)控機(jī)床發(fā)展成為平板式繪圖儀。50年代末期，MIT的林肯實(shí)驗(yàn)室在“旋風(fēng)”計(jì)算機(jī)上開發(fā)SAGE空中防御體系。60年代1962年，MIT林肯實(shí)驗(yàn)室的I.E.Sutherland發(fā)表了?篇題為“Sketchpad：?個(gè)人機(jī)交互通信的圖形系統(tǒng)”的博士論文。提出圖形學(xué)的概念，成就“圖形學(xué)之父”的英名3計(jì)算機(jī)圖形學(xué)的應(yīng)用及研究前沿計(jì)算機(jī)輔助設(shè)計(jì)與制造(CAD/CAM)CAD/CAM是計(jì)算機(jī)圖形學(xué)在工業(yè)界最廣泛、最活躍的應(yīng)用領(lǐng)域真實(shí)感圖形實(shí)時(shí)繪制與自然景物仿真計(jì)算機(jī)中重現(xiàn)真實(shí)世界的場(chǎng)景叫做真實(shí)感繪制，真實(shí)感繪制的主要任務(wù)是模擬真實(shí)物體的物理屬性，簡(jiǎn)單的說(shuō)就是物體的形狀，光學(xué)性質(zhì)，表面的紋理和粗糙程度，以及物體間的相對(duì)位置，遮擋關(guān)系等等。計(jì)算機(jī)動(dòng)畫二維動(dòng)畫、圖象變形、形狀混合、三維動(dòng)畫、關(guān)鍵幀動(dòng)畫、變形物體的動(dòng)畫、過(guò)程動(dòng)畫、關(guān)節(jié)動(dòng)畫與人體動(dòng)畫、基于視頻(Video)的動(dòng)畫用戶接口用戶接口是人們使用計(jì)算機(jī)的第?觀感。一個(gè)友好的圖形化的用戶界面能夠大大提高軟件的易用性計(jì)算機(jī)藝術(shù)用計(jì)算機(jī)軟件從事藝術(shù)創(chuàng)作：二維平面的畫筆程序（如CorelDraw,Photoshop,PaintShop）、圖表繪制軟件（如Visio）、三維建模和渲染軟件包（如3DMAX,Maya）、以及一些專門生成動(dòng)畫的軟件（如Alias,Softimage）4、圖形設(shè)備,圖形顯不設(shè)備圖形輸入設(shè)備圖形系統(tǒng)及其標(biāo)準(zhǔn)■圖形顯示設(shè)備：陰極射線管、彩色陰極射線管、射線穿透法、影孔板法、隨機(jī)掃描顯示系統(tǒng)、光柵掃描系統(tǒng)圖形處理器圖形處理器是圖形系統(tǒng)結(jié)構(gòu)的重要元件，是連接計(jì)算機(jī)和顯示終端的紐帶早期的圖形處理器只包含簡(jiǎn)單的存儲(chǔ)器和幀緩沖區(qū)，它們實(shí)際上只起了一個(gè)圖形的存儲(chǔ)和傳遞作用，一切操作都必須有CPU來(lái)控制?現(xiàn)在的圖形處理器不單單存儲(chǔ)圖形，而且能完成大部分圖形函數(shù)，專業(yè)的圖形卡已經(jīng)具有很強(qiáng)的3D處理能力，大大減輕了CPU的負(fù)擔(dān)，提高了顯示質(zhì)量和顯示速度圖形輸入設(shè)備最常用的圖形輸入設(shè)備就是基本的計(jì)算機(jī)輸入設(shè)備——鍵盤和鼠標(biāo)跟蹤球和空間球都是根據(jù)球在不同方向受到的推或拉的壓力來(lái)實(shí)現(xiàn)定位和選擇。數(shù)據(jù)手套則是通過(guò)傳感器和天線來(lái)獲得和發(fā)送手指的位置和方向的信息。這幾種輸入設(shè)備在虛擬現(xiàn)實(shí)場(chǎng)景的構(gòu)造和漫游中特別有用圖形系統(tǒng)及其標(biāo)準(zhǔn)硬件，圖形I/O設(shè)備，系統(tǒng)軟件，圖形軟件。圖形軟件：通用編程軟件包，專用應(yīng)用軟件包。通用類：提供一個(gè)可用于高級(jí)程序語(yǔ)言的圖形功能擴(kuò)展集（比如，OpenGL）.基本功能：圖元生成，屬性設(shè)置（顏色，….）選擇觀察及實(shí)施變換等。專用類：不關(guān)心圖形操作過(guò)程（比如，CAD系統(tǒng)。圖形系統(tǒng)標(biāo)準(zhǔn)圖形標(biāo)準(zhǔn)：圖形系統(tǒng)及其相關(guān)應(yīng)用系統(tǒng)中各界面之間進(jìn)行數(shù)據(jù)傳送和通信的接口標(biāo)準(zhǔn)，以及供圖形應(yīng)用程序調(diào)用的子程序功能及其格式標(biāo)準(zhǔn)，前者稱為數(shù)據(jù)及文件格式標(biāo)準(zhǔn)，后者稱為子程序界面標(biāo)準(zhǔn)。圖形系統(tǒng)標(biāo)準(zhǔn)分類面向圖形設(shè)備的接口標(biāo)準(zhǔn)：計(jì)算機(jī)圖形元文件（CGM）,（CRT,Mouse,…）計(jì)算機(jī)圖形接口（CGI）.設(shè)備驅(qū)動(dòng)程序。面向應(yīng)用軟件的標(biāo)準(zhǔn)：程序員層次交互式圖形系統(tǒng)（PHIGS）,GL（圖形程序包）（三維）圖形核心系統(tǒng)（3D-）GKS面向圖形應(yīng)用系統(tǒng)中工程和產(chǎn)品數(shù)據(jù)模型及其文件格式：基本圖形轉(zhuǎn)換規(guī)范（IGES）產(chǎn)品數(shù)據(jù)轉(zhuǎn)換規(guī)范（STEP）小結(jié)：本章主要介紹計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容、發(fā)展歷史、應(yīng)用領(lǐng)域、研究前沿及未來(lái)趨向,同時(shí)還介紹圖形硬件的一些基本原理，可使讀者對(duì)圖形學(xué)的相關(guān)內(nèi)容有一個(gè)概括性的了解。作業(yè)：.一個(gè)圖形系統(tǒng)通常由那些圖形設(shè)備組成？.圖形和圖象的區(qū)別是什么？.LCD顯示器有那些技術(shù)指標(biāo)？.常用的圖形輸入設(shè)備有哪些？二.光柵圖形學(xué)（一）課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：使學(xué)生掌握光柵圖形學(xué)中兒個(gè)重要的概念及其相應(yīng)算法。教學(xué)重點(diǎn)：直線段的掃描轉(zhuǎn)換算法。教學(xué)難點(diǎn)：圓弧的掃描轉(zhuǎn)換算法。教學(xué)過(guò)程：直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換：確定最佳逼近于該直線的一組象素，并且按掃描線順序，對(duì)這些象素進(jìn)行寫操作。三個(gè)常用算法：?數(shù)值微分法（DDA）?中點(diǎn)畫線法,Bresenham算法。2.1.1數(shù)值微分（DDA）法基本思想已知過(guò)端點(diǎn) 4（%,治）,《（斗，必）的直線段l：y=kx+b直線斜率為k= -1一.。X1—x0從X的左端點(diǎn)X。開始，向X右端點(diǎn)步進(jìn)。步長(zhǎng)=1（個(gè)象素），計(jì)算相應(yīng)的y坐標(biāo)y=履+b；取象素點(diǎn)（x,round（y））作為當(dāng)前點(diǎn)的坐標(biāo)。由此出發(fā)點(diǎn)，導(dǎo)致增量算法的思想。計(jì)算Z+i=kxi+i+b=kN+b+kAx=X+k^x當(dāng)Ax=i時(shí)；y+i=y+%即：當(dāng)x每遞增1,y遞增k（即直線斜率）;

例:X0例:X012345注:畫直線段4(0,0)一片(5,2)0 00 0.4+0.51 0.8+0.51 1.2+0.52 1.6+0.52 2.0+0.5網(wǎng)格點(diǎn)表示象素voidDDALine(intxO,intyO,intxl,intyl,intcolor)(intx；floatdx,dy,y,k;dx,=xl-xO,dy=yl-yO;k=dy/dx,y=yO;for(x=x0;x<xl,x++){drawpixel(x,int(y+0.5),color);y=y+k；2.1.2中點(diǎn)畫線法采用增量思想的DDA算法，每計(jì)算??個(gè)象素，只需計(jì)算一個(gè)加法，是否最優(yōu)?如非最優(yōu)，如何改進(jìn)？目標(biāo)：進(jìn)一步將?個(gè)加法改為一個(gè)整數(shù)加法。新思路一〉DDA算法采用兩點(diǎn)式，可否采用其他的直線表示方式？基本思想當(dāng)前象素點(diǎn)為(xp,yp)。下一個(gè)象素點(diǎn)為Pl或P2o設(shè)M=(xp+1,yp+0.5),為pl與p2之中點(diǎn)，Q為理想直線與x=xp+l垂線的交點(diǎn)。將Q與M的y坐標(biāo)進(jìn)行比較。?當(dāng)M在Q的下方，則P2應(yīng)為下一個(gè)象素點(diǎn);? M在Q的上方，應(yīng)取P1為下一點(diǎn)。構(gòu)造判另IJ式:d=F(M)=F(xp+l,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=yO-yl,b=xl-x0,c=x0yl-xly0當(dāng)d<0,M在L(Q點(diǎn))下方，取右上方P2為下一個(gè)象素；當(dāng)d>0,M在L(Q點(diǎn))上方，取右方P1為下一個(gè)象素；當(dāng)d=0,選Pl或P2均可，約定取P1為下一個(gè)象素；但這樣做，每一個(gè)象素的計(jì)算量是4個(gè)加法，兩個(gè)乘法。如果也采用增量算法呢？d是xp,yp的線性函數(shù)，因此可采用增量計(jì)算，提高運(yùn)算效率。若當(dāng)前或素處于企0情況，則取正右方象素Pl(xp+1,yp),要判下一個(gè)象素位置，應(yīng)計(jì)

算dl=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量為a若d<0時(shí)，則取右上方象素P2(xp+l,yp+l)。要判斷再下一象素，則要計(jì)算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量為a+b畫線從(xO,yO)開逅，d的初值dO=F(xO+l,y0+0.5)=F(x0,y0)+a+0.5b=a+O.5b?？梢杂?d代替d來(lái)擺脫小數(shù)，提高效率。令d0=2a+b,dl=2a,d2=2a+2b,我們有如下算法。voidMidpointLine(intxO,intyO,intxl,intyl,intcolor){inta,b,dl,d2,d,x,y;a=yO-y1,b=xl-xO,d=2*a+b;dl=2*a,d2=2*(a+b);x=xO,y=yO;drawpixel(x,y,color);while(x<xl){if(d<0) {x++,y++,d+=d2;}else{x++,d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/例：用中點(diǎn)畫線法 產(chǎn)。(0,0)-6(5,2)a=y0-Ji=-2,b=x,-x0=54,=2〃+b=1,&=2〃=—4,d2=2(a+b)=6,ixiixiyidI0013210-323213431-1154252.1.3Bresenham算法? 基本思想過(guò)各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素中與此交點(diǎn)最近的象素。設(shè)直線方程為： y,+i=Z+憶（七+1-七）=y+% ，其中k=dy/dxo因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)d的初值d0=0?X下標(biāo)每增加1,d的值相應(yīng)遞增直線的斜率值k,即（1=（1+匕一旦d21,就把它減去1,

這樣保證d在0、1之間。TOC\o"1-5"\h\z?當(dāng)d20.5時(shí)，最接近于當(dāng)前象素的右上方象素(％,+1，匕+1 ),而當(dāng)d<0.5時(shí)，更接近于右方象素( 匕+1，%)o為方便計(jì)算，々e=d-0.5,e的初值為-0.5,增量為k。?當(dāng)e20時(shí)，取當(dāng)前象素(xi,yi)的右上方象素( 玉+1，%+1 ):?而當(dāng)e<0時(shí)，更接近于右方象素(蒼+1，% )0可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換:e'=2*e*dx例：Line:P0(0,0),例：Line:P0(0,0),Pl(5,2)Xye00-0.5I0-0.1210.331-0.3420.152-0.5大于零，y加一，小于零，不變voidBresenhamline(intx0,intyO,intxl,intyl,intcolor){intx,y,dx,dy;floatk,e;dx=xl-xO,dy=yl-yO,k=dy/dx;e=-0.5,x=x0,y=yO;for(i=0;i<dx;i++){drawpixel(x,y,color);x=x+l,e=e+k;if(e>0){y++,e=e-l;}}2.2圓弧的掃描轉(zhuǎn)換算法圓的特征:八對(duì)稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集中點(diǎn)畫圓法：考慮中心在原點(diǎn)，半徑為R的第二個(gè)8分圓，構(gòu)造判別式(圓方程)d=F(M)=F(xp+\,yp-0.5)=(xp+l)2+(yp-0.5)2-/?2若d<0,則取Pl為下一象素，而且再下一象素的判別式為d'=F(xp+2,yp-0.5)=(x?+2)2+(yp-0.5)2-R2=d+2xp+3若d>=0,則應(yīng)取P2為下一象素，而且下一象素的判別式為d,=F(Xp+2,yp-1.5)=(xp+2)2+(yp-l.5)2-R2=d+2(xp-yp)+5第一個(gè)象素是(0,R),判別式d的初始值為=尸(1,E-O.5)=1.25-R為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。使用e=d-0.25代替deO=l-RMidPointCircle(intrintcolor){intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);〃顯示圓弧上的八個(gè)對(duì)稱點(diǎn)while(x<=y){if(d<0) d+=2*x+3;else{d+=2*(x-y)+5;y-;}x++;circlepoints(x,y,color);小結(jié)：本課主要介紹了繪制現(xiàn)寬為一個(gè)像素的直線的3個(gè)常用算法：DDA、analyzer,數(shù)值微分法，中點(diǎn)畫線法和Bresenham算法作業(yè)：.描述直線掃描的DDA算法、中點(diǎn)畫線算法、Bresenham算法，并用程序?qū)崿F(xiàn)Bresenham算法。.用中點(diǎn)畫線法掃描轉(zhuǎn)換從點(diǎn)(1,0)到(4,7)經(jīng)過(guò)的直線段，并給出每一補(bǔ)的判別值。三.光柵圖形學(xué)(二)課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：1.使學(xué)生掌握多邊形的掃描轉(zhuǎn)換。.使學(xué)生了解計(jì)算機(jī)是如何顯示字符的。.使學(xué)生了解計(jì)算機(jī)圖形裁剪。教學(xué)重點(diǎn)：計(jì)算機(jī)圖形裁剪教學(xué)難點(diǎn)：多邊行的掃描轉(zhuǎn)換與區(qū)域填充教學(xué)過(guò)程：2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充?多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。?多邊形的掃描轉(zhuǎn)換:把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域填充:指先將區(qū)域的點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。多邊形的掃描轉(zhuǎn)換掃描線算法基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟：求交、排序、配對(duì)、填色數(shù)據(jù)結(jié)構(gòu)1、活性邊表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中結(jié)點(diǎn)內(nèi)容x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)

△x：從當(dāng)前掃描線到下一條掃描線間X的增量ymax：該邊所交的最高掃描線號(hào)ymaxP6P1 P5P6 P4P5 P3P4I—[TT0171T~13.51 7D-H7I2I8I~|--|11|0|8TA"!A△xymax B△xymax C△xymax D△xymax2、新邊表（NET）：存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為ymin,則該邊就放在掃描線ymin的新邊表中8765876543210P4P5 P5P6]5|2|8| H-5|7|A|-111|0|8|A|P3P4H2|0|7|A|P6P115|-3|2| 5|3|3|A|P1P2 P2P3上圖所示各條掃描線的新邊表NET假定當(dāng)前掃描線與多邊形某一條邊的交點(diǎn)的x坐標(biāo)為x,則下一條掃描線與該邊的交點(diǎn)不要重計(jì)算，只要加一個(gè)增量^x。設(shè)該邊的直線方程為：ax+by+c=0；若丫=丫。x=xi；則當(dāng)y=yi+l時(shí)，七+1=7（一?。?1-G）=為一7；其中Ax=-%為常數(shù)掃描線與多邊形的頂點(diǎn)或邊界相交時(shí)，必須正確的交點(diǎn)的取舍。只需檢杳頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值。按這兩由y值中大于交點(diǎn)y值的個(gè)數(shù)是0,1,2來(lái)決定。voidpolyfill（polygon,color）intcolor;多邊形polygon;{for（各條掃描線i）（初始化新邊表頭指針NET[i]；IEymin=i的邊放進(jìn)邊表NET[i];）y=最低掃描線號(hào)；初始化活性邊表AET為空；for（各條掃描線i）把新邊表NET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列;

遍歷AET表，把配對(duì)交點(diǎn)區(qū)間(左閉右開)上的象素(x,y),用drawpixel(x,y,color)改寫象素顏色值；遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增Ax；若允許多邊形的邊自相交，則用冒泡排序法對(duì)AET表重新排序；邊界標(biāo)志算法基本思想：?幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打—L-木小??然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。?使用一個(gè)布爾量inside來(lái)指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。算法過(guò)程voidedgemark_fi11(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x)(if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside!=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);))用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。2.3.2區(qū)域填充算法區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種表示形式。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。四連通區(qū)域八連通區(qū)域區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的四連通區(qū)域八連通區(qū)域四個(gè)方向運(yùn)動(dòng) 八個(gè)方向運(yùn)動(dòng)?表示內(nèi)點(diǎn) o表示邊界點(diǎn)區(qū)域填充的遞歸算法內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法：voidFloodFill4(intx,inty,intoldcolor,intnewcolor){if(getpixel(x,y)==oldcolor)〃屬于區(qū)域內(nèi)點(diǎn)oldcolor{ drawpixel(x,y,newcolor);FloodFill4(x,y+l,oldcolor,newcolor);FloodFill4(x,y-1,oldcolor,newcolor);FloodFill4(x-l,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor);)}邊界表示的4連通區(qū)域的遞歸填充算法：voidBoundaryFiI14(intx,inty,intboundarycolor,intnewcolor){intcolor;if(color!=newcolor&&color!=boundarycolor){ drawpixel(x,y,newcolor);BoundaryFill4(x,y+l,boundarycolor,newcolor);BoundaryFill4(x,y-l,boundarycolor,newcolor);BoundaryFill4(x-l,y,boundarycolor,newcolor);BoundaryFill4(x+l,y,boundarycolor,newcolor);23.2.2區(qū)域填充的掃描線算法算法步驟：首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。(1)初始化：堆棧置空。將種子點(diǎn)(x,y)入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素(x,y),以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)(x,y)出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間［xl,xr］中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第

(2)步。上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。2.4字符字符指數(shù)字、字母、漢字等符號(hào)。計(jì)算機(jī)中字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)。國(guó)際上最流行的字符集：“美國(guó)信息交換用標(biāo)準(zhǔn)代碼集”，簡(jiǎn)稱ASCII碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128個(gè)字符；包括字母、標(biāo)點(diǎn)、運(yùn)算符以及一些特殊符號(hào)。漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集：GB2312-80o該字符集分為94個(gè)區(qū)，94個(gè)位，每個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼共同標(biāo)識(shí)。區(qū)碼和位碼各用一個(gè)字節(jié)表示。為了能夠區(qū)分ASCII碼與漢字編碼，采用字節(jié)的最高位來(lái)標(biāo)識(shí)：最高位為。表示ASCII碼；最高位為1表示表示漢字編碼。字庫(kù)：為了在顯示器等輸出設(shè)備上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字庫(kù)。字庫(kù)中存儲(chǔ)了每個(gè)字符的形狀信息，字庫(kù)分為矢量型和點(diǎn)陣型兩種。點(diǎn)陣字符:每個(gè)字符由一個(gè)位圖表示，該位為1表示字符的筆畫經(jīng)過(guò)此位，對(duì)應(yīng)于此位的象素應(yīng)置為字符顏色。該位為0表示字符的筆畫不經(jīng)過(guò)此位，對(duì)應(yīng)于此位的象素應(yīng)置為背景顏色。1111111110001100110I01100110011111000110口110011001101111110000000000點(diǎn)陣字符點(diǎn)陣字庫(kù)中的位圖表示在實(shí)際應(yīng)用中，有多種字體(如宋體、楷體等)，每種字體又有多種大小型號(hào)，因此字庫(kù)的存儲(chǔ)空間是很龐大的。解決這個(gè)問(wèn)題一般采用壓縮技術(shù)。點(diǎn)陣字符的顯示分為兩步。首先從字庫(kù)中將它的位圖檢索出來(lái)。然后將檢索到的位圖寫到幀緩沖器中。矢量字符:記錄字符的筆畫信息，而不是整個(gè)位圖，具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。對(duì)于字符的旋轉(zhuǎn)、縮放等變換，點(diǎn)陣字符的變換需要對(duì)表示字符位圖中的每一象素進(jìn)行；矢量字符的變換只要對(duì)其筆畫端點(diǎn)進(jìn)行變換就可以了。矢量字符的顯示也分為兩步。顯示：首先從字庫(kù)中將它的字符信息。然后取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。特點(diǎn)：?點(diǎn)陣字符：存儲(chǔ)量大，易于顯示矢量字符：存儲(chǔ)量小，美觀，變換方便；但需要光柵化后才能顯示。2.5裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過(guò)程稱為裁剪。在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部存儲(chǔ)的圖形往往比較大，而屏幕顯示的只是圖的一部分。

最簡(jiǎn)單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗內(nèi)。但那樣太費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。直線段裁剪直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。Cohen-Sutherland裁剪基本思想：對(duì)于每條線段P1P2分為三種情況處理分為三種情況處理：（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡(jiǎn)稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。（3）若線段不滿足“取”或“棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。為快速判斷，采用如下編碼方法：每個(gè)區(qū)域賦予4位編碼C（C/CC[y>yma^othery<Vminotherother線段裁剪y>yma^othery<Vminotherother線段裁剪-若P1P2完全在窗口內(nèi)codel=0,且code2=0,則“取”-若P1P2明顯在窗口外codel&code2W0,貝『‘棄"-在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。-計(jì)算線段Pl(xl,yl)P2(x2,y2)與窗口邊界的交點(diǎn)if(LEFT&code!=0)

{x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);}elseif(RIGHT&code!=0){x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);}elseif(BOTTOM&code!=0){y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);}編碼的思想在圖形學(xué)中非常重要。Sutherland：Coons,圖靈，IEEE計(jì)算機(jī)先驅(qū)獎(jiǎng)。中點(diǎn)分割裁剪算法基本思想：與前--種Cohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況：全在、完全不在和線段和窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。A、B分別為距PO、P1最近的可見點(diǎn)，Pm為P0P1中點(diǎn)從出發(fā)找最近可見點(diǎn)的方法先求出幾巴的中點(diǎn)匕若尼匕不是顯然不可見的，并且玲匕在窗口中有可見部分，則距尸消最近的可見點(diǎn)一定落在凡上，所以用尼匕代替痣尸加；否則取匕6代替外巴再對(duì)新的尸治求中點(diǎn)匕。重復(fù)上述過(guò)程，直到？書長(zhǎng)度小于給定的控制常數(shù)為止,此時(shí)P,?收斂于交點(diǎn)。從片出發(fā)找最近可見點(diǎn)采用上面類似方法。梁友棟一Barsky算法梁-Barsky算法的兒何含義：入邊、出邊與端點(diǎn)參數(shù)化形式寫出裁剪條件：XL<%1+t/Ax<XRYB<yt+必y<YT可以統(tǒng)一表示為形式：Pi=-Ax % —XMPk—QkP2=& /=XR-演P3=-^y Q\=y\-ybp4=^y %="一%入邊出邊

入邊Pk=0且%<0,則線段完全在邊界外外20,則該線段平行于裁剪邊界并且在窗口內(nèi)。當(dāng)Pkw。，?當(dāng)Pk<0,線段從裁剪邊界延長(zhǎng)線的外部延伸到內(nèi)部。?當(dāng)Pk>0,線段從裁剪邊界延長(zhǎng)線的內(nèi)部延伸到外部。對(duì)于每條直線，可以計(jì)算出參數(shù)ul和u2,它們定義了在裁剪矩形內(nèi)的線段部分ul的值由線段從外到內(nèi)遇到的矩形邊界所決定(p<0)o對(duì)這些邊界計(jì)算rk=qk/pkoul取0和各個(gè)rk值之中的最大值。u2的值由線段從內(nèi)到外遇到的矩形邊界所決定(p>0)o對(duì)這些邊界計(jì)算rk=qk/pk。u2取1和各個(gè)rk值之中的最小值。如果ul>u2,則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個(gè)值ul,u2計(jì)算出來(lái)。voidLB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatxl,yl,x2,y2,XL,XR,YB,YT;{floatdx,dy,ul,u2;tl=0;tu=1;dx=x2-x1;dy=y2-y1;if(ClipT(-dx,xl-Xl,&ul,&u2)if(ClipT(dx,XR-xl,&ul,&u2)if(ClipT(-dy,yl-YB,&ul,&u2)if(ClipT(dy,YT-yl,&ul,&u2){displayline(x14-u1*dx,y1+u1*dy,xl+u2*dx,yl+u2*dy)return;}boolClipT(p,q,ul,u2)floatp,q,*ul,*u2;{floatr;if(P<0){r=q/p;if(r>*u2)returnFALSE;elseif(r>*ul){*ul=r;returnTRUE;elseif(p>0)

{r=p/q;if(r<*u1)returnFALSE;elseif(r<*u2){*u2=r;returnTRUE;}}elseif(q<0)returnFALSE;returnTRUE;多邊形裁剪基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線該線把平面分成兩個(gè)部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點(diǎn)S、P。它們與裁剪線的位置關(guān)系只有四種對(duì)于情況（1）僅輸出頂點(diǎn)P;情況（2）輸出。個(gè)頂點(diǎn)；情況（3）輸出線段SP與裁剪線的交點(diǎn)I；情況（4）輸出線段SP與裁剪線的交點(diǎn)I和終點(diǎn)P上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪，得到一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過(guò)程的輸入。對(duì)于每一條裁剪邊，只是判斷點(diǎn)在窗口哪一側(cè)以及求線段SP與裁剪邊的交點(diǎn)算法應(yīng)隨之改變。其他窗口的裁剪圓域窗口裁剪：潛望鏡、…任意（凸）多邊形裁剪：個(gè)性化電腦顯示器定制，字符裁剪串精度:將包圍字串的外接矩形對(duì)窗口作裁剪字符精度:將包圍字的外接矩形對(duì)窗口作裁剪以及筆畫'象素精度:將筆劃分解成直線段對(duì)窗口作裁剪spring']""STRING2 STRING2RINGSTRING2S''RINGspring']""STRING2 STRING2RINGSTRING2S''RINGSTRING2待裁剪字符串串精度裁剪字符精度裁剪象素精度裁剪小結(jié)：光柵圖形學(xué)的一個(gè)基本問(wèn)題是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，為了在顯示器等輸出設(shè)備上輸出字符，系統(tǒng)中必須有相應(yīng)的字庫(kù)。計(jì)算機(jī)中的字符由數(shù)字編碼唯一標(biāo)識(shí)。使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部?jī)?chǔ)存的圖形往往比較大，而屏幕顯示的只是圖的一部分，因此需要剪裁。作業(yè)：.描述多邊形掃描轉(zhuǎn)換的掃描線算法，并寫出偽碼。.字符串裁剪可按哪3個(gè)精度進(jìn)行？四.光柵圖形學(xué)(三)課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：1.使學(xué)生了解圖形走樣與如何反走樣。2.使學(xué)生了解圖形的消隱教學(xué)重點(diǎn)：圖形消隱教學(xué)難點(diǎn)：圖形消隱教學(xué)過(guò)程：2.6反走樣?用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing),用于減少或消除這種效果的技術(shù)稱為反走樣(antialiasing)提高分辨率把顯示器分辨率提高一倍，直線經(jīng)過(guò)兩倍的象素，鋸齒也增加一-倍，但同時(shí)每個(gè)階梯的寬度也減小了一倍，所以顯示出的直線段看起來(lái)就平直光滑了一些。增加分辨率雖然簡(jiǎn)單，但是不經(jīng)濟(jì)的方法，有物理上的困難而且它也只能減輕而不能消除鋸齒問(wèn)題區(qū)域采樣基本思想：每個(gè)象素是一個(gè)具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長(zhǎng)矩形。當(dāng)直線段與象素有交時(shí)，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。有寬度的線條輪廓 象素相交的五種情況及用于計(jì)算面積的量面積計(jì)算情況⑴（5）陰影面積為：D2/2m；情況⑵（4）陰影面積為：D-m/2；TOC\o"1-5"\h\z情況⑶陰影面積為：l-D2/m /為了簡(jiǎn)化計(jì)算可以采用離散的方法 //n=9,k=3近似面積為1/3 /首先將屏幕象素均分成n個(gè)子象素， /伍到目然后計(jì)算中心點(diǎn)落在直線段內(nèi)的子象素的個(gè)數(shù)k。 才?小I.將屏幕該象素的亮度置為相交區(qū)域面積的近似值可k/n。 /非加權(quán)區(qū)域采樣方法有兩個(gè)缺點(diǎn)：象素的亮度與相交區(qū)域的面積成正比，而與相交區(qū)域落在象素內(nèi)的位置無(wú)關(guān)，這仍然會(huì)導(dǎo)致鋸齒效應(yīng)。直線條上沿理想直線方向的相鄰兩個(gè)象素有時(shí)會(huì)有較大的灰度差。加權(quán)區(qū)域取樣基本思想：使相交區(qū)域?qū)ο笏亓炼鹊呢暙I(xiàn)依賴于該區(qū)域與象素中心的距離，當(dāng)直線經(jīng)過(guò)該象素時(shí)，該象素的亮度F是在兩者相交區(qū)域A，上對(duì)濾波器（函數(shù)w）進(jìn)行積分的積分值?？刹捎秒x散計(jì)算方法4wl w2 卬3可采用離散計(jì)算方法4wl w2 卬3 1w4 vv5 w6 =— 216w7 卬8 w9 1?權(quán)函數(shù)w（x,y）為微面元dA與象素中心距離d的函數(shù)，縊國(guó)求出所有中心落于直線段內(nèi)的子象素，最后計(jì)算所有這些子象素對(duì)原象素亮度貢獻(xiàn)之和工嗎乘以象素的最大灰度值作為該象素的顯示灰度值。2.7消隱基本概念投影變換失去了深度信息，往往導(dǎo)致圖形的二義性，要消除二義性，就必須在繪制時(shí)消除被遮擋的不可見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，簡(jiǎn)稱為消隱。經(jīng)過(guò)消隱得到的投影圖稱為物體的真實(shí)圖形。長(zhǎng)方體線框投影圖的二義性消隱的對(duì)象是三維物體。三維體的表示主要有邊界表示和CSG表示等。消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān)。

線框圖 消隱圖 真實(shí)感圖形邊界表示（體、面、環(huán)、邊、點(diǎn)）圖3.2.圖3.2.10邊界表示消隱的分類按消隱對(duì)象分類?線消隱：消隱對(duì)象是物體上的邊，消除的是物體上不可見的邊。?面消隱：消隱對(duì)象是物體上的面，消除的是物體上不可見的面。Southerland按消隱空間分類? 物體空間的消隱算法（光線投射、Roberts）, 圖像空間的消隱算法（Z—buffer、掃描線、Warnock）? 物體空間和圖像空間的消隱算法（畫家算法）2.7.2消除隱藏線對(duì)造型的要求：在線框顯示模型中，要求造型系統(tǒng)中有面的信息，最好有體的信息。坐標(biāo)變換：將視點(diǎn)變換到Z軸的正無(wú)窮大處，視線方向變?yōu)閆軸的負(fù)方向。最基本的運(yùn)算：判斷面對(duì)線的遮擋關(guān)系.反復(fù)地進(jìn)行線線、線面之間的求交運(yùn)算包圍盒不交視點(diǎn)與線段同側(cè)分段交替取值包圍盒不交視點(diǎn)與線段同側(cè)分段交替取值（1）若線段的兩端點(diǎn)及視點(diǎn)在給定平面的同側(cè)，線段不被給定平面遮擋，轉(zhuǎn)7（2）若線段的投影與平面投影的包圍盒無(wú)交，線段不被給定平面遮擋，轉(zhuǎn)7（3）求直線與相應(yīng)無(wú)窮平面的交。若無(wú)交點(diǎn)，轉(zhuǎn)4O否則，交點(diǎn)在線段內(nèi)部或外部。若交點(diǎn)在線段內(nèi)部，交點(diǎn)將線段分成兩段，與視點(diǎn)同側(cè)的一段不被遮擋，另一段在視點(diǎn)異側(cè)，轉(zhuǎn)4再判；若交點(diǎn)在線段外部，轉(zhuǎn)4。(4)求所剩線段的投影與平面邊界投影的所有交點(diǎn)，并根據(jù)交點(diǎn)在原直線參數(shù)方程中的參數(shù)值求出Z值(即深度)。若無(wú)交點(diǎn)，轉(zhuǎn)5。(5)以上所求得的各交點(diǎn)將線段的投影分成若干段，求出第一段中點(diǎn)。(6)若第一段中點(diǎn)在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值進(jìn)行判斷。為了提高算法的效率，需要設(shè)法減少求交的工作量。若V?N>0,稱該多邊形為后向面。若V.N<0,稱該多邊形為前向面。后向面總是看不見的，不會(huì)由于后向面的遮擋，而使別的棱成為不可見的。因此計(jì)算時(shí)，可以把這些后向面全部去掉，這并不影響消隱結(jié)果?！竢前向面 后向面 多面體的隱藏線消除2.7.3消除隱藏面畫家算法(列表優(yōu)先算法)先把屏幕置成背景色，再把物體的各個(gè)面按其離視點(diǎn)的遠(yuǎn)近進(jìn)行排序，排序結(jié)果存在一張深度優(yōu)先級(jí)表中。然后按照從遠(yuǎn)到近的順序逐個(gè)繪制各個(gè)面。關(guān)鍵是如何對(duì)場(chǎng)景中的物體按深度排序?qū)?chǎng)景中的物體按深度排序深度重疊測(cè)試：Zmin(P)<Zmin(Q),若Zmax(P)<Zmin(Q),則P肯定不能遮擋Q=投影重疊判斷：P和Q在oxy平面上投影的包圍盒在x方向上不相交P和Q在oxy平面上投影的包圍盒在y方向上不相交P和Q在oxy平面上的投影不相交P在Q之后。P的各頂點(diǎn)均在Q的遠(yuǎn)離視點(diǎn)的一側(cè)Q在P之前。Q的各頂點(diǎn)均在P的靠近視點(diǎn)的--側(cè)精確的重疊測(cè)試：以上測(cè)試失敗，須作進(jìn)一步判斷。計(jì)算時(shí)不必具體求出重疊部分。在交點(diǎn)處進(jìn)行深度比較，只要能判斷出前后順序即可。若遇到多邊形相交或循環(huán)重疊的情況(如圖f),還必須在相交處分割多邊形，然后進(jìn)行判斷。P不遮擋Q的各種情況(ab,c,d,e)及互相遮擋f

2732Z緩沖區(qū)算法幀緩存來(lái)存放每個(gè)象素的顏色值，初值可放對(duì)應(yīng)背景顏色的值深度緩存來(lái)存放每個(gè)象素的深度值，初值取成Z的極小值。屏幕每個(gè)單元存放對(duì)應(yīng)象素的顏色值每個(gè)單元存放對(duì)應(yīng)象素的深度值屏幕每個(gè)單元存放對(duì)應(yīng)象素的顏色值每個(gè)單元存放對(duì)應(yīng)象素的深度值算法過(guò)程在把顯示對(duì)象的每個(gè)面上每?點(diǎn)的屬性(顏色或灰度)值填入幀緩沖器相應(yīng)單元前，要把這點(diǎn)的Z坐標(biāo)值和Z緩沖器中相應(yīng)單元的值進(jìn)行比較。只有前者大于后者時(shí)才改變幀緩沖器的那一單元的值，同時(shí)Z緩沖器中相應(yīng)單元的值也要改成這點(diǎn)的Z坐標(biāo)值。如果這點(diǎn)的Z坐標(biāo)值小于Z緩沖器中的值，則說(shuō)明對(duì)應(yīng)象素已經(jīng)顯示了對(duì)象上一個(gè)點(diǎn)的屬性，該點(diǎn)要比考慮的點(diǎn)更接近觀察點(diǎn)。對(duì)顯示對(duì)象的每個(gè)面上的每個(gè)點(diǎn)都做了上述處理后，便可得到消除了隱藏面的圖。Z-Buffer算法()(幀緩存全置為背景色深度緩存全置為最小Z值for(每一個(gè)多邊形){掃描轉(zhuǎn)換該多邊形for(該多邊形所覆蓋的每個(gè)象素(x,y)){ 計(jì)算該多邊形在該象素的深度值Z(x,y);if(Z(x,y)大于Z緩存在(x,y)的值){ 把Z(x,y)存入Z緩存中(x,y)處把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處由被測(cè)點(diǎn)P處向y=-oo方向作射線：交點(diǎn)個(gè)數(shù)是奇數(shù)，則被測(cè)點(diǎn)在多邊形內(nèi)部；否則，偶數(shù)，在多邊形外部。若射線正好經(jīng)過(guò)多邊形的頂點(diǎn)，則采用“左開右閉”的原則來(lái)實(shí)現(xiàn)。當(dāng)射線與某條邊的頂點(diǎn)相交時(shí)，若邊在射線的左側(cè)，交點(diǎn)有效，計(jì)數(shù)；若邊在射線的右側(cè)，交點(diǎn)無(wú)效，不計(jì)數(shù)。p(a)被測(cè)點(diǎn)p(a)被測(cè)點(diǎn)p在多邊形外(b)被測(cè)點(diǎn)p在多邊形內(nèi)以被測(cè)點(diǎn)為圓心，作單位圓，計(jì)算其在單位園上弧長(zhǎng)的代數(shù)和。代數(shù)和為0,點(diǎn)在多邊形外部；代數(shù)和為2兀，點(diǎn)在多邊形內(nèi)部;代數(shù)和為兀，點(diǎn)在多邊形邊上。2.7,3.3掃描線Z-buffer算法算法思想：點(diǎn)Buffer,面Buffer到線Buffer利用圖形的連貫性(指深度計(jì)算在處理當(dāng)前掃描線時(shí)，開??個(gè)一維數(shù)組作為當(dāng)前掃描線的Z-buffer。首先找出與當(dāng)前掃描線相關(guān)的多邊形，以及每個(gè)多邊形中相關(guān)的邊對(duì)。對(duì)每一個(gè)邊對(duì)之間的小區(qū)間上的各象素，計(jì)算深度，并與乙buffer中的值比較，找出各象素處可見平面。計(jì)算顏色，寫幀緩存。采用增量算法計(jì)算深度。掃描線Z-buffer算法(){建多邊形y表；對(duì)每一個(gè)多邊形根據(jù)頂點(diǎn)最小的y值，將多邊形置入多邊形y表?；罨噙呅伪鞟PT,活化邊表AET初始化為空。For(每條掃描線i,i從小到大){ 1?幀緩存CB置為背景色。.深度緩存ZB(一維數(shù)組)置為無(wú)窮大。.將對(duì)應(yīng)掃描線i的，多邊形y表中的多邊形加入到活化多邊形表APT中。.對(duì)新加入的多邊形，生成其相應(yīng)的邊Y表。.對(duì)APT中每一個(gè)多邊形，若其邊Y表中對(duì)應(yīng)掃描線I增加了新的邊，將新的邊配對(duì)，加到活化邊對(duì)表AET中。.對(duì)AET中的每一對(duì)邊：對(duì)xl<x<xi?的每?個(gè)象素，按增量公式z=z-Aza計(jì)算各點(diǎn)深度depth。與ZB中的量比較，depth<ZB(I),則令ZB⑴=depth,并計(jì)算顏色值，寫幀緩存。.刪除APT中，多邊形頂點(diǎn)最大y坐標(biāo)為I的多邊形，并刪除相應(yīng)的邊。.對(duì)AET中的每一個(gè)邊對(duì)，作如下處理：刪除ylmax或ylmax已等于i的邊。若一邊對(duì)中只刪除了其中一邊，需對(duì)該多邊形的邊重新配對(duì)。用增量公式計(jì)算新的xl、xr和力區(qū)間掃描線算法基本思想：?它是把當(dāng)前掃描線與各多邊形在投影平面的投影的交點(diǎn)進(jìn)行排序后，使掃描線分為若干子區(qū)間。只要在區(qū)間任一點(diǎn)處找出在該處z值最大的一個(gè)面，這個(gè)區(qū)間上的每一個(gè)象素就用這個(gè)面的顏色來(lái)顯示。?算法的優(yōu)點(diǎn)：將逐點(diǎn)（象素、Pixel）計(jì)算改為逐段計(jì)算?如何確定小區(qū)間的顏色可分為三種情況：（1）小區(qū)間上沒有任何多邊形，如[a4,a5],這時(shí)該小區(qū) 間用背景色顯示。（2）小區(qū)間上只有一個(gè)多邊形，如[al,a2][a5,a6]這時(shí)可以對(duì)應(yīng)多邊形在該處的顏色顯示。（3）小區(qū)間上存在兩個(gè)或兩個(gè)以上的多邊，形如[a6,a7],必須通過(guò)深度測(cè)試判斷哪個(gè)多邊形可見。兩個(gè)平面在屏幕上的投影 無(wú)貫穿的情形兩個(gè)平面在屏幕上的投影 無(wú)貫穿的情形 相互貫穿的情形若允許物體表面相互貫穿時(shí)，還必須求出它們?cè)趻呙杵矫妫╖X平面）的交點(diǎn)。用這些交點(diǎn)把該小區(qū)間分成更小的子區(qū)間（稱為間隔），在這些間隔上決定哪個(gè)多邊形可見。如將[a2,a3]區(qū)間分成[a2,b][b,a3]兩個(gè)子區(qū)間。確定某間隔內(nèi)哪一多邊形可見：可在間隔內(nèi)任取一采樣點(diǎn)（如間隔中點(diǎn)），分析該點(diǎn)處哪個(gè)多邊形離視點(diǎn)最近，該多邊形即是在該間隔內(nèi)可見的多邊形。區(qū)域子分割算法（Warnack算法）基本思想：把物體投影到全屏幕窗口上，然后遞歸分割窗口，直到窗口內(nèi)目標(biāo)足夠簡(jiǎn)單，可以顯示為止。區(qū)域子分的過(guò)程算法步驟：該算法把初始窗口取作屏幕坐標(biāo)系的矩形，將場(chǎng)景中的多邊形投影到窗口內(nèi)。如果窗口內(nèi)沒有物體則按背景色顯示；,若窗口內(nèi)只有一-個(gè)面，則把該面顯示出來(lái)。否則，窗口內(nèi)含有兩個(gè)以上的面，則把窗口等分成四個(gè)子窗口。對(duì)每個(gè)小窗口再做上

述同樣的處理。這樣反復(fù)地進(jìn)行下去。如果到某個(gè)時(shí)刻，窗口僅有象素那么大，而窗口內(nèi)仍有兩個(gè)以上的面，這時(shí)不必再分割，只要取窗口內(nèi)最近的可見面的顏色或所有可見面的平均顏色作為該象素的值。窗口與多邊形的覆蓋關(guān)系有四種：內(nèi)含、相交包圍和分離。如圖所示。內(nèi)含 多邊形與窗口相交包圍 窗口和多邊形分離下列情況之一發(fā)生時(shí)，窗口足夠簡(jiǎn)單，可以直接顯示：所有多邊形均與窗口分離。該窗口置背景色只有一個(gè)多邊形與窗口相交，或該多邊形包含窗口，則先整個(gè)窗口置背景色，在對(duì)多邊形在窗口內(nèi)部分掃描線算法繪制。有?個(gè)多邊形包圍了窗口，或窗口與多個(gè)多邊形相交，但有一個(gè)多邊形包圍窗口，而且在最前面最靠近觀察點(diǎn)。區(qū)域子分割算法流圖2.73.6光線投射算法基本思想：考察由視點(diǎn)出發(fā)穿過(guò)觀察屏幕的?象素而射入場(chǎng)景的一條射線，則可確定出場(chǎng)景中與該射線相交的物體。在計(jì)算出光線與物體表面的交點(diǎn)之后，離象素最近的交點(diǎn)的所在面片的顏色為該象素的顏色；如果沒有交點(diǎn)，說(shuō)明沒有多邊形的投影覆蓋此象素，用背景色顯示它即可。將通過(guò)屏幕各象素的投影線與場(chǎng)景中的物體表面求交for屏幕上的每一象素{形成通過(guò)該屏幕象素(u,v)的射線；for場(chǎng)景中的每個(gè)物體{ 將射線與該物體求交；if存在交點(diǎn)以最近的交點(diǎn)所屬的顏色顯示象素(u,v)else以背景色顯示象素(u,v)小結(jié)：本課主要了解在光柵顯示系統(tǒng)中，用來(lái)表示圖形的基本單位卻是一個(gè)個(gè)離散的像素。這種用離散量表示連續(xù)量引起的失真現(xiàn)象就是走樣。用計(jì)算機(jī)生成三維物體的真實(shí)圖形，是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容。作業(yè)：.解釋走樣和反走樣的概念，并描述反走樣的主要方法。.描述消隱的掃描線Z-Buffer算法，并與其他兩種Z-Buffer算法進(jìn)行比較。五.幾何造型技術(shù)(一)課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：1.使學(xué)生掌握參數(shù)曲線的表示及其概念。2.使學(xué)生掌握什么叫參數(shù)化，參數(shù)曲線的代數(shù)和兒何形式。教學(xué)重點(diǎn)：參數(shù)曲線的代數(shù)和幾何形式教學(xué)難點(diǎn)：參數(shù)化教學(xué)過(guò)程：參數(shù)曲線和曲面曲線曲面參數(shù)表示?顯式表示:y=f(x),隱式表示:f(x,y)=0,參數(shù)表示:P(t)=[x(t),y(t),z(t)]顯式或隱式表示存在下述問(wèn)題：1)與坐標(biāo)軸相關(guān)；2)會(huì)出現(xiàn)斜率為無(wú)窮大的情形(如垂線)；3)不便于計(jì)算機(jī)編程。參數(shù)表示:曲線上任一點(diǎn)的坐標(biāo)均表示成給定參數(shù)的函數(shù)。假定用t表示參數(shù)，平面曲線上任一點(diǎn)P可表示為：P(0=L⑺，y⑺]? 空間曲線上任一三維點(diǎn)p可表示為：P(?)=卜⑺，y⑺，z⑺], 參數(shù)表示例子：- 直線P(t)=Pi+(乙一小t￡[0,1]- 圓參數(shù)表示的優(yōu)點(diǎn)：1)以滿足幾何不變性的要求。2)有更大的自由度來(lái)控制曲線、曲面的形狀3)對(duì)曲線、曲面進(jìn)行變換，可對(duì)其參數(shù)方程直接進(jìn)行幾何變換。4)便于處理斜率為無(wú)窮大的情形，不會(huì)因此而中斷計(jì)算。5)便于用戶把低維空間中曲線、曲面擴(kuò)展到高維空間去。

6)規(guī)格化的參數(shù)變量tW[0,1],使其相應(yīng)的兒何分量是有界的，而不必用另外的參數(shù)去定義邊界。7)易于用矢量和矩陣表示幾何分量，簡(jiǎn)化了計(jì)算。3.1.2位置矢量、切矢量、法矢量、曲率和撓率曲線上任一點(diǎn)的位置矢量可表示為：P(t)=[x(t),y(t),z(t)]；切向量(切矢量) dP\P選擇弧長(zhǎng)s作為參數(shù)，則2ds曰+As是單位切矢根據(jù)弧長(zhǎng)微分公式有：(ds)2=(dx)2+(dy)2+(dz)2(ds/dt)2=(dx/dt)2+{dy/出丫+(dz/dt)2=P(r)|—此小。JP_JPdt_P\t), 于是有~ds~~dt'~ds~\P\A'即為單位矢量法矢量空 1 1與公平行的法矢稱為曲線在該點(diǎn)的主法矢N, 矢量積B=TxN是第三個(gè)單位矢量，它垂直于T和N。把平行于矢量B的法矢稱為曲線的副法矢矢我們可以推導(dǎo)出：p‘⑴xp〃a)N=BxT=(PQ)xP"?))xPQ)

|(尸'⑺xP"S)xN=BxT=- T(切矢)、N(主法矢)和B(副法矢)構(gòu)成了曲線上的活動(dòng)坐標(biāo)架N、B構(gòu)成的平面稱為法平面，N、T構(gòu)成的平面稱為密切平面，B、T構(gòu)成的平面稱為從切平面。曲率和撓率limAj->0ATAslimAjtO曲率和撓率limAj->0ATAslimAjtOAT△$△eAj「lim絲

zo|Ay稱為曲率，其幾何意義是曲線的單位切矢對(duì)弧長(zhǎng)的轉(zhuǎn)動(dòng)率曲率k的倒數(shù)0=一稱為曲率半徑。K撓率T的絕對(duì)值等于副法線方向(或密切平面)對(duì)于弧長(zhǎng)的轉(zhuǎn)動(dòng)率.\t\tI=lim11AsAs.對(duì)于一般參數(shù)t,我們可以推導(dǎo)出曲率和撓率的計(jì)算公式如下:”⑺)

xP"(t))2插值、擬合、逼近和光順給定一組有序的數(shù)據(jù)點(diǎn)Pi，i=0,1, 構(gòu)造一條曲線順序通過(guò)這些數(shù)據(jù)點(diǎn)，稱為對(duì)這些數(shù)據(jù)點(diǎn)進(jìn)行插值，所構(gòu)造的曲線稱為插值曲線。線性插值：假設(shè)給定函數(shù)f(x)在兩個(gè)不同點(diǎn)xl和x2的值，用一個(gè)線形函數(shù)：y=ax+b,近似代替，稱為的線性插值函數(shù)。拋物線插值:已知在三個(gè)互異點(diǎn)X1,X2,X3的函數(shù)值為必,為，/3，要求構(gòu)造一個(gè)函數(shù)(p{x}=ax1+bx+c使拋物線夕(％)在結(jié)點(diǎn)X,.(z=1,2,3)處與/(X)在七處的值相等擬合：構(gòu)造一條曲線使之在某種意義下最接近給定的數(shù)據(jù)點(diǎn)(但未必通過(guò)這些點(diǎn))，所構(gòu)造的曲線為擬合曲線。在計(jì)算數(shù)學(xué)中，逼近通常指用…些性質(zhì)較好的函數(shù)近似表示一些性質(zhì)不好的函數(shù)。在計(jì)算機(jī)圖形學(xué)中，逼近繼承了這方面的含義，因此插值和擬合都可以視為逼近。光順(Firing)指曲線的拐點(diǎn)不能太多。對(duì)平面曲線而言，相對(duì)光順的條件是：a.具有二階幾何連續(xù)性(G2)；b.不存在多余拐點(diǎn)和奇異點(diǎn)；c.曲率變化較小。參數(shù)化過(guò)三點(diǎn)PO、P1和P2構(gòu)造參數(shù)表示的插值多項(xiàng)式可以有無(wú)數(shù)條，這是因?yàn)閷?duì)應(yīng)地參數(shù)t,在[0,1]區(qū)間中有無(wú)數(shù)種取法。即P0、P1和P2可對(duì)應(yīng)不同的參數(shù)值，比如，t0=0冉==1，一zo=0，。=t42=1，2或 3其中每個(gè)參數(shù)值稱為節(jié)點(diǎn)(knot)。對(duì)于一條插值曲線，型值點(diǎn)外，匕…記,與其參數(shù)域止上。/"內(nèi)的節(jié)點(diǎn)之間有一種對(duì)應(yīng)關(guān)系。對(duì)于一組有序的型值點(diǎn)，所確定一種參數(shù)分割，稱之這組型值點(diǎn)的參數(shù)化。參數(shù)化常用方法有：均勻參數(shù)化(等距參數(shù)化)節(jié)點(diǎn)在參數(shù)軸上呈等距分布，Li=% +正常數(shù)。累加弦長(zhǎng)參數(shù)化卜=。 \p,[ti=*+,匕_獷=1,2,…1n這種參數(shù)法如實(shí)反映了型值點(diǎn)按弦長(zhǎng)的分布情況，能夠克服型值點(diǎn)按弦長(zhǎng)分布不均勻的情況下采用均勻參數(shù)化所出現(xiàn)的問(wèn)題。向心參數(shù)化法向心參數(shù)化法假設(shè)在一段曲線弧上的向心力與曲線切矢從該弧段始端至末端的轉(zhuǎn)角成正比,加上一些簡(jiǎn)化假設(shè)，得到向心參數(shù)化法。此法尤其適用于非均勻型值點(diǎn)分布。修正弦長(zhǎng)參數(shù)化法小=0[ti=(+KjMJi=1,2,…,〃k|M|q]’ 2,弭2I+M」q=min[乃-=I△闈=0弦長(zhǎng)修正系數(shù)Ki>=lo從公式可知，與前后鄰弦長(zhǎng)及相比，若越小，且與前后鄰弦邊夾角的外角qi-1和qi(不超過(guò)時(shí))越大，則修正系數(shù)就Ki就越大。參數(shù)區(qū)間的規(guī)格化我們通常將參數(shù)區(qū)間上0冊(cè)」規(guī)格化為[0,1], [t0r?]*[0,l],只需對(duì)參數(shù)化區(qū)間作如下處理：t..，o二。，乙==0,1,…簿3.1.5參數(shù)曲線的代數(shù)和幾何形式我們以三次參數(shù)曲線為例，討論參數(shù)曲線的代數(shù)和兒何形式。?代數(shù)形式x(t)=a3f+a2xt2+alxt+aOx<y(t)=a3yt3+a2yr+aiyt+aOyte[0,1]z(t)=aizty+a2zt2+aizt+aOz上述代數(shù)式寫成矢量式是P(r)=a3t3+a^t2+a1t+a0tg[0,1]? 幾何形式對(duì)三次參數(shù)曲線，若用其端點(diǎn)位矢P(0)、P(l)和切矢PC(O)、Pc(l)描述。將P(0)、P(l)、P,(0)和Pc(l)簡(jiǎn)記為PO、Pl、PR和Pel,代入得 roq=4<ci7=-34+3月-2P0—6a3=2尼-2PX+-+片- 令：人⑴=2"一3戶+16。)=—2r+3產(chǎn)G。⑺=/一2『+1 G?)=/一產(chǎn)可將其簡(jiǎn)化為：尸⑺=FqP0+F^+G0P0+Gf；tG[0,1]上式是三次Hermite(Ferguson)曲線的幾何形式，幾何系數(shù)是P0、Pl、P0O和P010耳),片,G()，G稱為調(diào)和函數(shù)(或混合函數(shù))3.1.6連續(xù)性? 曲線間連接的光滑度的度量有兩種：函數(shù)的可微性：組合參數(shù)曲線在連接處具有直到n階連續(xù)導(dǎo)矢，即n階連續(xù)可微，這類光滑度稱之為 或n階參數(shù)連續(xù)性。C"兒何連續(xù)性：組合曲線在連接處滿足不同老"的某…組約束條件，稱為具有n階幾何連續(xù)性，簡(jiǎn)記為 。 C"反例：g0Q131+(1嚴(yán)M3 7 31 O①'(「)=4僅一匕)①'(1+)=￡僅一匕)? 若要求在結(jié)合處達(dá)到G°連續(xù)或G°連續(xù)，即兩曲線在結(jié)合處位置連續(xù)：P⑴=Q(0)若要求在結(jié)合處達(dá)到G1連續(xù)，就是說(shuō)兩條曲線在結(jié)合處在滿足G°連續(xù)的條件下,并有公共的切矢0(0)=社⑴(?>0)當(dāng)a=l時(shí)，G1連續(xù)就成為C'連續(xù)若要求在結(jié)合處達(dá)到G2連續(xù)，就是說(shuō)兩條曲線在結(jié)合處在滿足G1連續(xù)的條件下，并有公共的曲率矢：P⑴xP⑴O(0)xQ(0)|A(1)|3 |G,(0)|3這個(gè)關(guān)系可寫為：?！?0)=。2尸飛])+優(yōu)(])，為任意常數(shù)。當(dāng)。=1,力=0時(shí)，G2連續(xù)就成為連續(xù)。圖3.1.7兩條曲線的連續(xù)性我們已經(jīng)看到，連續(xù)保證G】連續(xù)，。2連續(xù)能保證G2連續(xù)，但反過(guò)來(lái)不行。也就是說(shuō)C"連續(xù)的條件比G"連續(xù)的條件要苛刻。3.1.7參數(shù)曲面基本概念一張定義在矩形域上的參數(shù)曲面可以表示為X=<y=y(u.v),(w,v)g[0,1]x[0,1]z=z(w,v)尸(〃,v)=(x(w,v),y(w,v),z(〃,v))參數(shù)曲面的兒個(gè)基本概念.曲面上的點(diǎn)：將給定的參數(shù)值“0,%代入?yún)?shù)方程，可得曲面上的點(diǎn).曲面上一點(diǎn)的切向量(切矢)：SP(u,v)dP(u,v)dul，=UQdvu=u°

v=v0 v=v0.曲面上一點(diǎn)的法向量(法矢)dP(M,v)dP(M,v)—du—"刃。'—dv-

V=vo V=Vq.角點(diǎn)P(O,O)P(O,1)P(1,O)P(l,l).邊界線：小結(jié)：本課介紹曲線、曲面可以用顯示、隱式和參數(shù)表示。由于參數(shù)表示的曲線、曲面具有幾何不變性等優(yōu)點(diǎn)，計(jì)算機(jī)圖形學(xué)中常用參數(shù)形式描述曲線、曲面。作業(yè)：.參數(shù)曲線曲面有兒種表示形式？.設(shè)有控制頂點(diǎn)為a(0,0),b(48,96),c(120,120),d(216,72)的三次Bezier曲線P(t),試計(jì)算P(0,4)的(x,y)坐標(biāo)，并寫出(x(t),y(t))的多項(xiàng)式表示。六.幾何造型技術(shù)(二)課型：理論講授課課時(shí)：3課時(shí)教學(xué)目標(biāo)：1.使學(xué)生掌握Bezier曲線的定義和性質(zhì)。.使學(xué)生掌握Bezier曲線的拼接、升階與降階。.使學(xué)生了解Bezier曲面。教學(xué)重點(diǎn)：Bezier曲線的拼接、升階與降階教學(xué)難點(diǎn)：Bezier曲面教學(xué)過(guò)程：3.2Bezier曲線與曲面由于幾何外形設(shè)計(jì)的要求越來(lái)越高，傳統(tǒng)的曲線曲面表示方法，已不能滿足用戶的需求。1962年，法國(guó)雷諾汽車公司的P.E.Bezier構(gòu)造了--種以逼近為基礎(chǔ)的參數(shù)曲線和曲面的設(shè)計(jì)方法，并用這種方法完成了一種稱為UNISURF的曲線和曲面設(shè)計(jì)系統(tǒng)，1972年，該系統(tǒng)被投入了應(yīng)用。Bezier方法將函數(shù)逼近同幾何表示結(jié)合起來(lái)，使得設(shè)計(jì)師在計(jì)算機(jī)上就象使用作圖丫⑴這Z丫⑴這Z九")4(=01,i=0,

九")=(5〃1(17嚴(yán)-1、?典故日本的穗板：天上掉下來(lái)A為邊向量3.2.1Bezier曲線的定義和性質(zhì)定義給定空間n+1個(gè)點(diǎn)的位置矢量Pi(i=0,1,2, n),則Bezier曲線可定義為:。。)=￡尸及〃0), ^[o,i]i=0其中，Pi構(gòu)成該Bezier曲線的特征多邊形，Bi,n⑴是n次Bernstein基函數(shù):(i=0,L )0°=1,0!=1Betnstein基函數(shù)的性質(zhì)(1)正性

=Qt=0,1>Org(0,1),z=1,2,_1;(2)端點(diǎn)性質(zhì)(2)端點(diǎn)性質(zhì)fl%(o)=[o%(1)=];(i=0)otherwise(i=〃)

otlienvise(3)權(quán)性Z%⑺三"6(0,1)z=0由二項(xiàng)式定理可知：n 幾X紇〃⑺=Ec/a-)1=1a-)+〃〃三1i=0 i=0(4)對(duì)稱性Bjn(才)=n(t)(5)遞推性。%⑴=(l-r)%T⑺+回_皿()(z=0,1,...,n)因?yàn)?即高一次的Bernstein基函數(shù)可由兩個(gè)低一次的Bernstein調(diào)和函數(shù)線性組合而成。因?yàn)?%⑴=%(1-尸=f(1T尸=(1 (1T)5TZ+CO"(1T)("-l)-g)(6)導(dǎo)函數(shù)耳〃S=N8t〃t⑺一"I。)］，i=0,1,…,明(7)最大值。Bin(r)在t七處達(dá)到最大值。(8)升階公式

巴川=百用皿⑴旦+旦+im+i。)⑼積分1%〃(')='Jo n+1Bezier曲線的性質(zhì)(1)端點(diǎn)性質(zhì)a)曲線端點(diǎn)位置矢量由Bernstein基函數(shù)的端點(diǎn)性質(zhì)可以推得，當(dāng)t=0時(shí)，P(O)=PO；當(dāng)t=l時(shí)，P(l)=Pn。由此可見，Bezier曲線的起點(diǎn)、終點(diǎn)與相應(yīng)的特征多邊形的起點(diǎn)、終點(diǎn)重合。b)切矢量因?yàn)?產(chǎn)(，)=〃2〉年山(，)一%-1(。］ 所以當(dāng)t=0時(shí)，P,(O)=n(Pl-PO),當(dāng)t=l時(shí)，P'(l)=n(Pn-Pn-l^這說(shuō)明Bezier曲線的起點(diǎn)和終點(diǎn)處的切線方向和特征多邊形的第…條邊及最后一條邊的走向一致。c.)二階導(dǎo)矢當(dāng)t=0時(shí)，當(dāng)t=l時(shí)，尸⑴=〃(〃-1)￡(匕+2—2九+c.)二階導(dǎo)矢當(dāng)t=0時(shí)，當(dāng)t=l時(shí)，P(0)=〃(〃—1)(8—2片+4)P(1)=〃(〃-1)(P“-2Rt+P“_2)上式表明：2階導(dǎo)矢只與相鄰的3個(gè)頂點(diǎn)有關(guān)，事實(shí)上，r階導(dǎo)矢只與(r+1)個(gè)相鄰點(diǎn)有關(guān),代入曲率公式"代入曲率公式"⑴「將尸(0)、P(0)及p⑴、尸⑴Bezier曲線在端點(diǎn)的曲率分別為：〃一］Z：(o)=—〃一］Z：(o)=—

n乂1)=〃一1|(匕一1一匕一2)X(4-匕T)|(2)對(duì)稱性。由控制頂點(diǎn)？=Ei，(i=0,1,.??,〃)，構(gòu)造出的新Bezier曲線，與原Bezier曲線形狀相同，走向相反。因?yàn)椋篊*⑴=力。*耳“⑴=￡%冏.")=汽。T紇/(17)=為。鳥.(1T), re［0,1］1=0 1=0 1=0 1=0這個(gè)性質(zhì)說(shuō)明Bezier曲線在起點(diǎn)處有什么幾何性質(zhì)，在終點(diǎn)處也有相同的性質(zhì)。(3)凸包性由于⑺=1,且04%?)<1(0</<覃=°，1，.一，〃)，這一結(jié)果說(shuō)明當(dāng)1在［0，1］區(qū)間變化時(shí)，對(duì)某一個(gè)t值，尸⑴是特征多邊形各頂點(diǎn)的加權(quán)平均，權(quán)因子依次是te[O,1J。在兒何圖形上，意味著Bezier曲線P⑴在。.⑺中各點(diǎn)是控制點(diǎn)p\的凸線性組合，即曲線落在Pi構(gòu)成的凸包之中。(4)幾何不變性。這是指某些幾何特性不隨坐標(biāo)變換而變化的特性。Bezier曲線位置與形狀與其特征多邊形頂點(diǎn)4(i=0,『??,〃) 的位置有關(guān)，它不依賴坐標(biāo)系的選擇。(5)變差縮減性。若Bezier曲線的特征多邊形P()P1--P是一個(gè)平面圖形，則平面內(nèi)任意直線與的交點(diǎn)個(gè)數(shù)不多于該直線與其特征多邊形的交點(diǎn)個(gè)數(shù)，這一性質(zhì)叫變差縮減性質(zhì)。此性質(zhì)反映了Bezier曲線比其特征多邊形的波動(dòng)還小，也就是說(shuō)Bezier曲線比特征多邊形的折線更光順(6)仿射不變性對(duì)于任意的仿射變換A：4[尸⑺]=4支 (。=ZA[P,也"⑺即在仿射變換下，的形式不變。Bezier曲線的遞推(deCasteljau)算法計(jì)算Bezier曲線上的點(diǎn)，可用Bezier曲線方程，但使用deCasteljau提出的遞推算法則要簡(jiǎn)單的多。如下圖所示，設(shè)不、石、鳥是一條拋物線上順序三個(gè)不同的點(diǎn)。過(guò)外和點(diǎn)的兩p切線交于片點(diǎn)，在后點(diǎn)的切線交和片22于々：和，則如下比例成立：*2 IPP1 PP1 P1P2r()r0_/_「0?0P1P P1P P2Plr0rl r\r2 r0r\ ]這是所謂拋物線的三切線定理。 ”=(17)尼+俏當(dāng)P0,P2固定，引入?yún)?shù)t,令上述比值為t:(l-t),即有：H=(1T)《+俏年=(1—陽(yáng)+引t從0變到1,第一、二式就分別表示控制二邊形的第一、二條邊，它們是兩條一次Bezier曲線。將一、二式代入第三式得：P：=(1-爐.+2?1-/)耳+產(chǎn)尸2當(dāng)t從0變到1時(shí)，它表示了由三頂點(diǎn)P0、Pl、P2三點(diǎn)定義的一條二次Bezier曲線。并且表明：這二次Bezier曲線P20可以定義為分別由前兩個(gè)頂點(diǎn)(P0,P1)和后兩個(gè)頂點(diǎn)(P1,P2)決定的一次Bezier曲線的線性組合。依次類推，由四個(gè)控制點(diǎn)定義的三次Bezier曲線P30可被定義為分別由(P0,Pl,P2)和(Pl,P2,P3)確定的二條二次Bezier曲線的線性組合，由(n+1)個(gè)控制點(diǎn)Pi(i=0,1,n)定義的n次Bezier曲線PnO可被定義為分別由前、后n個(gè)控制點(diǎn)定義的兩條(n-1)次Bezier曲線POn-1與Pln-1的線性組合：以=(1T)瑞，出尸 t€[01]由此得到Bezier曲線的遞推計(jì)算公式：片 k=0k=1,2,…,〃j=0,1,這便是著名的deCasteljau算法。用這一遞推公式，在給定參數(shù)下，求Bezier曲線上一點(diǎn)P(t)

非常有效。上式中：是定義Bezier曲線的控制點(diǎn)，以即為曲線尸⑴上具有參數(shù)t的點(diǎn)。deCasteljau算法穩(wěn)定可靠，直觀簡(jiǎn)便，可以編出十分簡(jiǎn)捷的程序，是計(jì)算Bezier曲線的基本算法和標(biāo)準(zhǔn)算法。當(dāng)n=3時(shí)，decasteljau算法遞推出的Pki呈直角三角形，對(duì)應(yīng)結(jié)果如圖3.1.11所示。從左向右遞推，最右邊點(diǎn)P30即為曲線上的點(diǎn)。圖3.1.11n=3時(shí)年的遞推關(guān)系這一算法可用簡(jiǎn)單的幾何作圖來(lái)實(shí)現(xiàn)。給定參數(shù)就把定義域分成長(zhǎng)度為的兩段。依次對(duì)原始控制多邊形每?邊琳闡炯群的定比分割，所得分點(diǎn)就是由第一級(jí)遞推生成的中間頂點(diǎn)p(i=O,l,?一，〃-1) ,對(duì)這些中間頂點(diǎn)構(gòu)成的控制多邊形再執(zhí)行同樣的定比分割，得第二級(jí)中間頂點(diǎn)^2(z=0,l,--,n-2)o重復(fù)進(jìn)行下去，直到n級(jí)遞推得到一個(gè)中間頂點(diǎn)即為所求曲赫上的點(diǎn)尸⑺，如圖3.1.12所示。0 1/3 1圖3.1.12幾何作圖法求Bezier曲線上一點(diǎn)(n=3,t=l/4)Bezier曲線的拼接兒何設(shè)計(jì)中，?條Bezier曲線往往難以描述復(fù)雜的曲線形狀。這是由于增加由于特征多邊形的頂點(diǎn)數(shù)，會(huì)引起B(yǎng)ezier曲線次數(shù)的提高，而高次多項(xiàng)式又會(huì)帶來(lái)計(jì)算上的困難，實(shí)際使用中，一般不超過(guò)10次。所以有時(shí)采用分段設(shè)計(jì)，然后將各段曲線相互連接起來(lái)，并在接合處保持一定的連續(xù)條件。下面討論兩段Bezier曲線達(dá)到不同階幾何連續(xù)的條件。給定兩條Bezier曲線P⑺和。⑺，相應(yīng)控制點(diǎn)為Pi(i=0,1，…,〃)和Qj(/=0,m),且令ai=Pi-Pi-\^j=Qj-Qj-\,如圖所示，我們現(xiàn)在把兩條曲線連接起來(lái)。

(1)要使它們達(dá)到GO連續(xù)的充要條件是：Pn=QO；(2)要使它們達(dá)到G/連續(xù)的充要條件是：Pn-1,Pn=Q,0三點(diǎn)共線，即：b1=aa“(a>0)(3)要使它們達(dá)到G2連續(xù)的充要條件是：在G1連續(xù)的條件下，并滿足方程Q(0)=。2/⑴+優(yōu)⑴o我們將。(0)、尸⑴和P⑴， 2=2、。|一。2=?勺一匕一1)代入，并整理,可以得到：Bezier曲線的升階與降階Bezier曲線的升階所謂升階是指保持Bezier曲線的形狀與定向不變，增加定義它的控制頂點(diǎn)數(shù)，也即是提高該Bezier曲線的次數(shù)。增加了控制頂點(diǎn)數(shù)，不僅能增加了對(duì)曲線進(jìn)行形狀控制的靈活性，還在構(gòu)造曲面方面有著重要的應(yīng)用。對(duì)于一些由曲線生成曲面的算法，要求那些曲線必須是同次的。應(yīng)用升階的方法，我們可以把低于最高次數(shù)的的曲線提升到最高次數(shù)，而獲得同一的次數(shù)。曲線升階后，原控制頂點(diǎn)會(huì)發(fā)生變化。下面，我們來(lái)計(jì)算曲線提升一階后的新的控制頂點(diǎn)。設(shè)給定原始控制頂點(diǎn)P0,Py,---,Pn )定義了一條n次Bezier曲線：尸⑺⑺te[0,1]z=o增加一個(gè)頂點(diǎn)后，仍定義同一條曲線的新控制頂點(diǎn)為外,匕*，…記2,則有:之C"(1T嚴(yán)=t以記7(1一嚴(yán)<=0 1=0對(duì)上式左邊乘以《+(lT)),得到：Xa“at)"+i+tMa)=X"a比較等式兩邊 項(xiàng)的系數(shù)，得到：=PC’+P,cj~}n+iin n-1n化簡(jiǎn)即得：P,其中21=匕+「=。此式說(shuō)明：其中21=匕+「=。此式說(shuō)明：?新的控制頂點(diǎn)是以參數(shù)值Q按分段線性插值從原始特征多邊形得出的。?升階后的新的特征多邊形在原始特征多邊形的凸包內(nèi)?特征多邊形更靠近曲線。三次Bezier曲線的升階實(shí)例如圖3.1.14所示。圖3.1.14Bezier曲線升階Bezier曲線的降階降階是升階的逆過(guò)程。給定一條由原始控制頂點(diǎn)C(i=O,l,…定義的n次Bezier曲線,要求找到一條由新控制頂點(diǎn)牙(i=O,l,…，〃-1)定義的n-1次Bezier曲線來(lái)逼近原始曲線。假定P,是由P；升階得到，則由升階公式有：匕=七"+」匕片*(，=0,1,.-,〃-1)nn從這個(gè)方程可以導(dǎo)出兩個(gè)遞推公式：和pn=nP,-iP；±n-i*叱一(〃一i)￡*i3.2.5Bezier曲面基于Bezier曲線的討論，我們可以方便地可以給出Bezier曲面的定義和性質(zhì)，Bezier曲線的一些算法也可以很容易擴(kuò)展到Bezier曲面的情況。.定義設(shè) 局(0,1,…,〃;j=0,1,…,m) 為(n+l)x(m+l)個(gè)空間點(diǎn)列，則mxn次張量積形式的Bezier曲面定義為：尸(",V)=ZX4gm(")鳥,"W) ",Ve[0,1]i=0j=0其中 %3)=C/(li尸，紇"")=。"/(1一?” 是Bernstein基函數(shù)。依次用線段連接點(diǎn)列中相鄰兩點(diǎn)所形成的空間網(wǎng)格，稱之為特征網(wǎng)格。Bezier曲面的矩陣表示式是：%)^01 'Bom?<0Al,%。)P"1.Pnm_在一般實(shí)際應(yīng)用中，n,m不大于4。.性質(zhì)除變差減小性質(zhì)外，Bezier曲線的其它性質(zhì)可推廣到Bezier曲面：(1)Bezier曲面特征網(wǎng)格的四個(gè)角點(diǎn)正好是Bezier曲面的四個(gè)角點(diǎn)，P(0,0)=& P(L0)=* ”0,1)=& P(1，D=&“

(2)Bezier曲面特征網(wǎng)格最外一圈頂點(diǎn)定義Bezier曲面的四條邊界；Bezier曲面邊界跨界切矢只與定義該邊界的頂點(diǎn)及相鄰一排頂點(diǎn)有關(guān)，匕』”.〃一IEl.” 和 匕0匕(圖3.1.15打上斜線的三角形)；其跨界二階導(dǎo)矢只與定義該邊界的及相鄰兩排頂點(diǎn)有關(guān)；…。(3)幾何不變性。(4)對(duì)稱性。(5)凸包性。P(O,v)P(O,1)=%Pd.D=(3)幾何不變性。(4)對(duì)稱性。(5)凸包性。P(O,v)P(O,1)=%Pd.D=p?PnP22'P(Lv)5/%%P(0,0)=%)P(〃,0)3.Bezier曲面片的拼接3.Bezier曲面片的拼接P(l,o)=&>圖3.1.15雙三次Bezier曲面及邊界信息如圖3.1.16所示，設(shè)兩張mXn次Bezier曲面片“I〃p(“，v)=ZZEH，.“(")％"日)Q(u,v)=ZZ。聲M(")%(v)?=Oj=0分別由控制頂點(diǎn)P”和Qu定義。為了構(gòu)造合成曲面時(shí)有更大的靈活性，Bezier在1972年放棄把(3.1.12)式作為G1連續(xù)的條件，而以_ . .._ .Qu(0,v)=a(y)Pu(l,v)+夕(v)R(1,v)(3」」3)來(lái)滿足(3.1.11)式，這僅僅要求Q“g)位于匕(1，丫)和4(Lv)所在的同一個(gè)平面內(nèi),也就是曲面片P(〃,v)邊界上相應(yīng)點(diǎn)處的切平面，這樣就有了大得多的余地，但跨界切矢在跨越曲面片的邊界時(shí)就不再連續(xù)了。同樣，為了保證等式兩邊關(guān)于v的多項(xiàng)式次數(shù)相同，a須為任意正常數(shù)， 是v的任意尸(V)線性函數(shù)。4.遞推(deCasteljau)算法Bezier曲線的遞推(deCasteljau)算法，可以推廣到Bezier曲面的情形。若給定Bezier曲面特和一對(duì)參數(shù)值(“#),貝IJ：征網(wǎng)格的控制頂點(diǎn)/>.(/=0,1,…,m;j和一對(duì)參數(shù)值(“#),貝IJ：m-k?一//=0y=0(3.1.14)其中P"町=11-其中P"町=11-〃)與1，0(1)成片+苗叫(1=0)(k=1,2,???,加；/=0)(k—m,l=1,2,???,〃)或fP" (女=/=0)管(1-丫)段"+叱得 (k=0;/=l,2,…(1一〃)限"+uP^(k=l,2,-,m;/=n)' ' (3.1.16)(3.1.15)與(3.1.16)中的下標(biāo)ij的變化范圍已在(3.1.14)式中給出。上面給出了確定曲面上一點(diǎn)的兩種方案。當(dāng)按(3.1.15)式方案執(zhí)行時(shí)，先以u(píng)參數(shù)值對(duì)控制網(wǎng)格u向的n+1個(gè)多邊形執(zhí)行曲線deCasteljau算法，m級(jí)遞推后，得到沿v向由n+1個(gè)頂點(diǎn)%=0,1,)構(gòu)成的中間多邊形。再以v參數(shù)值對(duì)它執(zhí)行曲線的deCasteljau算法，n級(jí)遞推以后，得到一個(gè)瑞”，即所求曲面上的點(diǎn)(u,v)也可以按(3.1.1