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

計(jì)算機(jī)圖形學(xué)東北大學(xué)聞時(shí)光計(jì)算機(jī)圖形學(xué)東北大學(xué)聞時(shí)光1課程簡介學(xué)習(xí)方法實(shí)驗(yàn)課小組項(xiàng)目聯(lián)系方式CGcourse@163.com83688326聞時(shí)光課程簡介學(xué)習(xí)方法2參考書目陳元琰《計(jì)算機(jī)圖形學(xué)實(shí)用技術(shù)》清華大學(xué)出版社2007.3孔令德《計(jì)算機(jī)圖形學(xué)實(shí)用教程》清華大學(xué)出版社2008.4PhilipJ.Schneider《計(jì)算機(jī)圖形學(xué)幾何工具算法詳解》電子工業(yè)出版社2005.1參考書目陳元琰《計(jì)算機(jī)圖形學(xué)實(shí)用技術(shù)》清華大學(xué)出版社203圖形圖形是傳遞信息最主要的媒體之一。人們使用圖形來表達(dá)與交流思想有著悠久的歷史，工程領(lǐng)域和各個(gè)科學(xué)分支都離不開圖。它能使人們通觀全局，一目了然。人的眼睛從一張圖紙中吸收信息比從一張數(shù)據(jù)表格吸收信息快得多。若圖形和數(shù)字互為補(bǔ)充，則可使人們更深刻地認(rèn)識事物的本質(zhì)及其內(nèi)在聯(lián)系。圖形圖形是傳遞信息最主要的媒體之一。4計(jì)算機(jī)圖形學(xué)定義是研究怎樣利用計(jì)算機(jī)表示、生成、處理和顯示圖形的原理、算法、方法和技術(shù)的一門學(xué)科。它與一般的科學(xué)計(jì)算不同。在一般的科學(xué)計(jì)算中，涉及的是數(shù)字運(yùn)算，在計(jì)算機(jī)圖形學(xué)中則是以基本的幾何元素為其運(yùn)算對象的。這些幾何元素描述物體的模擬圖示表示：符號、線圖、陰影區(qū)域和物體等。研究計(jì)算機(jī)圖形學(xué)的主要工具是圖形顯示系統(tǒng)和繪圖機(jī)、打印機(jī)等，乃至三維虛擬環(huán)境。計(jì)算機(jī)圖形學(xué)定義是研究怎樣利用計(jì)算機(jī)表示、生成、處理和顯示圖5計(jì)算機(jī)圖形學(xué)相關(guān)學(xué)科C.G.——對非圖形信息產(chǎn)生圖形I.P.——對圖象采用增強(qiáng)、變換等技術(shù)進(jìn)行處理增強(qiáng)(對比度)：對暴光過度或不足，以及 模糊的圖象進(jìn)行處理。變換：一幅亮度范圍寬的圖象—>兩種亮 度的圖象—>線條狀圖形P.R.——對圖象提取特征、予以分類 和描述關(guān)系，再進(jìn)行模式匹配計(jì)算機(jī)圖形學(xué)相關(guān)學(xué)科C.G.——對非圖形信息產(chǎn)生圖形I.P.6C.G.、I.P.和P.R.之間的區(qū)別描述圖像I.P.C.G.P.R.C.G.、I.P.和P.R.之間的區(qū)別描述圖像I.P.C7應(yīng)用領(lǐng)域1.管理、科學(xué)技術(shù)2.制圖學(xué)3.動畫4.計(jì)算機(jī)輔助設(shè)計(jì)CAD5.模擬6.藝術(shù)和教育7.辦公自動化應(yīng)用領(lǐng)域1.管理、科學(xué)技術(shù)8管理、科學(xué)技術(shù)繪制數(shù)學(xué)、物理以及經(jīng)濟(jì)函數(shù)的二維及三維圖形：直方圖、線條圖、扇形圖、進(jìn)程圖...特點(diǎn)：簡潔、直觀——>數(shù)據(jù)的模型和趨勢。管理、科學(xué)技術(shù)繪制數(shù)學(xué)、物理以及經(jīng)濟(jì)函數(shù)的二維及三維圖形：直9制圖學(xué)以高精度的地理或其他自然現(xiàn)象的圖形—>紙或膠片上。包括地圖、地質(zhì)圖、油層圖、海圖、氣象、人口密度圖...制圖學(xué)以高精度的地理或其他自然現(xiàn)象的圖形—>紙或膠片上10動畫用計(jì)算機(jī)可以產(chǎn)生逼真的動畫效果，可用于藝術(shù)創(chuàng)作，模擬真實(shí)的環(huán)境，或進(jìn)行飛機(jī)、駕駛等訓(xùn)練。動畫用計(jì)算機(jī)可以產(chǎn)生逼真的動畫效果，可用于藝術(shù)創(chuàng)作，模擬真11計(jì)算機(jī)輔助設(shè)計(jì)CAD設(shè)計(jì){元部件：機(jī)械、電氣、電子設(shè)備...系統(tǒng){結(jié)構(gòu)(建筑物、汽車車身、飛機(jī)和船的外殼及內(nèi)部結(jié)構(gòu))光學(xué)系統(tǒng)電話及計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)輔助設(shè)計(jì)CAD設(shè)計(jì){元部件：機(jī)械、電氣、電子設(shè)備..12汽車效果圖和線框圖汽車效果圖和線框圖13模擬數(shù)學(xué)圖形——科學(xué)現(xiàn)象的數(shù)學(xué)模型(液體流動、相對論、核反應(yīng)、化學(xué)反應(yīng)、生理系統(tǒng)與器官以及有負(fù)載時(shí)結(jié)構(gòu)的變形等)DNA皮膚結(jié)構(gòu)：真皮，上皮及附屬結(jié)構(gòu)模擬數(shù)學(xué)圖形——科學(xué)現(xiàn)象的數(shù)學(xué)模型(液體流動、相對論、核14模擬云霧、煙、其他大小形狀不同的飛機(jī)等特殊景物飛行模擬器：固定環(huán)境的景色可用在月球登陸的宇航員(練習(xí)登月）、宇宙飛船駕駛員(首航前訓(xùn)練)模擬云霧、煙、其他大小形狀不同的飛機(jī)等特殊景物15過程控制利用交互式圖形生成技術(shù)形成的人機(jī)交互系統(tǒng)，實(shí)現(xiàn)人與控制或管理對象之間的相互作用。如工廠中的設(shè)備、工序控制，機(jī)場與鐵路的調(diào)度等。過程控制利用交互式圖形生成技術(shù)形成的人機(jī)交互系統(tǒng)，實(shí)現(xiàn)人與控16藝術(shù)和教育：教學(xué)活動蟬（線框圖）藝術(shù)和教育：教學(xué)活動蟬（線框圖）17藝術(shù)和教育藝術(shù)廣告藝術(shù)繪畫藝術(shù)和教育藝術(shù)廣告18辦公自動化在辦公室中，用圖形方式顯示并交換文件、報(bào)表、圖例和其它信息，并在輸出設(shè)備上輸出、保存起來。辦公自動化在辦公室中，用圖形方式顯示并交換文件、報(bào)表、圖例和19圖形學(xué)發(fā)展歷史50s1950年，第一臺圖形顯示器作為美國麻省理工學(xué)院（MIT）旋風(fēng)I號（WhirlwindI）計(jì)算機(jī)的附件誕生了。該顯示器用一個(gè)類似于示波器的陰極射線管（CRT）來顯示一些簡單的圖形。1958年美國Calcomp公司由聯(lián)機(jī)的數(shù)字記錄儀發(fā)展成滾筒式繪圖儀，GerBer公司把數(shù)控機(jī)床發(fā)展成為平板式繪圖儀。圖形學(xué)發(fā)展歷史50s1950年，第一臺圖形顯示器作為美國麻省20圖形學(xué)發(fā)展歷史60s1962年，MIT林肯實(shí)驗(yàn)室的IvanE.Sutherland發(fā)表了一篇題為“Sketchpad：一個(gè)人機(jī)交互通信的圖形系統(tǒng)”的博士論文，首次使用“ComputerGraphics”這個(gè)術(shù)語，證明了交互計(jì)算機(jī)圖形學(xué)是一個(gè)可行的、有用的研究領(lǐng)域1964年MIT的教授StevenA.Coons提出了被后人稱為超限插值的新思想，通過插值四條任意的邊界曲線來構(gòu)造曲面。同在60年代早期，法國雷諾汽車公司的工程師PierreBézier發(fā)展了一套Bézier曲線、曲面的理論，成功地用于幾何外形設(shè)計(jì)。Coons方法和Bézier方法是CAGD最早的開創(chuàng)性工作。圖形學(xué)發(fā)展歷史60s1962年，MIT林肯實(shí)驗(yàn)室的Ivan21圖形學(xué)發(fā)展歷史70s70年代是計(jì)算機(jī)圖形學(xué)發(fā)展過程中一個(gè)重要的歷史時(shí)期。光柵顯示器的產(chǎn)生，圖形學(xué)進(jìn)入了第一個(gè)興盛的時(shí)期，并開始出現(xiàn)實(shí)用的CAD圖形系統(tǒng)1977、1979年開始，計(jì)算機(jī)圖形學(xué)標(biāo)準(zhǔn)制定，真實(shí)感圖形學(xué)和實(shí)體造型技術(shù)的產(chǎn)生。1970年Bouknight提出了第一個(gè)光反射模型，1971年Gourand提出“漫反射模型＋插值”的思想，被稱為Gourand明暗處理。r1975年P(guān)hong提出了著名的簡單光照模型—Phong模型。這些可以算是真實(shí)感圖形學(xué)最早的開創(chuàng)性工作。從1973年開始，相繼出現(xiàn)了英國劍橋大學(xué)CAD小組的Build系統(tǒng)、美國羅徹斯特大學(xué)的PADL-1系統(tǒng)等實(shí)體造型系統(tǒng)。圖形學(xué)發(fā)展歷史70s70年代是計(jì)算機(jī)圖形學(xué)發(fā)展過程中一個(gè)重要22圖形學(xué)發(fā)展歷史80s1980年Whitted提出了一個(gè)光透視模型—Whitted模型，并第一次給出光線跟蹤算法的范例，實(shí)現(xiàn)Whitted模型。1984年，美國Cornell大學(xué)和日本廣島大學(xué)的學(xué)者分別將熱輻射工程中的輻射度方法引入到計(jì)算機(jī)圖形學(xué)中，用輻射度方法成功地模擬了理想漫反射表面間的多重漫反射效果。1986年，美國科學(xué)基金會（NSF）專門召開了一次研討會，會上提出了“科學(xué)計(jì)算可視化（VisualizationinScientificComputing，簡稱為ViSC）”。圖形學(xué)發(fā)展歷史80s1980年Whitted提出了一個(gè)光透視23SIGGRAPHSIGGRAPH會議，“TheSpecialInterestGrouponComputerGraphicsandInteractiveTechniques”ACMSIGGRAPH會議是計(jì)算機(jī)圖形學(xué)最權(quán)威的國際會議，每年在美國召開，參加會議的人在50,000人左右。世界上沒有第二個(gè)領(lǐng)域每年召開如此規(guī)模巨大的專業(yè)會議，SIGGRAPH會議很大程度上促進(jìn)了圖形學(xué)的發(fā)展。

1974年在Colorado大學(xué)召開了第一屆SIGGRAPH年會。因?yàn)槊磕曛讳浫〈蠹s50篇論文，在ComputerGraphics雜志上發(fā)表，因此論文的學(xué)術(shù)水平較高，基本上代表了圖形學(xué)的主流方向。SIGGRAPHSIGGRAPH會議，“TheSpec24虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)技術(shù)就是利用計(jì)算機(jī)生成一個(gè)逼真的三維虛擬環(huán)境，通過自然技能使用傳感設(shè)備與之相互作用的新技術(shù)。它與傳統(tǒng)的模擬技術(shù)完全不同，是將模擬環(huán)境、視景系統(tǒng)和仿真系統(tǒng)合三為一，利用頭盔顯示器、圖形眼鏡、數(shù)據(jù)服、立體聲耳機(jī)、數(shù)據(jù)手套及腳踏板等傳感裝置，把操作者與計(jì)算機(jī)生成的三維虛擬環(huán)境連結(jié)在一起。與傳統(tǒng)計(jì)算機(jī)相比，虛擬現(xiàn)實(shí)系統(tǒng)具有三個(gè)重要特征：臨境性、交互性、想象性。虛擬現(xiàn)實(shí)建模語言VRML是描述虛擬環(huán)境中場景的一種標(biāo)準(zhǔn)，可以利用它在INTERNET建立交互式的三維多媒體環(huán)境。VRML的基本特征包括分布式、交互式、平臺無關(guān)、三維、多媒體集成和逼真自然等，國際標(biāo)準(zhǔn)化組織1998年1月正式將其批準(zhǔn)為國際標(biāo)準(zhǔn)。虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)技術(shù)就是利用計(jì)算機(jī)生成一個(gè)逼真的三維虛擬環(huán)境25計(jì)算機(jī)藝術(shù)可用于美術(shù)創(chuàng)作的軟件很多，如二維平面的畫筆程序(如CorelDraw，Photoshop，PaintShop)、專門的圖表繪制軟件(如Visio)、三維建模和渲染軟件包(如3DMAX，Maya)、以及一些專門生成動畫的軟件(如Alias，SoftImage)等。這些軟件不僅提供多種風(fēng)格的畫筆、畫刷，而且提供多種多樣的紋理貼圖，甚至能對圖像進(jìn)行霧化/變形等操作。很多功能是一個(gè)傳統(tǒng)的藝術(shù)家無法實(shí)現(xiàn)也不可想象的。當(dāng)然，傳統(tǒng)藝術(shù)的一些效果也是上述軟件所不能達(dá)到的。例如鋼筆素描的效果，由于鋼筆素描與傳統(tǒng)的圖形學(xué)繪制方法差別很大，所以研究起來難度也頗大，很多學(xué)者已在這方面做了卓有成效的工作，取得了一定的成果。計(jì)算機(jī)藝術(shù)可用于美術(shù)創(chuàng)作的軟件很多，如二維平面的畫筆程序(如26圖形用戶接口用戶接口是人們使用計(jì)算機(jī)的第一觀感。一個(gè)友好的圖形化的用戶界面能夠大大提高軟件的易用性，在DOS時(shí)代，計(jì)算機(jī)的易用性很差，編寫一個(gè)圖形化的界面要費(fèi)去大量的勞動，過去軟件中有60％的程序是用來處理與用戶接口有關(guān)的問題和功能的。進(jìn)入80年代后，隨著Xwindow標(biāo)準(zhǔn)的面世，蘋果公司圖形化操作系統(tǒng)的推出，特別是微軟公司W(wǎng)indows操作系統(tǒng)的普及，標(biāo)志著圖形學(xué)已經(jīng)全面融入計(jì)算機(jī)的方方面面。目前幾個(gè)大的軟件公司都在研究下一代用戶界面，開發(fā)面向主流應(yīng)用的自然、高效多通道的用戶界面。研究多通道語義模型、多通道整合算法及其軟件結(jié)構(gòu)和界面范式是當(dāng)前用戶界面和接口方面研究的主流方向，而圖形學(xué)在其中起主導(dǎo)作用。圖形用戶接口用戶接口是人們使用計(jì)算機(jī)的第一觀感。一個(gè)友好的圖27計(jì)算機(jī)圖形學(xué)研究的基本問題圖形描述基本幾何：直線、圓弧等；高級幾何：曲線、曲面等圖形變換二、三維變換、三維到二維、觀察流程、幾何變換等圖形運(yùn)算基本幾何間的計(jì)算、裁剪、布爾運(yùn)算等圖形顯示/輸出基本圖形生成算法、消隱、繪圖、光照模型等圖形輸入交互技術(shù)、參數(shù)化設(shè)計(jì)、造型技術(shù)等算法和算法復(fù)雜性分析空間和時(shí)間等計(jì)算機(jī)圖形學(xué)研究的基本問題圖形描述28兩個(gè)核心問題如何建模交互技術(shù)曲線造型如何繪制光柵圖形學(xué)光照模型裁剪計(jì)算顏色模型兩個(gè)核心問題如何建模29圖形描述一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)所懂得，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在顯示屏幕或繪圖機(jī)上輸出；而圖形是模型的一個(gè)具體可見像，是人們所看到的模型的表征。在三維空間，描述的是幾何形體和幾何曲面，只有在平面上，它才是人們通常所稱的圖形。圖形描述一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)所懂得，并30圖形描述幾何形體以封閉的表面表示，一般為一個(gè)由平面和曲面圍成的多面體。一個(gè)幾何形體在空間上應(yīng)是完備的(幾何性和拓?fù)湫?，而且包含足夠的用于推導(dǎo)的任何空間函數(shù)(如直線方程、平面方程、曲面構(gòu)造等)以及進(jìn)行各種形體運(yùn)算與處理的信息。圖形描述幾何形體以封閉的表面表示，一般為一個(gè)由平面和曲面圍成31圖形描述在多面體表示中，有關(guān)的基本元素（體、面、環(huán)、棱和頂點(diǎn)）的信息分為二大類：幾何信息：用以確定每個(gè)分量在歐氏空間中的幾何位置(如點(diǎn)坐標(biāo))和描述(如平面方程系數(shù))；拓?fù)湫畔ⅲ河脕矶x幾何元素的數(shù)目及相互間的連接關(guān)系。幾何信息只考慮點(diǎn)、線和無限面。拓?fù)湫畔Ⅻc(diǎn)看作頂點(diǎn)，將線限制為棱(線段)，由外環(huán)和內(nèi)環(huán)定義出面和內(nèi)孔。一個(gè)完全的三維幾何體描述，幾何信息和拓?fù)湫畔烧叨际潜匾膱D形描述在多面體表示中，有關(guān)的基本元素（體、面、環(huán)、棱和頂點(diǎn)32圖形描述描述一個(gè)多面體各元素之間的拓?fù)潢P(guān)系可以互相推導(dǎo)。故理論上只需存儲一種關(guān)系就行了，但由于關(guān)系的推導(dǎo)要付出代價(jià)，所以一般的系統(tǒng)常同時(shí)存儲若于種拓?fù)潢P(guān)系。這些拓?fù)潢P(guān)系，既要足夠地表示出幾何形體的構(gòu)造，又要盡量壓縮信息的存儲量，且要便于檢索和修改，而十分重要的是要便于計(jì)算機(jī)的自動生成。圖形描述描述一個(gè)多面體各元素之間的拓?fù)潢P(guān)系可以互相推導(dǎo)。故理33圖形描述對于曲表面的幾何形體，需分別研究自由曲線和自由曲面的建立；用于插值和數(shù)學(xué)放樣的三次樣條函數(shù)是應(yīng)用得最早研究得最詳盡的一種。Bezier曲線和曲面與B樣條曲線和曲面是在計(jì)算機(jī)輔助幾何設(shè)計(jì)應(yīng)用最廣的曲線和曲面幾何構(gòu)型方法。關(guān)于這些方面的研究，至今仍在繼續(xù)發(fā)展中。圖形描述對于曲表面的幾何形體，需分別研究自由曲線和自由曲面的34圖形描述平面上圖形的描述是基于直線和圓弧的描述。僅用這兩種基本幾何元素就可構(gòu)成平面上的任何圖形。因而直線段和圓弧段也叫基本幾何段，本課程將詳加闡述。數(shù)據(jù)結(jié)構(gòu)技術(shù)在圖形描述中起著關(guān)鍵的作用。線性鏈接表、樹結(jié)構(gòu)、堆棧、隊(duì)列等將廣泛應(yīng)用于幾何模型的描述、運(yùn)算和顯示中。圖形描述平面上圖形的描述是基于直線和圓弧的描述。僅用這兩種基35圖形輸入圖形輸入需要解決的問題是：交互輸入的方法。工程設(shè)計(jì)圖紙直接輸入（矢量識別）的方法。將自由手書的立體構(gòu)造或三視圖重構(gòu)的方法。計(jì)算機(jī)自動生成方法。從物體的多幅深度圖像重建三維幾何模型。通過三維激光掃描儀在物體表面測得一些離散點(diǎn)，再用重構(gòu)算法生成網(wǎng)格模型等等。圖形輸入圖形輸入需要解決的問題是：36圖形輸入圖形輸入的常規(guī)方法是將事先寫好的源程序(指令)在屏幕上輸入，即所謂的編程輸入，使得人、機(jī)之間的交互作用緩慢。對于工程上常用的一類規(guī)格化圖形，可以編制一個(gè)通用程序，采用格式數(shù)據(jù)輸入的辦法得到圖形。但是在處理三維的，或是形狀復(fù)雜的物體時(shí)還有較多的困難，輸入數(shù)據(jù)太多就是一個(gè)障礙。圖形輸入圖形輸入的常規(guī)方法是將事先寫好的源程序(指令)在屏幕37圖形輸入除了這種圖形的直接輸入之外，通過對基本體元的構(gòu)型產(chǎn)生新的、復(fù)雜的三維物體也是一種輸入的手段，當(dāng)然這需要涉及更多的研究。從計(jì)算機(jī)圖形學(xué)的發(fā)展情況看，對圖形輸出的研究多于對圖形輸入的研究，許多人往往被計(jì)算機(jī)輸出的美妙圖形所迷惑，卻看不到為得到這些圖形所做的大量數(shù)據(jù)輸入的準(zhǔn)備工作。圖形輸入的工作量和難度并不亞于幾何算法和圖形輸出。隨著時(shí)間的推移，圖形輸入將越來越成為計(jì)算圖形學(xué)應(yīng)用中的主要障礙。圖形輸入除了這種圖形的直接輸入之外，通過對基本體元的構(gòu)型產(chǎn)生38圖形變換一個(gè)圖形系統(tǒng)需具有圖形變換的功能。這種變換包括二維變換、三維變換和三維向二維的變換三種。對應(yīng)于幾何元素及其選定的坐標(biāo)系來說，則包括幾何變換和坐標(biāo)系變換兩種。這些變換系統(tǒng)稱為圖形變換。在構(gòu)造、產(chǎn)生、處理和輸出圖形的各個(gè)環(huán)節(jié)，圖形變換起著重要的作用。圖形變換一個(gè)圖形系統(tǒng)需具有圖形變換的功能。這種變換包括二維變39圖形變換人們可以直接定義一個(gè)幾何圖形或幾何體，也可通過對某些幾何體的變換去構(gòu)造新的幾何體或其中的某個(gè)部份。這種變換可以是平移、放大(縮小)、旋轉(zhuǎn)、反射、錯(cuò)切等。一個(gè)三維場景通常就是由一些基本幾何元素通過上述操作構(gòu)造的。例如，可以通過平移的辦法裝配一幢建筑物的大部份窗子，這使得圖形輸入大為簡化。在進(jìn)行圖形處理的過程中，還可以放大一個(gè)圖形以便使其某一部份能更清楚地顯示；縮小圖形以便看到圖形更多的部份。圖形變換人們可以直接定義一個(gè)幾何圖形或幾何體，也可通過對某些40圖形變換在顯示或繪制一個(gè)環(huán)境的時(shí)候，需要將三維信息映射到二維屏幕上。軸測投影、平行投影和透視投影用于完成這項(xiàng)工作。在視點(diǎn)改變得非常快或物體相對運(yùn)動的應(yīng)用場合，變換必須反復(fù)運(yùn)用。因此，找到一個(gè)有效的方法去實(shí)現(xiàn)圖形變換是十分重要的。圖形變換在顯示或繪制一個(gè)環(huán)境的時(shí)候，需要將三維信息映射到二維41圖形變換采用向量、矩陣和齊次坐標(biāo)的形式去描述圖形變換是一種比較好的辦法，它允許將線性代數(shù)的一些基本理論應(yīng)用到圖形變換中。例如一個(gè)矩陣對應(yīng)于一個(gè)變換，圖形的連續(xù)變換可由矩陣的相乘實(shí)現(xiàn)，而逆矩陣對應(yīng)于一個(gè)逆變換。所有的變換都基于點(diǎn)變換，例如對一條線段的變換只需考慮其兩個(gè)端點(diǎn)的變換就可以了?；編缀卧孛枋龅淖儞Q也和點(diǎn)的變換有密切的聯(lián)系。例如描述一條直線的方程系數(shù)在不同坐標(biāo)下的關(guān)系也可由點(diǎn)變換的相應(yīng)變換矩陣求得。圖形變換采用向量、矩陣和齊次坐標(biāo)的形式去描述圖形變換是一種比42圖形運(yùn)算在三維空間，圖形的運(yùn)算是一種幾何形體的運(yùn)算，它是CAGD的一個(gè)重要操作，這種操作通常叫做物體造型，或幾何造型。設(shè)計(jì)人員可通過修改立方體，圓柱體之類的基本體元來生成形體。例如通過縮放，通過用集合論中的并、交、非、差等概念所進(jìn)行的各種布爾運(yùn)算把一些基本物體體元組合起來。設(shè)計(jì)人員的職責(zé)是把各體元正確地定位下來，使得這些運(yùn)算能進(jìn)行下去。另一方面幾何造型系統(tǒng)還負(fù)責(zé)估計(jì)各體元之間的相互作用，各種相交出現(xiàn)的位置以及它們之間的相互關(guān)系，以確保生成法定的三維形體。系統(tǒng)還必須正確地、在計(jì)算機(jī)限制下內(nèi)盡可能精確地完成相交分析。圖形運(yùn)算在三維空間，圖形的運(yùn)算是一種幾何形體的運(yùn)算，它是CA43圖形運(yùn)算幾何造型系統(tǒng)常處理一些比較簡單的體元：立方體、圓柱體、楔、嵌條，以直線或圓弧為邊界的薄片等。所涉及的線和面在幾何上是簡單的直線、圓弧、平面和圓柱面，處理這些由一個(gè)正確的方式構(gòu)造出來的物體的相交，從概念上是比較容易的。但主要困難在于：雖然幾何簡單，但多個(gè)元素的拼合卻是復(fù)雜的。故對于確實(shí)復(fù)雜的形體的組合問題，所需的幾何算法的效率就變得十分重要，需進(jìn)行幾何復(fù)雜性分析。圖形運(yùn)算幾何造型系統(tǒng)常處理一些比較簡單的體元：立方體、圓柱體44圖形運(yùn)算幾何造型系統(tǒng)較之早期圖形系統(tǒng)的顯著優(yōu)越之處在于：無需人為干預(yù)就能預(yù)定形體與執(zhí)行一連串運(yùn)算。即具有高度自動化的圖形定義或構(gòu)造、產(chǎn)生處理或演變功能。幾何元素的定向在圖形運(yùn)算中起著相當(dāng)大的作用。例如平面圖形的幾何運(yùn)算就是建立在以向量為基本幾何元素的環(huán)的基礎(chǔ)上實(shí)現(xiàn)的。直線和圓弧這兩種基本幾何段的相貫運(yùn)算是平面圖形運(yùn)算的基礎(chǔ)，保證這些算法的準(zhǔn)確性，提高這些算法的效率是計(jì)算機(jī)圖形系統(tǒng)一項(xiàng)基礎(chǔ)性的工作。圖形運(yùn)算幾何造型系統(tǒng)較之早期圖形系統(tǒng)的顯著優(yōu)越之處在于：無需45圖形輸出圖形輸出是人—機(jī)交互系統(tǒng)中人們能夠得到的最直觀的結(jié)果。它直接向人們顯示出計(jì)算機(jī)圖形系統(tǒng)的效果。相對而言，圖形輸出計(jì)算機(jī)圖學(xué)中研究得最早、最深入、解決得最好的一部份工作。圖形輸出圖形輸出是人—機(jī)交互系統(tǒng)中人們能夠得到的最直觀的結(jié)46圖形輸出一個(gè)物體的制造者可以從一張多視圖的圖樣里了解到許多內(nèi)容。因此，一個(gè)能在二維參考平面里提供綜合的，繪制直線和曲線的系統(tǒng)也就提供了畫出一個(gè)復(fù)雜而詳細(xì)的圖形或物體的基礎(chǔ)。但是，圖形只是三維物體的某一個(gè)特定的不完整的表示。而物體有一種圖里沒有的，與眾不同的特性——完全的三維定義。人們可以隨意地在三維空間中把物體旋轉(zhuǎn)和平移以及物體的綜合，但一般不能用圖形做到這一點(diǎn)。圖形輸出一個(gè)物體的制造者可以從一張多視圖的圖樣里了解到許多內(nèi)47圖形輸出基本幾何（點(diǎn)、直線、圓及圓弧等）和文字的光柵化顯示，幾何裁剪算法基本幾何的描述、相交算法，曲線擬合和雙圓弧逼近算法，動態(tài)顯示的插值算法。圖形顯示中的裁剪算法，通常稱為窗口算法；隱藏線、隱藏面消除算法。光照模型及算法。紋理貼圖；大規(guī)模場景顯示算法；圖形顯示軟件和打印機(jī)、繪圖機(jī)等的圖形輸出后處理軟件等等。圖形輸出基本幾何（點(diǎn)、直線、圓及圓弧等）和文字的光柵化顯示，48幾何算法、幾何復(fù)雜性和計(jì)算效率一個(gè)動畫程序，一個(gè)游戲程序，用戶的起碼要求是“流暢”；支撐它的是幾何算法，幾何復(fù)雜性問題及計(jì)算的效率。許多通過交互設(shè)計(jì)各種形體的系統(tǒng)，其成功的主要斷依據(jù)是憑視覺。例如套料問題，這在造船、服裝等行業(yè)是極為有用的，然而至今存在的系統(tǒng)還是由人機(jī)交互作用來完成。而幾何造型系統(tǒng)在相交問題的正確算法和處理組合比較復(fù)雜問題的能力，這種系統(tǒng)的發(fā)展表明，需要多多研究幾何算法。幾何算法、幾何復(fù)雜性和計(jì)算效率一個(gè)動畫程序，一個(gè)游戲程序，用49幾何算法、幾何復(fù)雜性和計(jì)算效率幾何相交問題在幾何算法中占有較大的比重，在平面上，它處理直線和直線，圓弧和直線，圓弧和圓弧等基本幾何的相交，在三維空間則是處理直線和平面，平面和平面的相互關(guān)系。但是，并不是所有的處理直線和直線的相交都是簡易的。例如，考慮兩個(gè)平面多邊形相交的狀態(tài)，按照Shamos(1978)算法，如果這兩個(gè)多邊形是凸的，對于n條邊的多邊形可以用O(n)的時(shí)間解決這個(gè)問題。而對于兩個(gè)任意非凸多邊形，為解決這個(gè)問題要花O(n2)的時(shí)間，可能形成達(dá)n2/4個(gè)不相疊的凸多邊形。幾何算法、幾何復(fù)雜性和計(jì)算效率幾何相交問題在幾何算法中占有較50幾何算法、幾何復(fù)雜性和計(jì)算效率觀察一個(gè)時(shí)間復(fù)雜性的例子：問題：設(shè)給定n個(gè)已經(jīng)排序的數(shù)的隊(duì)列，現(xiàn)在要插入一個(gè)新的數(shù)到這個(gè)隊(duì)列中，并保持隊(duì)列原有的次序，幾何復(fù)雜性為O(n)次主算。應(yīng)用二分法，可降為O(log2n)次。如果不計(jì)檢索到元素后對其處理所花費(fèi)的計(jì)算時(shí)間，而只對n的步數(shù)計(jì)算時(shí)間，那末當(dāng)n=60時(shí)：n：6×10-5秒N^2：36×10-4秒N^3：216×10-3秒N^5：13分鐘2^n：366世紀(jì)3^n：1.3×1013世紀(jì)幾何算法、幾何復(fù)雜性和計(jì)算效率觀察一個(gè)時(shí)間復(fù)雜性的例子：51幾何算法、幾何復(fù)雜性和計(jì)算效率降低幾何復(fù)雜性是幾何算法的一個(gè)努力目標(biāo)，它可以提高算法的效率。過去開發(fā)僅僅能“工作”的算法就常常足夠了，即使在某些情況下效率低也無妨。隨著使用計(jì)算機(jī)進(jìn)行幾何設(shè)計(jì)的增加，以及要解決問題的范圍之?dāng)U大，效率、精度和正確性的問題就變得非常重要了。幾何算法、幾何復(fù)雜性和計(jì)算效率降低幾何復(fù)雜性是幾何算法的一個(gè)52計(jì)算機(jī)圖形學(xué)的相關(guān)開發(fā)技術(shù)計(jì)算機(jī)圖形學(xué)經(jīng)過幾十年的發(fā)展，已經(jīng)達(dá)到了比較高的水平，目前已有若干圖形學(xué)軟件開發(fā)技術(shù)。利用這些開發(fā)技術(shù)，編寫圖形程序就容易多了，不必從底層開始，而只需將精力集中到圖形程序本身上。計(jì)算機(jī)圖形學(xué)的相關(guān)開發(fā)技術(shù)計(jì)算機(jī)圖形學(xué)經(jīng)過幾十年的發(fā)展，已經(jīng)53OpenGLOpenGL：OpenGL是OpenGraphicsLib的縮寫，是一套三維圖形處理庫，也是該領(lǐng)域的工業(yè)標(biāo)準(zhǔn)。OpenGL源于SGI公司為其圖形工作站開發(fā)的IRISGL，在跨平臺移植過程中發(fā)展成為OpenGL。OpenGL被設(shè)計(jì)成獨(dú)立于硬件，獨(dú)立于窗口系統(tǒng)的，在運(yùn)行各種操作系統(tǒng)的各種計(jì)算機(jī)上都可用，并能在網(wǎng)絡(luò)環(huán)境下以客戶/服務(wù)器模式工作，是專業(yè)圖形處理、科學(xué)計(jì)算等高端應(yīng)用領(lǐng)域的標(biāo)準(zhǔn)圖形庫。OpenGLOpenGL：OpenGL是OpenGraph54OpenGLMicrosoft、SGI、IBM、DEC、SUN、HP等大公司都采用了OpenGL作為三維圖形標(biāo)準(zhǔn)。許多軟件廠商也紛紛以O(shè)penGL為基礎(chǔ)開發(fā)出自己的產(chǎn)品，包括動畫制作軟件SoftImage和3DStudioMAX、仿真軟件OpenInventor、VR軟件WorldToolKit、CAD軟件Pro/Engineer、GIS軟件ARC/INFO等等。OpenGL實(shí)際上是一個(gè)開放的三維圖形軟件包，它獨(dú)立于窗口系統(tǒng)和操作系統(tǒng)，以它為基礎(chǔ)開發(fā)的應(yīng)用程序可以十分方便地在各種平臺間移植；OpenGL與C++緊密接合，便于實(shí)現(xiàn)圖形的相關(guān)算法，并可保證算法的正確性和可靠性；OpenGL使用簡便，效率高。OpenGLMicrosoft、SGI、IBM、DEC、SU55ACISACIS是美國SpatialTechnology公司推出的三維幾何引擎，為各種3D造型應(yīng)用的開發(fā)提供了幾何造型平臺，目前的最高本版已經(jīng)到了R13。ACIS能夠安裝在多種平臺上，包括Windows,Linux,Unix,Solaris,AIX等。ACIS采用了軟件組件技術(shù)，用C++技術(shù)構(gòu)造，它包含一整套的C++類和函數(shù)，開發(fā)人員可以使用這些類和函數(shù)構(gòu)造一個(gè)面向終端用戶的2/3維軟件系統(tǒng)。ACIS是一個(gè)基于邊界表示法的造型引擎，集線框、曲面和實(shí)體造型于一體，并允許這三種表示共存于統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)中。ACISACIS是美國SpatialTechnology公56ACISACIS系統(tǒng)的造型方法有：覆蓋技術(shù)(covering)：覆蓋一個(gè)由曲線組成的閉合區(qū)域的曲面放樣技術(shù)(lofting)：通過一系列的曲線和與這些曲線相關(guān)聯(lián)的曲面來構(gòu)造新曲面的一種技術(shù)蒙面技術(shù)(skinning)：在一系列曲線之間構(gòu)造一個(gè)曲面ACISACIS系統(tǒng)的造型方法有：57ACIS網(wǎng)格曲面(netsurfaces)：用一族曲線網(wǎng)來定義曲面的u和v參數(shù)方向，這為控制最終的曲面形狀提供了很大的自由度規(guī)則(law)和圖(graph)：提供規(guī)則類，直接用數(shù)學(xué)方程定義實(shí)體中的邊和面掃掠(sweeping)：通過掃描一個(gè)輪廓(profile)來生成實(shí)體（solidbody）或者薄片體(sheetbody)。ACIS有三種不同的掃掠操作：規(guī)則掃掠、垂直掃掠以及剛性掃掠ACIS網(wǎng)格曲面(netsurfaces)：用一族曲線網(wǎng)來58DirectXDirectX是一種圖形應(yīng)用程序接口（API），它是一個(gè)提高系統(tǒng)性能的加速軟件，由微軟公司創(chuàng)建開發(fā)，微軟將其定義為“硬件設(shè)備無關(guān)性”。DirectX就是一系列的DLL(DynamicLinkLib)，通過這些DLL，程序員可以在無視于設(shè)備差異的情況下訪問底層的硬件。DirectX并不是一個(gè)單純的圖形API，它是一個(gè)用途廣泛的API，它包含有DirectGraphics(Direct3D+DirectDraw)、DirectInput、DirectPlay、DirectSound、DirectShow、DirectSetup和DirectMediaObjects等多個(gè)組件，它提供了一整套的多媒體接口方案。DirectXDirectX是一種圖形應(yīng)用程序接口（API）59DirectXDirectX主要應(yīng)用于游戲軟件的開發(fā)。微軟公司給眾多的軟、硬件商家提供一個(gè)共同開發(fā)的標(biāo)準(zhǔn)平臺(就是DirectX)，大家都遵循這個(gè)標(biāo)準(zhǔn)，硬件制造商按照此標(biāo)準(zhǔn)研發(fā)制造更好的產(chǎn)品，游戲程序員根據(jù)這套標(biāo)準(zhǔn)開發(fā)游戲。無論硬件是否支持某特殊效果，只要DirectX標(biāo)準(zhǔn)中有，程序員就可以把它寫到游戲中，當(dāng)這個(gè)游戲在硬件上運(yùn)行，如果此硬件根據(jù)DirectX標(biāo)準(zhǔn)把這個(gè)效果做到了此硬件驅(qū)動程序中，驅(qū)動程序駕馭其硬件算出此效果，用戶就可以欣賞到此效果。DirectXDirectX主要應(yīng)用于游戲軟件的開發(fā)。60Java3DJava3DAPI是Sun定義的用于實(shí)現(xiàn)3D顯示的接口。3D技術(shù)是底層的顯示技術(shù)，Java3D提供了基于Java的上層接口。Java3D把OpenGL和DirectX這些底層技術(shù)包裝在Java接口中。這種全新的設(shè)計(jì)使3D技術(shù)變得不再繁瑣并且可以加入到J2SE、J2EE的整套架構(gòu)，這些特性保證了Java3D技術(shù)強(qiáng)大的擴(kuò)展性。Java3DJava3DAPI是Sun定義的用于實(shí)現(xiàn)3D顯61Java3DJava3D實(shí)現(xiàn)了以下三維顯示能夠用到的功能生成簡單或復(fù)雜的形體（也可以調(diào)用現(xiàn)有的三維形體）使形體具有顏色、透明效果、貼圖等在三維環(huán)境中生成燈光、移動燈光等具有行為處理判斷能力（鍵盤、鼠標(biāo)、定時(shí)等）生成霧、背景、聲音等。使形體變形、移動、生成三維動畫等。編寫非常復(fù)雜的應(yīng)用程序，用于各種領(lǐng)域如VR（虛擬現(xiàn)實(shí)）Java3D是一個(gè)獨(dú)立的可選組件，可以單獨(dú)下載Java3DJava3D實(shí)現(xiàn)了以下三維顯示能夠用到的功能62VRMLVRML(VirtualRealityModelingLanguage)是一種標(biāo)記語言，而不是一種API開發(fā)包。它使用VRML瀏覽器能讀懂的ASCⅡ文本格式來描述世界和鏈接。VRML既可以用來建立真實(shí)世界場景的模型，也可以建立虛構(gòu)的三維世界，就像許多游戲那樣。VRML的設(shè)計(jì)是從在Web上欣賞實(shí)時(shí)的3D圖像開始的。VRML瀏覽器，既是插件，又是幫助應(yīng)用程序，還是獨(dú)立運(yùn)行的應(yīng)用程序，它是傳統(tǒng)的虛擬現(xiàn)實(shí)中同樣也使用的實(shí)時(shí)3D著色引擎。這使得VRML應(yīng)用從三維建模和動畫應(yīng)用中分離出來，在三維建模和動畫應(yīng)用中可以預(yù)先對前方場景進(jìn)行著色，但是沒有選擇方向的自由。VRMLVRML(VirtualRealityModeli63VRMLVRML提供了6+1個(gè)自由度，可以沿著三個(gè)方向移動，也可以沿著三個(gè)方位旋轉(zhuǎn)，同時(shí)還可以建立與其他3D空間的超鏈接。因此VRML是超空間的。VRML使用場景圖(SceneGraph)數(shù)據(jù)結(jié)構(gòu)來建立3D實(shí)境，這種數(shù)據(jù)結(jié)構(gòu)是以SGI開發(fā)的OpenInventor3D工具包為基礎(chǔ)的一種數(shù)據(jù)格式。VRML的場景圖是—種代表所有3D世界靜態(tài)特征的節(jié)點(diǎn)等級：幾何關(guān)系、質(zhì)材、紋理、幾何轉(zhuǎn)換、光線、視點(diǎn)以及嵌套結(jié)構(gòu)。幾乎所有生產(chǎn)三維產(chǎn)品的廠商，無論是CAD、建模、動畫、VR，還是VRML，它們的結(jié)構(gòu)核心都有場景圖。VRMLVRML提供了6+1個(gè)自由度，可以沿著三個(gè)方向移動，64VRMLVRML在許多方面是與HTML平行的。VRML的文件.wrl是由可閱讀的ASCⅡ文本構(gòu)成的。這樣一個(gè)文本編輯器就可以變成一個(gè)VRML世界的生成工具。程序員可以通過直接操作場景圖來得到完全的控制權(quán)和高度的靈活性。VRMLVRML在許多方面是與HTML平行的。65五種計(jì)算機(jī)圖形開發(fā)技術(shù)比較五種計(jì)算機(jī)圖形開發(fā)技術(shù)比較66總結(jié)光柵圖形學(xué)：經(jīng)典基礎(chǔ)算法基本幾何的表示和計(jì)算：算法的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：計(jì)算機(jī)圖形學(xué)的基礎(chǔ)圖形變換：新的敘述方法——幾何表示圖形輸入：三維造型、曲線、曲面圖形輸出：光照模型虛擬現(xiàn)實(shí)：計(jì)算機(jī)圖形學(xué)的極致應(yīng)用總結(jié)光柵圖形學(xué)：經(jīng)典基礎(chǔ)算法67考核方法開發(fā)語言C/C++/matlab工具庫OpenGL,OGRE,Direct3D,不強(qiáng)調(diào)全部自己開發(fā)分組可以采用單人或分組方式，人數(shù)最多不超過四人可以跨班級組隊(duì)評分作品創(chuàng)意，效果，難度，分工，總結(jié)材料考核方法開發(fā)語言C/C++/matlab68總結(jié)材料文檔總體方案詳細(xì)設(shè)計(jì)源代碼注釋成果展示要求提交的文件結(jié)構(gòu)清晰，內(nèi)容完整源程序可讀性好設(shè)計(jì)報(bào)告有總體框架，算法描述總結(jié)材料文檔69作品綜合運(yùn)用各個(gè)課程知識策劃設(shè)計(jì)開發(fā)測試總結(jié)作品綜合運(yùn)用各個(gè)課程知識70計(jì)算機(jī)圖形學(xué)東北大學(xué)聞時(shí)光計(jì)算機(jī)圖形學(xué)東北大學(xué)聞時(shí)光71課程簡介學(xué)習(xí)方法實(shí)驗(yàn)課小組項(xiàng)目聯(lián)系方式CGcourse@163.com83688326聞時(shí)光課程簡介學(xué)習(xí)方法72參考書目陳元琰《計(jì)算機(jī)圖形學(xué)實(shí)用技術(shù)》清華大學(xué)出版社2007.3孔令德《計(jì)算機(jī)圖形學(xué)實(shí)用教程》清華大學(xué)出版社2008.4PhilipJ.Schneider《計(jì)算機(jī)圖形學(xué)幾何工具算法詳解》電子工業(yè)出版社2005.1參考書目陳元琰《計(jì)算機(jī)圖形學(xué)實(shí)用技術(shù)》清華大學(xué)出版社2073圖形圖形是傳遞信息最主要的媒體之一。人們使用圖形來表達(dá)與交流思想有著悠久的歷史，工程領(lǐng)域和各個(gè)科學(xué)分支都離不開圖。它能使人們通觀全局，一目了然。人的眼睛從一張圖紙中吸收信息比從一張數(shù)據(jù)表格吸收信息快得多。若圖形和數(shù)字互為補(bǔ)充，則可使人們更深刻地認(rèn)識事物的本質(zhì)及其內(nèi)在聯(lián)系。圖形圖形是傳遞信息最主要的媒體之一。74計(jì)算機(jī)圖形學(xué)定義是研究怎樣利用計(jì)算機(jī)表示、生成、處理和顯示圖形的原理、算法、方法和技術(shù)的一門學(xué)科。它與一般的科學(xué)計(jì)算不同。在一般的科學(xué)計(jì)算中，涉及的是數(shù)字運(yùn)算，在計(jì)算機(jī)圖形學(xué)中則是以基本的幾何元素為其運(yùn)算對象的。這些幾何元素描述物體的模擬圖示表示：符號、線圖、陰影區(qū)域和物體等。研究計(jì)算機(jī)圖形學(xué)的主要工具是圖形顯示系統(tǒng)和繪圖機(jī)、打印機(jī)等，乃至三維虛擬環(huán)境。計(jì)算機(jī)圖形學(xué)定義是研究怎樣利用計(jì)算機(jī)表示、生成、處理和顯示圖75計(jì)算機(jī)圖形學(xué)相關(guān)學(xué)科C.G.——對非圖形信息產(chǎn)生圖形I.P.——對圖象采用增強(qiáng)、變換等技術(shù)進(jìn)行處理增強(qiáng)(對比度)：對暴光過度或不足，以及 模糊的圖象進(jìn)行處理。變換：一幅亮度范圍寬的圖象—>兩種亮 度的圖象—>線條狀圖形P.R.——對圖象提取特征、予以分類 和描述關(guān)系，再進(jìn)行模式匹配計(jì)算機(jī)圖形學(xué)相關(guān)學(xué)科C.G.——對非圖形信息產(chǎn)生圖形I.P.76C.G.、I.P.和P.R.之間的區(qū)別描述圖像I.P.C.G.P.R.C.G.、I.P.和P.R.之間的區(qū)別描述圖像I.P.C77應(yīng)用領(lǐng)域1.管理、科學(xué)技術(shù)2.制圖學(xué)3.動畫4.計(jì)算機(jī)輔助設(shè)計(jì)CAD5.模擬6.藝術(shù)和教育7.辦公自動化應(yīng)用領(lǐng)域1.管理、科學(xué)技術(shù)78管理、科學(xué)技術(shù)繪制數(shù)學(xué)、物理以及經(jīng)濟(jì)函數(shù)的二維及三維圖形：直方圖、線條圖、扇形圖、進(jìn)程圖...特點(diǎn)：簡潔、直觀——>數(shù)據(jù)的模型和趨勢。管理、科學(xué)技術(shù)繪制數(shù)學(xué)、物理以及經(jīng)濟(jì)函數(shù)的二維及三維圖形：直79制圖學(xué)以高精度的地理或其他自然現(xiàn)象的圖形—>紙或膠片上。包括地圖、地質(zhì)圖、油層圖、海圖、氣象、人口密度圖...制圖學(xué)以高精度的地理或其他自然現(xiàn)象的圖形—>紙或膠片上80動畫用計(jì)算機(jī)可以產(chǎn)生逼真的動畫效果，可用于藝術(shù)創(chuàng)作，模擬真實(shí)的環(huán)境，或進(jìn)行飛機(jī)、駕駛等訓(xùn)練。動畫用計(jì)算機(jī)可以產(chǎn)生逼真的動畫效果，可用于藝術(shù)創(chuàng)作，模擬真81計(jì)算機(jī)輔助設(shè)計(jì)CAD設(shè)計(jì){元部件：機(jī)械、電氣、電子設(shè)備...系統(tǒng){結(jié)構(gòu)(建筑物、汽車車身、飛機(jī)和船的外殼及內(nèi)部結(jié)構(gòu))光學(xué)系統(tǒng)電話及計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)輔助設(shè)計(jì)CAD設(shè)計(jì){元部件：機(jī)械、電氣、電子設(shè)備..82汽車效果圖和線框圖汽車效果圖和線框圖83模擬數(shù)學(xué)圖形——科學(xué)現(xiàn)象的數(shù)學(xué)模型(液體流動、相對論、核反應(yīng)、化學(xué)反應(yīng)、生理系統(tǒng)與器官以及有負(fù)載時(shí)結(jié)構(gòu)的變形等)DNA皮膚結(jié)構(gòu)：真皮，上皮及附屬結(jié)構(gòu)模擬數(shù)學(xué)圖形——科學(xué)現(xiàn)象的數(shù)學(xué)模型(液體流動、相對論、核84模擬云霧、煙、其他大小形狀不同的飛機(jī)等特殊景物飛行模擬器：固定環(huán)境的景色可用在月球登陸的宇航員(練習(xí)登月）、宇宙飛船駕駛員(首航前訓(xùn)練)模擬云霧、煙、其他大小形狀不同的飛機(jī)等特殊景物85過程控制利用交互式圖形生成技術(shù)形成的人機(jī)交互系統(tǒng)，實(shí)現(xiàn)人與控制或管理對象之間的相互作用。如工廠中的設(shè)備、工序控制，機(jī)場與鐵路的調(diào)度等。過程控制利用交互式圖形生成技術(shù)形成的人機(jī)交互系統(tǒng)，實(shí)現(xiàn)人與控86藝術(shù)和教育：教學(xué)活動蟬（線框圖）藝術(shù)和教育：教學(xué)活動蟬（線框圖）87藝術(shù)和教育藝術(shù)廣告藝術(shù)繪畫藝術(shù)和教育藝術(shù)廣告88辦公自動化在辦公室中，用圖形方式顯示并交換文件、報(bào)表、圖例和其它信息，并在輸出設(shè)備上輸出、保存起來。辦公自動化在辦公室中，用圖形方式顯示并交換文件、報(bào)表、圖例和89圖形學(xué)發(fā)展歷史50s1950年，第一臺圖形顯示器作為美國麻省理工學(xué)院（MIT）旋風(fēng)I號（WhirlwindI）計(jì)算機(jī)的附件誕生了。該顯示器用一個(gè)類似于示波器的陰極射線管（CRT）來顯示一些簡單的圖形。1958年美國Calcomp公司由聯(lián)機(jī)的數(shù)字記錄儀發(fā)展成滾筒式繪圖儀，GerBer公司把數(shù)控機(jī)床發(fā)展成為平板式繪圖儀。圖形學(xué)發(fā)展歷史50s1950年，第一臺圖形顯示器作為美國麻省90圖形學(xué)發(fā)展歷史60s1962年，MIT林肯實(shí)驗(yàn)室的IvanE.Sutherland發(fā)表了一篇題為“Sketchpad：一個(gè)人機(jī)交互通信的圖形系統(tǒng)”的博士論文，首次使用“ComputerGraphics”這個(gè)術(shù)語，證明了交互計(jì)算機(jī)圖形學(xué)是一個(gè)可行的、有用的研究領(lǐng)域1964年MIT的教授StevenA.Coons提出了被后人稱為超限插值的新思想，通過插值四條任意的邊界曲線來構(gòu)造曲面。同在60年代早期，法國雷諾汽車公司的工程師PierreBézier發(fā)展了一套Bézier曲線、曲面的理論，成功地用于幾何外形設(shè)計(jì)。Coons方法和Bézier方法是CAGD最早的開創(chuàng)性工作。圖形學(xué)發(fā)展歷史60s1962年，MIT林肯實(shí)驗(yàn)室的Ivan91圖形學(xué)發(fā)展歷史70s70年代是計(jì)算機(jī)圖形學(xué)發(fā)展過程中一個(gè)重要的歷史時(shí)期。光柵顯示器的產(chǎn)生，圖形學(xué)進(jìn)入了第一個(gè)興盛的時(shí)期，并開始出現(xiàn)實(shí)用的CAD圖形系統(tǒng)1977、1979年開始，計(jì)算機(jī)圖形學(xué)標(biāo)準(zhǔn)制定，真實(shí)感圖形學(xué)和實(shí)體造型技術(shù)的產(chǎn)生。1970年Bouknight提出了第一個(gè)光反射模型，1971年Gourand提出“漫反射模型＋插值”的思想，被稱為Gourand明暗處理。r1975年P(guān)hong提出了著名的簡單光照模型—Phong模型。這些可以算是真實(shí)感圖形學(xué)最早的開創(chuàng)性工作。從1973年開始，相繼出現(xiàn)了英國劍橋大學(xué)CAD小組的Build系統(tǒng)、美國羅徹斯特大學(xué)的PADL-1系統(tǒng)等實(shí)體造型系統(tǒng)。圖形學(xué)發(fā)展歷史70s70年代是計(jì)算機(jī)圖形學(xué)發(fā)展過程中一個(gè)重要92圖形學(xué)發(fā)展歷史80s1980年Whitted提出了一個(gè)光透視模型—Whitted模型，并第一次給出光線跟蹤算法的范例，實(shí)現(xiàn)Whitted模型。1984年，美國Cornell大學(xué)和日本廣島大學(xué)的學(xué)者分別將熱輻射工程中的輻射度方法引入到計(jì)算機(jī)圖形學(xué)中，用輻射度方法成功地模擬了理想漫反射表面間的多重漫反射效果。1986年，美國科學(xué)基金會（NSF）專門召開了一次研討會，會上提出了“科學(xué)計(jì)算可視化（VisualizationinScientificComputing，簡稱為ViSC）”。圖形學(xué)發(fā)展歷史80s1980年Whitted提出了一個(gè)光透視93SIGGRAPHSIGGRAPH會議，“TheSpecialInterestGrouponComputerGraphicsandInteractiveTechniques”ACMSIGGRAPH會議是計(jì)算機(jī)圖形學(xué)最權(quán)威的國際會議，每年在美國召開，參加會議的人在50,000人左右。世界上沒有第二個(gè)領(lǐng)域每年召開如此規(guī)模巨大的專業(yè)會議，SIGGRAPH會議很大程度上促進(jìn)了圖形學(xué)的發(fā)展。

1974年在Colorado大學(xué)召開了第一屆SIGGRAPH年會。因?yàn)槊磕曛讳浫〈蠹s50篇論文，在ComputerGraphics雜志上發(fā)表，因此論文的學(xué)術(shù)水平較高，基本上代表了圖形學(xué)的主流方向。SIGGRAPHSIGGRAPH會議，“TheSpec94虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)技術(shù)就是利用計(jì)算機(jī)生成一個(gè)逼真的三維虛擬環(huán)境，通過自然技能使用傳感設(shè)備與之相互作用的新技術(shù)。它與傳統(tǒng)的模擬技術(shù)完全不同，是將模擬環(huán)境、視景系統(tǒng)和仿真系統(tǒng)合三為一，利用頭盔顯示器、圖形眼鏡、數(shù)據(jù)服、立體聲耳機(jī)、數(shù)據(jù)手套及腳踏板等傳感裝置，把操作者與計(jì)算機(jī)生成的三維虛擬環(huán)境連結(jié)在一起。與傳統(tǒng)計(jì)算機(jī)相比，虛擬現(xiàn)實(shí)系統(tǒng)具有三個(gè)重要特征：臨境性、交互性、想象性。虛擬現(xiàn)實(shí)建模語言VRML是描述虛擬環(huán)境中場景的一種標(biāo)準(zhǔn)，可以利用它在INTERNET建立交互式的三維多媒體環(huán)境。VRML的基本特征包括分布式、交互式、平臺無關(guān)、三維、多媒體集成和逼真自然等，國際標(biāo)準(zhǔn)化組織1998年1月正式將其批準(zhǔn)為國際標(biāo)準(zhǔn)。虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)技術(shù)就是利用計(jì)算機(jī)生成一個(gè)逼真的三維虛擬環(huán)境95計(jì)算機(jī)藝術(shù)可用于美術(shù)創(chuàng)作的軟件很多，如二維平面的畫筆程序(如CorelDraw，Photoshop，PaintShop)、專門的圖表繪制軟件(如Visio)、三維建模和渲染軟件包(如3DMAX，Maya)、以及一些專門生成動畫的軟件(如Alias，SoftImage)等。這些軟件不僅提供多種風(fēng)格的畫筆、畫刷，而且提供多種多樣的紋理貼圖，甚至能對圖像進(jìn)行霧化/變形等操作。很多功能是一個(gè)傳統(tǒng)的藝術(shù)家無法實(shí)現(xiàn)也不可想象的。當(dāng)然，傳統(tǒng)藝術(shù)的一些效果也是上述軟件所不能達(dá)到的。例如鋼筆素描的效果，由于鋼筆素描與傳統(tǒng)的圖形學(xué)繪制方法差別很大，所以研究起來難度也頗大，很多學(xué)者已在這方面做了卓有成效的工作，取得了一定的成果。計(jì)算機(jī)藝術(shù)可用于美術(shù)創(chuàng)作的軟件很多，如二維平面的畫筆程序(如96圖形用戶接口用戶接口是人們使用計(jì)算機(jī)的第一觀感。一個(gè)友好的圖形化的用戶界面能夠大大提高軟件的易用性，在DOS時(shí)代，計(jì)算機(jī)的易用性很差，編寫一個(gè)圖形化的界面要費(fèi)去大量的勞動，過去軟件中有60％的程序是用來處理與用戶接口有關(guān)的問題和功能的。進(jìn)入80年代后，隨著Xwindow標(biāo)準(zhǔn)的面世，蘋果公司圖形化操作系統(tǒng)的推出，特別是微軟公司W(wǎng)indows操作系統(tǒng)的普及，標(biāo)志著圖形學(xué)已經(jīng)全面融入計(jì)算機(jī)的方方面面。目前幾個(gè)大的軟件公司都在研究下一代用戶界面，開發(fā)面向主流應(yīng)用的自然、高效多通道的用戶界面。研究多通道語義模型、多通道整合算法及其軟件結(jié)構(gòu)和界面范式是當(dāng)前用戶界面和接口方面研究的主流方向，而圖形學(xué)在其中起主導(dǎo)作用。圖形用戶接口用戶接口是人們使用計(jì)算機(jī)的第一觀感。一個(gè)友好的圖97計(jì)算機(jī)圖形學(xué)研究的基本問題圖形描述基本幾何：直線、圓弧等；高級幾何：曲線、曲面等圖形變換二、三維變換、三維到二維、觀察流程、幾何變換等圖形運(yùn)算基本幾何間的計(jì)算、裁剪、布爾運(yùn)算等圖形顯示/輸出基本圖形生成算法、消隱、繪圖、光照模型等圖形輸入交互技術(shù)、參數(shù)化設(shè)計(jì)、造型技術(shù)等算法和算法復(fù)雜性分析空間和時(shí)間等計(jì)算機(jī)圖形學(xué)研究的基本問題圖形描述98兩個(gè)核心問題如何建模交互技術(shù)曲線造型如何繪制光柵圖形學(xué)光照模型裁剪計(jì)算顏色模型兩個(gè)核心問題如何建模99圖形描述一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)所懂得，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在顯示屏幕或繪圖機(jī)上輸出；而圖形是模型的一個(gè)具體可見像，是人們所看到的模型的表征。在三維空間，描述的是幾何形體和幾何曲面，只有在平面上，它才是人們通常所稱的圖形。圖形描述一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)所懂得，并100圖形描述幾何形體以封閉的表面表示，一般為一個(gè)由平面和曲面圍成的多面體。一個(gè)幾何形體在空間上應(yīng)是完備的(幾何性和拓?fù)湫?，而且包含足夠的用于推導(dǎo)的任何空間函數(shù)(如直線方程、平面方程、曲面構(gòu)造等)以及進(jìn)行各種形體運(yùn)算與處理的信息。圖形描述幾何形體以封閉的表面表示，一般為一個(gè)由平面和曲面圍成101圖形描述在多面體表示中，有關(guān)的基本元素（體、面、環(huán)、棱和頂點(diǎn)）的信息分為二大類：幾何信息：用以確定每個(gè)分量在歐氏空間中的幾何位置(如點(diǎn)坐標(biāo))和描述(如平面方程系數(shù))；拓?fù)湫畔ⅲ河脕矶x幾何元素的數(shù)目及相互間的連接關(guān)系。幾何信息只考慮點(diǎn)、線和無限面。拓?fù)湫畔Ⅻc(diǎn)看作頂點(diǎn)，將線限制為棱(線段)，由外環(huán)和內(nèi)環(huán)定義出面和內(nèi)孔。一個(gè)完全的三維幾何體描述，幾何信息和拓?fù)湫畔烧叨际潜匾膱D形描述在多面體表示中，有關(guān)的基本元素（體、面、環(huán)、棱和頂點(diǎn)102圖形描述描述一個(gè)多面體各元素之間的拓?fù)潢P(guān)系可以互相推導(dǎo)。故理論上只需存儲一種關(guān)系就行了，但由于關(guān)系的推導(dǎo)要付出代價(jià)，所以一般的系統(tǒng)常同時(shí)存儲若于種拓?fù)潢P(guān)系。這些拓?fù)潢P(guān)系，既要足夠地表示出幾何形體的構(gòu)造，又要盡量壓縮信息的存儲量，且要便于檢索和修改，而十分重要的是要便于計(jì)算機(jī)的自動生成。圖形描述描述一個(gè)多面體各元素之間的拓?fù)潢P(guān)系可以互相推導(dǎo)。故理103圖形描述對于曲表面的幾何形體，需分別研究自由曲線和自由曲面的建立；用于插值和數(shù)學(xué)放樣的三次樣條函數(shù)是應(yīng)用得最早研究得最詳盡的一種。Bezier曲線和曲面與B樣條曲線和曲面是在計(jì)算機(jī)輔助幾何設(shè)計(jì)應(yīng)用最廣的曲線和曲面幾何構(gòu)型方法。關(guān)于這些方面的研究，至今仍在繼續(xù)發(fā)展中。圖形描述對于曲表面的幾何形體，需分別研究自由曲線和自由曲面的104圖形描述平面上圖形的描述是基于直線和圓弧的描述。僅用這兩種基本幾何元素就可構(gòu)成平面上的任何圖形。因而直線段和圓弧段也叫基本幾何段，本課程將詳加闡述。數(shù)據(jù)結(jié)構(gòu)技術(shù)在圖形描述中起著關(guān)鍵的作用。線性鏈接表、樹結(jié)構(gòu)、堆棧、隊(duì)列等將廣泛應(yīng)用于幾何模型的描述、運(yùn)算和顯示中。圖形描述平面上圖形的描述是基于直線和圓弧的描述。僅用這兩種基105圖形輸入圖形輸入需要解決的問題是：交互輸入的方法。工程設(shè)計(jì)圖紙直接輸入（矢量識別）的方法。將自由手書的立體構(gòu)造或三視圖重構(gòu)的方法。計(jì)算機(jī)自動生成方法。從物體的多幅深度圖像重建三維幾何模型。通過三維激光掃描儀在物體表面測得一些離散點(diǎn)，再用重構(gòu)算法生成網(wǎng)格模型等等。圖形輸入圖形輸入需要解決的問題是：106圖形輸入圖形輸入的常規(guī)方法是將事先寫好的源程序(指令)在屏幕上輸入，即所謂的編程輸入，使得人、機(jī)之間的交互作用緩慢。對于工程上常用的一類規(guī)格化圖形，可以編制一個(gè)通用程序，采用格式數(shù)據(jù)輸入的辦法得到圖形。但是在處理三維的，或是形狀復(fù)雜的物體時(shí)還有較多的困難，輸入數(shù)據(jù)太多就是一個(gè)障礙。圖形輸入圖形輸入的常規(guī)方法是將事先寫好的源程序(指令)在屏幕107圖形輸入除了這種圖形的直接輸入之外，通過對基本體元的構(gòu)型產(chǎn)生新的、復(fù)雜的三維物體也是一種輸入的手段，當(dāng)然這需要涉及更多的研究。從計(jì)算機(jī)圖形學(xué)的發(fā)展情況看，對圖形輸出的研究多于對圖形輸入的研究，許多人往往被計(jì)算機(jī)輸出的美妙圖形所迷惑，卻看不到為得到這些圖形所做的大量數(shù)據(jù)輸入的準(zhǔn)備工作。圖形輸入的工作量和難度并不亞于幾何算法和圖形輸出。隨著時(shí)間的推移，圖形輸入將越來越成為計(jì)算圖形學(xué)應(yīng)用中的主要障礙。圖形輸入除了這種圖形的直接輸入之外，通過對基本體元的構(gòu)型產(chǎn)生108圖形變換一個(gè)圖形系統(tǒng)需具有圖形變換的功能。這種變換包括二維變換、三維變換和三維向二維的變換三種。對應(yīng)于幾何元素及其選定的坐標(biāo)系來說，則包括幾何變換和坐標(biāo)系變換兩種。這些變換系統(tǒng)稱為圖形變換。在構(gòu)造、產(chǎn)生、處理和輸出圖形的各個(gè)環(huán)節(jié)，圖形變換起著重要的作用。圖形變換一個(gè)圖形系統(tǒng)需具有圖形變換的功能。這種變換包括二維變109圖形變換人們可以直接定義一個(gè)幾何圖形或幾何體，也可通過對某些幾何體的變換去構(gòu)造新的幾何體或其中的某個(gè)部份。這種變換可以是平移、放大(縮小)、旋轉(zhuǎn)、反射、錯(cuò)切等。一個(gè)三維場景通常就是由一些基本幾何元素通過上述操作構(gòu)造的。例如，可以通過平移的辦法裝配一幢建筑物的大部份窗子，這使得圖形輸入大為簡化。在進(jìn)行圖形處理的過程中，還可以放大一個(gè)圖形以便使其某一部份能更清楚地顯示；縮小圖形以便看到圖形更多的部份。圖形變換人們可以直接定義一個(gè)幾何圖形或幾何體，也可通過對某些110圖形變換在顯示或繪制一個(gè)環(huán)境的時(shí)候，需要將三維信息映射到二維屏幕上。軸測投影、平行投影和透視投影用于完成這項(xiàng)工作。在視點(diǎn)改變得非?？旎蛭矬w相對運(yùn)動的應(yīng)用場合，變換必須反復(fù)運(yùn)用。因此，找到一個(gè)有效的方法去實(shí)現(xiàn)圖形變換是十分重要的。圖形變換在顯示或繪制一個(gè)環(huán)境的時(shí)候，需要將三維信息映射到二維111圖形變換采用向量、矩陣和齊次坐標(biāo)的形式去描述圖形變換是一種比較好的辦法，它允許將線性代數(shù)的一些基本理論應(yīng)用到圖形變換中。例如一個(gè)矩陣對應(yīng)于一個(gè)變換，圖形的連續(xù)變換可由矩陣的相乘實(shí)現(xiàn)，而逆矩陣對應(yīng)于一個(gè)逆變換。所有的變換都基于點(diǎn)變換，例如對一條線段的變換只需考慮其兩個(gè)端點(diǎn)的變換就可以了?；編缀卧孛枋龅淖儞Q也和點(diǎn)的變換有密切的聯(lián)系。例如描述一條直線的方程系數(shù)在不同坐標(biāo)下的關(guān)系也可由點(diǎn)變換的相應(yīng)變換矩陣求得。圖形變換采用向量、矩陣和齊次坐標(biāo)的形式去描述圖形變換是一種比112圖形運(yùn)算在三維空間，圖形的運(yùn)算是一種幾何形體的運(yùn)算，它是CAGD的一個(gè)重要操作，這種操作通常叫做物體造型，或幾何造型。設(shè)計(jì)人員可通過修改立方體，圓柱體之類的基本體元來生成形體。例如通過縮放，通過用集合論中的并、交、非、差等概念所進(jìn)行的各種布爾運(yùn)算把一些基本物體體元組合起來。設(shè)計(jì)人員的職責(zé)是把各體元正確地定位下來，使得這些運(yùn)算能進(jìn)行下去。另一方面幾何造型系統(tǒng)還負(fù)責(zé)估計(jì)各體元之間的相互作用，各種相交出現(xiàn)的位置以及它們之間的相互關(guān)系，以確保生成法定的三維形體。系統(tǒng)還必須正確地、在計(jì)算機(jī)限制下內(nèi)盡可能精確地完成相交分析。圖形運(yùn)算在三維空間，圖形的運(yùn)算是一種幾何形體的運(yùn)算，它是CA113圖形運(yùn)算幾何造型系統(tǒng)常處理一些比較簡單的體元：立方體、圓柱體、楔、嵌條，以直線或圓弧為邊界的薄片等。所涉及的線和面在幾何上是簡單的直線、圓弧、平面和圓柱面，處理這些由一個(gè)正確的方式構(gòu)造出來的物體的相交，從概念上是比較容易的。但主要困難在于：雖然幾何簡單，但多個(gè)元素的拼合卻是復(fù)雜的。故對于確實(shí)復(fù)雜的形體的組合問題，所需的幾何算法的效率就變得十分重要，需進(jìn)行幾何復(fù)雜性分析。圖形運(yùn)算幾何造型系統(tǒng)常處理一些比較簡單的體元：立方體、圓柱體114圖形運(yùn)算幾何造型系統(tǒng)較之早期圖形系統(tǒng)的顯著優(yōu)越之處在于：無需人為干預(yù)就能預(yù)定形體與執(zhí)行一連串運(yùn)算。即具有高度自動化的圖形定義或構(gòu)造、產(chǎn)生處理或演變功能。幾何元素的定向在圖形運(yùn)算中起著相當(dāng)大的作用。例如平面圖形的幾何運(yùn)算就是建立在以向量為基本幾何元素的環(huán)的基礎(chǔ)上實(shí)現(xiàn)的。直線和圓弧這兩種基本幾何段的相貫運(yùn)算是平面圖形運(yùn)算的基礎(chǔ)，保證這些算法的準(zhǔn)確性，提高這些算法的效率是計(jì)算機(jī)圖形系統(tǒng)一項(xiàng)基礎(chǔ)性的工作。圖形運(yùn)算幾何造型系統(tǒng)較之早期圖形系統(tǒng)的顯著優(yōu)越之處在于：無需115圖形輸出圖形輸出是人—機(jī)交互系統(tǒng)中人們能夠得到的最直觀的結(jié)果。它直接向人們顯示出計(jì)算機(jī)圖形系統(tǒng)的效果。相對而言，圖形輸出計(jì)算機(jī)圖學(xué)中研究得最早、最深入、解決得最好的一部份工作。圖形輸出圖形輸出是人—機(jī)交互系統(tǒng)中人們能夠得到的最直觀的結(jié)116圖形輸出一個(gè)物體的制造者可以從一張多視圖的圖樣里了解到許多內(nèi)容。因此，一個(gè)能在二維參考平面里提供綜合的，繪制直線和曲線的系統(tǒng)也就提供了畫出一個(gè)復(fù)雜而詳細(xì)的圖形或物體的基礎(chǔ)。但是，圖形只是三維物體的某一個(gè)特定的不完整的表示。而物體有一種圖里沒有的，與眾不同的特性——完全的三維定義。人們可以隨意地在三維空間中把物體旋轉(zhuǎn)和平移以及物體的綜合，但一般不能用圖形做到這一點(diǎn)。圖形輸出一個(gè)物體的制造者可以從一張多視圖的圖樣里了解到許多內(nèi)117圖形輸出基本幾何（點(diǎn)、直線、圓及圓弧等）和文字的光柵化顯示，幾何裁剪算法基本幾何的描述、相交算法，曲線擬合和雙圓弧逼近算法，動態(tài)顯示的插值算法。圖形顯示中的裁剪算法，通常稱為窗口算法；隱藏線、隱藏面消除算法。光照模型及算法。紋理貼圖；大規(guī)模場景顯示算法；圖形顯示軟件和打印機(jī)、繪圖機(jī)等的圖形輸出后處理軟件等等。圖形輸出基本幾何（點(diǎn)、直線、圓及圓弧等）和文字的光柵化顯示，118幾何算法、幾何復(fù)雜性和計(jì)算效率一個(gè)動畫程序，一個(gè)游戲程序，用戶的起碼要求是“流暢”；支撐它的是幾何算法，幾何復(fù)雜性問題及計(jì)算的效率。許多通過交互設(shè)計(jì)各種形體的系統(tǒng)，其成功的主要斷依據(jù)是憑視覺。例如套料問題，這在造船、服裝等行業(yè)是極為有用的，然而至今存在的系統(tǒng)還是由人機(jī)交互作用來完成。而幾何造型系統(tǒng)在相交問題的正確算法和處理組合比較復(fù)雜問題的能力，這種系統(tǒng)的發(fā)展表明，需要多多研究幾何算法。幾何算法、幾何復(fù)雜性和計(jì)算效率一個(gè)動畫程序，一個(gè)游戲程序，用119幾何算法、幾何復(fù)雜性和計(jì)算效率幾何相交問題在幾何算法中占有較大的比重，在平面上，它處理直線和直線，圓弧和直線，圓弧和圓弧等基本幾何的相交，在三維空間則是處理直線和平面，平面和平面的相互關(guān)系。但是，并不是所有的處理直線和直線的相交都是簡易的。例如，考慮兩個(gè)平面多邊形相交的狀態(tài)，按照Shamos(1978)算法，如果這兩個(gè)多邊形是凸的，對于n條邊的多邊形可以用O(n)的時(shí)間解決這個(gè)問題。而對于兩個(gè)任意非凸多邊形，為解決這個(gè)問題要花O(n2)的時(shí)間，可能形成達(dá)n2/4個(gè)不相疊的凸多邊形。幾何算法、幾何復(fù)雜性和計(jì)算效率幾何相交問題在幾何算法中占有較120幾何算法、幾何復(fù)雜性和計(jì)算效率觀察一個(gè)時(shí)間復(fù)雜性的例子：問題：設(shè)給定n個(gè)已經(jīng)排序的數(shù)的隊(duì)列，現(xiàn)在要插入一個(gè)新的數(shù)到這個(gè)隊(duì)列中，并保持隊(duì)列原有的次序，幾何復(fù)雜性為O(n)次主算。應(yīng)用二分法，可降為O(log2n)次。如果不計(jì)檢索到元素后對其處理所花費(fèi)的計(jì)算時(shí)間，而只對n的步數(shù)計(jì)算時(shí)間，那末當(dāng)n=60時(shí)：n：6×10-5秒N^2：36×10-4秒N^3：216×10-3秒N^5：13分鐘2^n：366世紀(jì)3^n：1.3×1013世紀(jì)幾何算法、幾何復(fù)雜性和計(jì)算效率觀察一個(gè)時(shí)間復(fù)雜性的例子：121幾何算法、幾何復(fù)雜性和計(jì)算效率降低幾何復(fù)雜性是幾何算法的一個(gè)努力目標(biāo)，它可以提高算法的效率。過去開發(fā)僅僅能“工作”的算法就常常足夠了，即使在某些情況下效率低也無妨。隨著使用計(jì)算機(jī)進(jìn)行幾何設(shè)計(jì)的增加，以及要解決問題的范圍之?dāng)U大，效率、精度和正確性的問題就變得非常重要了。幾何算法、幾何復(fù)雜性和計(jì)算效率降低幾何復(fù)雜性是幾何算法的一個(gè)122計(jì)算機(jī)圖形學(xué)的相關(guān)開發(fā)技術(shù)計(jì)算機(jī)圖形學(xué)經(jīng)過幾十年的發(fā)展，已經(jīng)達(dá)到了比較高的水平，目前已有若干圖形學(xué)軟件開發(fā)技術(shù)。利用這些開發(fā)技術(shù)，編寫圖形程序就容易多了，不必從底層開始，而只需將精力集中到圖形程序本身上。計(jì)算機(jī)圖形學(xué)的相關(guān)開發(fā)技術(shù)計(jì)算機(jī)圖形學(xué)經(jīng)過幾十年的發(fā)展，已經(jīng)123OpenGLOpenGL：OpenGL是OpenGraphicsLib的縮寫，是一套三維圖形處理庫，也是該領(lǐng)域的工業(yè)標(biāo)準(zhǔn)。OpenGL源于SGI公司為其圖形工作站開發(fā)的IRISGL，在跨平臺移植過程中發(fā)展成為OpenGL。OpenGL被設(shè)計(jì)成獨(dú)立于硬件，獨(dú)立于窗口系統(tǒng)的，在運(yùn)行各種操作系統(tǒng)的各種計(jì)算機(jī)上都可用，并能在網(wǎng)絡(luò)環(huán)境下以客戶/服務(wù)器模式工作，是專業(yè)圖形處理、科學(xué)計(jì)算等高端應(yīng)用領(lǐng)域的標(biāo)準(zhǔn)圖形庫。OpenGLOpenGL：OpenGL是OpenGraph124OpenGLMicrosoft、SGI、IBM、DEC、SUN、HP等大公司都采用了OpenGL作為三維圖形標(biāo)準(zhǔn)。許多軟件廠商也紛紛以O(shè)penGL為基礎(chǔ)開發(fā)出自己的產(chǎn)品，包括動畫制作軟件SoftImage和3DStudioMAX、仿真軟件OpenInventor、VR軟件WorldToolKit、CAD軟件Pro/Engineer、GIS軟件ARC/INFO等等。OpenGL實(shí)際上是一個(gè)開放的三維圖形軟件包，它獨(dú)立于窗口系統(tǒng)和操作系統(tǒng)，以它為基礎(chǔ)開發(fā)的應(yīng)用程序可以十分方便地在各種平臺間移植；OpenGL與C++緊密接合，便于實(shí)現(xiàn)圖形的相關(guān)算法，并可保證算法的正確性和可靠性；OpenGL使用簡便，效率高。OpenGLMicrosoft、SGI、IBM、DEC、SU125ACISACIS是美國SpatialTechnology公司推出的三維幾何引擎，為各種3D造型應(yīng)用的開發(fā)提供了幾何造型平臺，目前的最高本版已經(jīng)到了R13。ACIS能夠安裝在多種平臺上，包括Windows,Linux,Unix,Solaris,AIX等。ACIS采用了軟件組件技術(shù)，用C++技術(shù)構(gòu)造，它包含一整套的C++類和函數(shù)，開發(fā)人員可以使用這些類和函數(shù)構(gòu)造一個(gè)面向終端用戶的2/3維軟件系統(tǒng)。ACIS是一個(gè)基于邊界表示法的造型引擎，集線框、曲面和實(shí)體造型于一體，并允許這三種表示共存于統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)中。ACISACIS是美國SpatialTechnology公126ACISACIS系統(tǒng)的造型方法有：覆蓋技術(shù)(covering