計算機圖形學教案(最終稿)

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

算dl=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量為a若d<0時，則取右上方象素P2(xp+l,yp+l)。要判斷再下一象素，則要計算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。可以用2d代替d來擺脫小數(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*/例：用中點畫線法 產(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算法? 基本思想過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列象素中與此交點最近的象素。設直線方程為： y,+i=Z+憶（七+1-七）=y+% ，其中k=dy/dxo因為直線的起始點在象素中心，所以誤差項d的初值d0=0?X下標每增加1,d的值相應遞增直線的斜率值k,即（1=（1+匕一旦d21,就把它減去1,

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

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

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

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

最簡單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點之后，再判斷各點是否在窗內(nèi)。但那樣太費時，一般不可取。這是因為有些圖形組成部分全部在窗口外，可以完全排除，不必進行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。直線段裁剪直線段裁剪算法是復雜圖元裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理分為三種情況處理：（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。（3）若線段不滿足“取”或“棄”的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷，采用如下編碼方法：每個區(qū)域賦予4位編碼C（C/CC[y>yma^othery<Vminotherother線段裁剪y>yma^othery<Vminotherother線段裁剪-若P1P2完全在窗口內(nèi)codel=0,且code2=0,則“取”-若P1P2明顯在窗口外codel&code2W0,貝『‘棄"-在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。-計算線段Pl(xl,yl)P2(x2,y2)與窗口邊界的交點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);}編碼的思想在圖形學中非常重要。Sutherland：Coons,圖靈，IEEE計算機先驅(qū)獎。中點分割裁剪算法基本思想：與前--種Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關(guān)系分為三種情況：全在、完全不在和線段和窗口有交。對前兩種情況，進行一樣的處理。對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距PO、P1最近的可見點，Pm為P0P1中點從出發(fā)找最近可見點的方法先求出幾巴的中點匕若尼匕不是顯然不可見的，并且玲匕在窗口中有可見部分，則距尸消最近的可見點一定落在凡上，所以用尼匕代替痣尸加；否則取匕6代替外巴再對新的尸治求中點匕。重復上述過程，直到？書長度小于給定的控制常數(shù)為止,此時P,?收斂于交點。從片出發(fā)找最近可見點采用上面類似方法。梁友棟一Barsky算法梁-Barsky算法的兒何含義：入邊、出邊與端點參數(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)。當Pkw。，?當Pk<0,線段從裁剪邊界延長線的外部延伸到內(nèi)部。?當Pk>0,線段從裁剪邊界延長線的內(nèi)部延伸到外部。對于每條直線，可以計算出參數(shù)ul和u2,它們定義了在裁剪矩形內(nèi)的線段部分ul的值由線段從外到內(nèi)遇到的矩形邊界所決定(p<0)o對這些邊界計算rk=qk/pkoul取0和各個rk值之中的最大值。u2的值由線段從內(nèi)到外遇到的矩形邊界所決定(p>0)o對這些邊界計算rk=qk/pk。u2取1和各個rk值之中的最小值。如果ul>u2,則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個值ul,u2計算出來。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;多邊形裁剪基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長線構(gòu)成的裁剪線該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種對于情況（1）僅輸出頂點P;情況（2）輸出。個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應隨之改變。其他窗口的裁剪圓域窗口裁剪：潛望鏡、…任意（凸）多邊形裁剪：個性化電腦顯示器定制，字符裁剪串精度:將包圍字串的外接矩形對窗口作裁剪字符精度:將包圍字的外接矩形對窗口作裁剪以及筆畫'象素精度:將筆劃分解成直線段對窗口作裁剪spring']""STRING2 STRING2RINGSTRING2S''RINGspring']""STRING2 STRING2RINGSTRING2S''RINGSTRING2待裁剪字符串串精度裁剪字符精度裁剪象素精度裁剪小結(jié)：光柵圖形學的一個基本問題是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，為了在顯示器等輸出設備上輸出字符，系統(tǒng)中必須有相應的字庫。計算機中的字符由數(shù)字編碼唯一標識。使用計算機處理圖形信息時，計算機內(nèi)部儲存的圖形往往比較大，而屏幕顯示的只是圖的一部分，因此需要剪裁。作業(yè)：.描述多邊形掃描轉(zhuǎn)換的掃描線算法，并寫出偽碼。.字符串裁剪可按哪3個精度進行？四.光柵圖形學(三)課型：理論講授課課時：3課時教學目標：1.使學生了解圖形走樣與如何反走樣。2.使學生了解圖形的消隱教學重點：圖形消隱教學難點：圖形消隱教學過程：2.6反走樣?用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing),用于減少或消除這種效果的技術(shù)稱為反走樣(antialiasing)提高分辨率把顯示器分辨率提高一倍，直線經(jīng)過兩倍的象素，鋸齒也增加一-倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。增加分辨率雖然簡單，但是不經(jīng)濟的方法，有物理上的困難而且它也只能減輕而不能消除鋸齒問題區(qū)域采樣基本思想：每個象素是一個具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長矩形。當直線段與象素有交時，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。有寬度的線條輪廓 象素相交的五種情況及用于計算面積的量面積計算情況⑴（5）陰影面積為：D2/2m；情況⑵（4）陰影面積為：D-m/2；TOC\o"1-5"\h\z情況⑶陰影面積為：l-D2/m /為了簡化計算可以采用離散的方法 //n=9,k=3近似面積為1/3 /首先將屏幕象素均分成n個子象素， /伍到目然后計算中心點落在直線段內(nèi)的子象素的個數(shù)k。 才?小I.將屏幕該象素的亮度置為相交區(qū)域面積的近似值可k/n。 /非加權(quán)區(qū)域采樣方法有兩個缺點：象素的亮度與相交區(qū)域的面積成正比，而與相交區(qū)域落在象素內(nèi)的位置無關(guān)，這仍然會導致鋸齒效應。直線條上沿理想直線方向的相鄰兩個象素有時會有較大的灰度差。加權(quán)區(qū)域取樣基本思想：使相交區(qū)域?qū)ο笏亓炼鹊呢暙I依賴于該區(qū)域與象素中心的距離，當直線經(jīng)過該象素時，該象素的亮度F是在兩者相交區(qū)域A，上對濾波器（函數(shù)w）進行積分的積分值?？刹捎秒x散計算方法4wl w2 卬3可采用離散計算方法4wl w2 卬3 1w4 vv5 w6 =— 216w7 卬8 w9 1?權(quán)函數(shù)w（x,y）為微面元dA與象素中心距離d的函數(shù)，縊國求出所有中心落于直線段內(nèi)的子象素，最后計算所有這些子象素對原象素亮度貢獻之和工嗎乘以象素的最大灰度值作為該象素的顯示灰度值。2.7消隱基本概念投影變換失去了深度信息，往往導致圖形的二義性，要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習慣上稱作消除隱藏線和隱藏面，簡稱為消隱。經(jīng)過消隱得到的投影圖稱為物體的真實圖形。長方體線框投影圖的二義性消隱的對象是三維物體。三維體的表示主要有邊界表示和CSG表示等。消隱結(jié)果與觀察物體有關(guān)，也與視點有關(guān)。

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

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

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

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

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

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

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

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

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

九")=(5〃1(17嚴-1、?典故日本的穗板：天上掉下來A為邊向量3.2.1Bezier曲線的定義和性質(zhì)定義給定空間n+1個點的位置矢量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)端點性質(zhì)(2)端點性質(zhì)fl%(o)=[o%(1)=];(i=0)otherwise(i=〃)

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

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

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

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

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

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