第1章計算機(jī)圖形學(xué)綜述

第一章計算機(jī)圖形學(xué)

綜述曾智勇福建師范大學(xué)軟件學(xué)院Telmail:zengzhiy@圖形是傳遞信息最主要的媒體之一。人們使用圖形來表達(dá)與交流思想有著悠久的歷史，工程領(lǐng)域和各個科學(xué)分支都離不開圖。它能使人們通觀全局，一目了然。人的眼睛從一張圖紙中吸收信息比從一張數(shù)據(jù)表格吸收信息快得多(一幅畫勝千言萬語)。若圖形和數(shù)字互為補(bǔ)充，則可使人們更深刻地認(rèn)識事物的本質(zhì)及其內(nèi)在聯(lián)系。計算機(jī)圖形處理使計算機(jī)在處理復(fù)雜問題后輸出離散數(shù)據(jù)的同時，有可能以圖形的形式輸出其連續(xù)模型。計算機(jī)圖形學(xué)的發(fā)展和應(yīng)用在某種意義上已成為計算機(jī)軟、硬件發(fā)展水平的標(biāo)志。它已成為一門成熟的學(xué)科，是信息技術(shù)中不可缺少的重要內(nèi)容和發(fā)展基石。計算機(jī)圖形學(xué)課程也已成為大學(xué)計算機(jī)、機(jī)械等相關(guān)學(xué)科的一門主干課程。計算機(jī)圖形學(xué)之所以能在它短短的40多年歷史中獲得飛速發(fā)展，其根本原因是圖形為傳遞信息的最主要媒體之一。所有現(xiàn)代科學(xué)和工程領(lǐng)域幾乎都可以采用計算機(jī)圖形以加強(qiáng)信息的傳遞和理解，因此當(dāng)今的科學(xué)家和工程師都需要具備計算機(jī)圖形學(xué)的基本知識。計算機(jī)圖形學(xué)來源于生活、科學(xué)、工程技術(shù)、藝術(shù)、音樂、舞蹈、電影制作等，反過來，又大大促進(jìn)了這些領(lǐng)域的發(fā)展。計算機(jī)圖形學(xué)涉及怎樣用計算機(jī)去產(chǎn)生、表示、操作和處理圖示物體。它與一般的科學(xué)計算不同。在一般的科學(xué)計算中，涉及的是數(shù)字運(yùn)算，在計算機(jī)圖形學(xué)中則是以基本的幾何元素為其運(yùn)算對象的。這些幾何元素描述物體的模擬圖示表示：符號、線圖、陰影區(qū)域和物體等。研究計算機(jī)圖形學(xué)的主要工具是圖形顯示系統(tǒng)和繪圖機(jī)、打印機(jī)等，乃至三維虛擬環(huán)境。什么是計算機(jī)圖形學(xué)

ComputerGraphics(CG)

計算機(jī)圖形學(xué)是研究怎樣用計算機(jī)表示、生成、處理和顯示圖形的原理、算法、方法和技術(shù)的一門學(xué)科。

國際標(biāo)準(zhǔn)化組織(ISO)的定義：

計算機(jī)圖形學(xué)是研究通過計算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在專門顯示設(shè)備上顯示的原理、方法和技術(shù)的學(xué)科。它是建立在傳統(tǒng)的圖學(xué)理論、應(yīng)用數(shù)學(xué)和計算機(jī)科學(xué)基礎(chǔ)上的一門邊緣學(xué)科。1.1計算機(jī)圖形學(xué)及它與其他學(xué)科的關(guān)系計算機(jī)圖形學(xué)與其他學(xué)科CAD（及計算機(jī)繪圖）、計算幾何/計算機(jī)輔助幾何設(shè)計（CAGD）、圖像（及識別）等的關(guān)系是界線模糊、相互交叉、相互滲透的。圖像（image）：計算機(jī)中以具有顏色信息的點(diǎn)陣來表示的圖形，它強(qiáng)調(diào)圖形由哪些點(diǎn)組成，記錄點(diǎn)及它的灰度或色彩。圖形（graphics）：計算機(jī)中由場景的幾何模型和景物的物理屬性表示的圖形，它更強(qiáng)調(diào)場景的幾何表示，記錄圖形的形狀參數(shù)與屬性參數(shù)。它的顯示形式是基于線條信息的矢量圖和基于明暗（Shading）處理后的圖像圖。1.1計算機(jī)圖形學(xué)及它與其他學(xué)科的關(guān)系1.1計算機(jī)圖形學(xué)及它與其他學(xué)科的關(guān)系計算機(jī)圖形學(xué)最直觀目的是將具有屬性信息的幾何模型（以圖像形式）顯示在計算機(jī)上。在CAD/計算機(jī)繪圖等應(yīng)用中，常通過圖像識別和反求工程等得到幾何模型。1.1計算機(jī)圖形學(xué)及它與其他學(xué)科的關(guān)系處理幾何模型的主要理論是計算幾何/計算機(jī)輔助幾何設(shè)計(CAGD）和計算機(jī)圖形學(xué)。計算幾何/計算機(jī)輔助幾何設(shè)計(CAGD）集中在曲線、曲面的生成和處理。而幾何造型等常被認(rèn)為是計算機(jī)圖形學(xué)的工作。1.1計算機(jī)圖形學(xué)及它與其他學(xué)科的關(guān)系處理圖像信息的主要理論是數(shù)字圖像處理。上述各種理論、方法和技術(shù)的基礎(chǔ)是數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計等1950年，第一臺圖形顯示器作為美國麻省理工學(xué)院（MIT）旋風(fēng)I號（WhirlwindI）計算機(jī)的附件誕生了。該顯示器用一個類似于示波器的陰極射線管（CRT）來顯示一些簡單的圖形。

1958年美國Calcomp公司由聯(lián)機(jī)的數(shù)字記錄儀發(fā)展成滾筒式繪圖儀，GerBer公司把數(shù)控機(jī)床發(fā)展成為平板式繪圖儀。到50年代末期，MIT的林肯實(shí)驗(yàn)室在“旋風(fēng)”計算機(jī)上開發(fā)SAGE空中防御體系，第一次使用了具有指揮和控制功能的CRT顯示器，操作者可以用筆在屏幕上指出被確定的目標(biāo)。在整個50年代，計算機(jī)圖形學(xué)處于準(zhǔn)備和醞釀時期，并稱之為：“被動式”圖形學(xué)。1.2計算機(jī)圖形學(xué)發(fā)展簡史1962年，MIT林肯實(shí)驗(yàn)室的IvanE.Sutherland發(fā)表了一篇題為“Sketchpad：一個人機(jī)交互通信的圖形系統(tǒng)”的博士論文，首次使用“ComputerGraphics”這個術(shù)語，證明了交互計算機(jī)圖形學(xué)是一個可行的有用的研究領(lǐng)域。1964年MIT的教授StevenA.Coons提出了被后人稱為超限插值的新思想，通過插值四條任意的邊界曲線來構(gòu)造曲面。同在60年代早期，法國雷諾汽車公司的工程師PierreBézier發(fā)展了一套Bézier曲線、曲面的理論，成功地用于幾何外形設(shè)計。Coons方法和Bézier方法是CAGD最早的開創(chuàng)性工作。1.2計算機(jī)圖形學(xué)發(fā)展簡史70年代是計算機(jī)圖形學(xué)發(fā)展過程中一個重要的歷史時期。光柵顯示器的產(chǎn)生，圖形學(xué)進(jìn)入了第一個興盛的時期，并開始出現(xiàn)實(shí)用的CAD圖形系統(tǒng)。1977、1979年開始，計算機(jī)圖形學(xué)標(biāo)準(zhǔn)制定：CGI(ComputerGraphicsInterface)CGM(ComputerGraphicsMetafile)GKS(GraphicsKernelsystem)PHIGS(Programmer'sHierarchicalInteractiveGraphicsStandard)等。1.2計算機(jī)圖形學(xué)發(fā)展簡史70年代，計算機(jī)圖形學(xué)另外兩個重要進(jìn)展是真實(shí)感圖形學(xué)和實(shí)體造型技術(shù)的產(chǎn)生。1970年Bouknight提出了第一個光反射模型，1971年Gourand提出“漫反射模型＋插值”的思想，被稱為Gourand明暗處理。1975年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)。1.2計算機(jī)圖形學(xué)發(fā)展簡史

1980年Whitted提出了一個光透視模型—Whitted模型，并第一次給出光線跟蹤算法的范例，實(shí)現(xiàn)Whitted模型。1984年，美國Cornell大學(xué)和日本廣島大學(xué)的學(xué)者分別將熱輻射工程中的輻射度方法引入到計算機(jī)圖形學(xué)中，用輻射度方法成功地模擬了理想漫反射表面間的多重漫反射效果。1.2計算機(jī)圖形學(xué)發(fā)展簡史光線跟蹤算法和輻射度算法的提出，標(biāo)志著真實(shí)感圖形的顯示算法已逐漸成熟。從80年代中期以來，超大規(guī)模集成電路的發(fā)展，為圖形學(xué)的飛速發(fā)展奠定了物質(zhì)基礎(chǔ)。計算機(jī)的運(yùn)算能力的提高，圖形處理速度的加快，使得圖形學(xué)的各個研究方向得到充分發(fā)展。圖形學(xué)已廣泛應(yīng)用于動畫、科學(xué)計算可視化、CAD/CAM、影視娛樂等各個領(lǐng)域。1.2計算機(jī)圖形學(xué)發(fā)展簡史最后，強(qiáng)調(diào)一下SIGGRAPH會議，“TheSpecialInterestGrouponComputerGraphicsandInteractiveTechniques”ACMSIGGRAPH會議是計算機(jī)圖形學(xué)最權(quán)威的國際會議，每年在美國召開，參加會議的人在50,000人左右。世界上沒有第二個領(lǐng)域每年召開如此規(guī)模巨大的專業(yè)會議，SIGGRAPH會議很大程度上促進(jìn)了圖形學(xué)的發(fā)展。

1974年在Colorado大學(xué)召開了第一屆SIGGRAPH年會。因?yàn)槊磕曛讳浫〈蠹s50篇論文，在ComputerGraphics雜志上發(fā)表，因此論文的學(xué)術(shù)水平較高，基本上代表了圖形學(xué)的主流方向。1.2計算機(jī)圖形學(xué)發(fā)展簡史

1.3計算機(jī)圖形學(xué)的應(yīng)用領(lǐng)域1.3.1圖形用戶接口用戶接口是人們使用計算機(jī)的第一觀感。一個友好的圖形化的用戶界面能夠大大提高軟件的易用性，在DOS時代，計算機(jī)的易用性很差，編寫一個圖形化的界面要費(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ī)的方方面面。目前幾個大的軟件公司都在研究下一代用戶界面，開發(fā)面向主流應(yīng)用的自然、高效多通道的用戶界面。研究多通道語義模型、多通道整合算法及其軟件結(jié)構(gòu)和界面范式是當(dāng)前用戶界面和接口方面研究的主流方向，而圖形學(xué)在其中起主導(dǎo)作用。人機(jī)交互技術(shù)通常是以WIMP為特征的圖形用戶界面：W（Window，窗口）：用戶可以隨意在屏幕上創(chuàng)建、移動和縮放窗口，在不同的窗口中可以執(zhí)行不同的任務(wù)。I（Icon，圖標(biāo)）：它形象化地標(biāo)示一個對象或功能。M（Menu，菜單）：提供選項(xiàng)功能，避免命令記憶之苦。P（PointingDevices，指點(diǎn)設(shè)備）：便于用戶對屏幕對象進(jìn)行直接操作。1.3.1圖形用戶接口計算機(jī)輔助設(shè)計（ComputerAidedDesign）和計算機(jī)圖形學(xué)（ComputerGraphics）是緊密聯(lián)系在一起的。國內(nèi)《計算機(jī)輔助設(shè)計和圖形學(xué)學(xué)報》國外《ComputerAidedDesign》CAD/CAM是CG在工業(yè)界最廣泛、最活躍的應(yīng)用領(lǐng)域。飛機(jī)、汽車、船舶、機(jī)電、輕工、服裝的外形設(shè)計集成電路、印刷電路板的設(shè)計建筑設(shè)計基于工程圖紙的三維形體重建

1.3.2計算機(jī)輔助設(shè)計與制造－工業(yè)領(lǐng)域CAD系統(tǒng)中的一個難點(diǎn)——參數(shù)設(shè)計問題，幾何約束滿足問題（GeometricConstraintSatisfactionProblem，GCSP）：給定一組幾何元素和一組描述幾何元素間關(guān)系的約束條件，求解這組幾何元素以滿足這組約束。GCSP的求解是智能CAD系統(tǒng)中參數(shù)化設(shè)計的核心問題，也是人工智能、軟件工程、工程設(shè)計等領(lǐng)域的研究課題。在網(wǎng)絡(luò)環(huán)境下進(jìn)行異地、異構(gòu)系統(tǒng)的協(xié)同設(shè)計，已經(jīng)成為CAD領(lǐng)域最熱門的課題之一。異地設(shè)計、異地制造、異地裝配為企業(yè)在市場競爭中贏得了寶貴的時間。1.3.2計算機(jī)輔助設(shè)計與制造－工業(yè)領(lǐng)域三維幾何造型系統(tǒng)基本上代表了CAD技術(shù)的發(fā)展方向。

CAD另一個非常重要的研究領(lǐng)域就是基于工程圖紙的三維形體重建。目前的重建算法主要是針對多面體和對主軸方向有嚴(yán)格限制的二次曲面體的。任意曲面體的三維形體重建，至今仍是一個未解決的難題。1.3.2計算機(jī)輔助設(shè)計與制造－工業(yè)領(lǐng)域（a）工程圖應(yīng)用舉例（b）線框圖

（c）實(shí)體圖

Boeing777,無紙設(shè)計，無紙制造在飛機(jī)工業(yè)中，美國波音飛機(jī)公司已用有關(guān)的CAD系統(tǒng)實(shí)現(xiàn)波音777大型客機(jī)的整體設(shè)計和模擬，其中包括飛機(jī)外型、內(nèi)部零部件的安裝和檢驗(yàn)。使其設(shè)計制造成本下降30%以上。

計算機(jī)動畫是計算機(jī)圖形學(xué)和藝術(shù)相結(jié)合的產(chǎn)物，它綜合利用計算機(jī)科學(xué)、藝術(shù)、數(shù)學(xué)、物理學(xué)和其它相關(guān)學(xué)科的知識在計算機(jī)上生成絢麗多彩的連續(xù)的虛擬真實(shí)畫面，給人們提供了一個充分展示個人想象力和藝術(shù)才能的新天地。簡單地講，計算機(jī)動畫是指用繪制程序生成一系列的景物畫面，其中當(dāng)前幀畫面是對前一幀畫面的部分修改。動畫是運(yùn)動中的藝術(shù)，正如動畫大師JohnHalas所講的，運(yùn)動是動畫的要素。計算機(jī)動畫所生成的是一個虛擬的世界，動畫師可以隨心所欲地創(chuàng)造他的虛幻世界，為我們的世界增添更多的色彩。3D射擊游戲例子1.3.3計算機(jī)動畫－商業(yè)領(lǐng)域影視制作

計算機(jī)動畫技術(shù)還被廣泛用于電影電視中的特技鏡頭的制作，產(chǎn)生以假亂真而又驚險的特技效果，如模擬大樓被炸、橋梁坍塌等。影片《珍珠港》劇照。由電腦制作出的災(zāi)難景象。1.3.3計算機(jī)動畫－商業(yè)領(lǐng)域1.3.4計算機(jī)藝術(shù)—藝術(shù)領(lǐng)域含義很廣以計算機(jī)為工具，可以完成多種藝術(shù)品的制作和設(shè)計，如繪畫（平面圖形）、雕塑（立體圖形）、音樂、平面構(gòu)成、空間結(jié)構(gòu)，還有體操舞蹈設(shè)計等等。其中，美術(shù)作品占比重最大因此，計算機(jī)藝術(shù)由主要指計算機(jī)美術(shù)計算機(jī)平面繪畫藝術(shù)計算機(jī)繪畫（ComputerPainting）主要指人們利用鼠標(biāo)或數(shù)字壓感光筆直接在屏幕或數(shù)字化板上進(jìn)行的繪畫軟件包括：CorelPainter或AdobePhotoshop等該類繪畫最接近于傳統(tǒng)繪畫，其畫風(fēng)細(xì)膩、形象生動自然。但畫幅一般較小，要求繪畫者有較高的美術(shù)功底。優(yōu)勢為：易于修改、效果豐富、成本較低、但對于電腦設(shè)備要求較高。近期廣泛應(yīng)用于手繪動畫和漫畫創(chuàng)作。1.3.4計算機(jī)藝術(shù)—藝術(shù)領(lǐng)域計算機(jī)平面合成藝術(shù)計算機(jī)數(shù)字圖像合成藝術(shù)（ComputerImageEditingandMontageArt）主要指利用電腦對掃描或數(shù)字相機(jī)導(dǎo)入的圖像素材進(jìn)行編輯和合成，以及進(jìn)行后期特技處理所產(chǎn)生的新視覺作品軟件包括：CorelPainter或AdobePhotoshop等。該類作品接近于傳統(tǒng)攝影特技，并帶有“蒙太奇藝術(shù)”的特點(diǎn)，許多合成圖像帶有荒誕、刺激、搞笑、離奇和超現(xiàn)實(shí)主義風(fēng)格的效果。優(yōu)勢為：易于掌握和普及、效果豐富、成本較低。廣泛應(yīng)用于影視后期和多媒體創(chuàng)作。和應(yīng)用美術(shù)及廣告設(shè)計的關(guān)系十分密切。1.3.4計算機(jī)藝術(shù)—藝術(shù)領(lǐng)域可用于美術(shù)創(chuàng)作的軟件很多，如二維平面的畫筆程序(如CorelDraw，Photoshop，PaintShop)專門的圖表繪制軟件(如Visio)、三維建模和渲染軟件包(如3DMAX，Maya)、以及一些專門生成動畫的軟件(如Alias，SoftImage)等。這些軟件不僅提供多種風(fēng)格的畫筆、畫刷，而且提供多種多樣的紋理貼圖，甚至能對圖像進(jìn)行霧化/變形等操作。很多功能是一個傳統(tǒng)的藝術(shù)家無法實(shí)現(xiàn)也不可想象的。當(dāng)然，傳統(tǒng)藝術(shù)的一些效果也是上述軟件所不能達(dá)到的。例如鋼筆素描的效果，由于鋼筆素描與傳統(tǒng)的圖形學(xué)繪制方法差別很大，所以研究起來難度也頗大，很多學(xué)者已在這方面做了卓有成效的工作，取得了一定的成果。1.3.4計算機(jī)藝術(shù)—藝術(shù)領(lǐng)域1.3.5非真實(shí)感繪制(NPRNon-PhotorealisticRendering

)非真實(shí)感圖形比真實(shí)感圖形應(yīng)用更廣泛，如文學(xué)讀物插圖，其中兒童讀物插圖量最大；用數(shù)字方法對傳統(tǒng)繪畫進(jìn)行模擬以掌握其規(guī)律性的東西；傳統(tǒng)動畫都是非真實(shí)感的，現(xiàn)在需要用計算機(jī)技術(shù)再現(xiàn)它們鋼筆畫效果鋼筆素描產(chǎn)生于中世紀(jì)，從19世紀(jì)開始成為一門藝術(shù)，然而用計算機(jī)模擬鋼筆繪畫卻是20世紀(jì)90年代的事情。

鉛筆畫效果油畫效果水彩畫效果基于圖像的NPR

石油化工、金屬冶煉、電網(wǎng)控制的工作人員根據(jù)設(shè)備關(guān)鍵部位的傳感器送來得圖像和數(shù)據(jù)，對設(shè)備運(yùn)行過程進(jìn)行監(jiān)控機(jī)場、鐵路的調(diào)度人員通過計算機(jī)產(chǎn)生運(yùn)行狀態(tài)信息來調(diào)整空中交通和鐵路運(yùn)輸1.3.6過程控制飛行模擬艙——用光柵掃描器產(chǎn)生駕駛員在駕駛艙中預(yù)期所能看到的景象，對飛行員進(jìn)行單飛前的地面訓(xùn)練和飛機(jī)格斗訓(xùn)練等1.3.7系統(tǒng)環(huán)境模擬

繪制表示經(jīng)濟(jì)信息的各類二、三維統(tǒng)計管理圖表信息可視化:信息流量，商業(yè)統(tǒng)計數(shù)據(jù)，股市行情1.3.8事務(wù)和商務(wù)數(shù)據(jù)圖形顯示

地理信息系統(tǒng)（GIS）數(shù)字地球，地形數(shù)據(jù)作為載體，（70％）全球信息化.軍事，政府決策，旅游，資源調(diào)查。地理圖、地形圖、礦藏分布圖、氣象氣流圖、植物分布圖1.3.9地形地貌和自然資源的圖形顯示

不同于可視化計算科學(xué)計算可視化是將科學(xué)計算過程中的數(shù)據(jù)及結(jié)果數(shù)據(jù)轉(zhuǎn)換為圖像實(shí)際上也包括了工程計算可視化和測量數(shù)據(jù)可視化其核心是三維數(shù)據(jù)場的可視化。可應(yīng)用于氣象預(yù)報、（CT）醫(yī)學(xué)圖象重建、流場、湍流、激波、石油地質(zhì)勘探、環(huán)境保護(hù)、核爆炸模擬、計算流體力學(xué)、天體物理、分子生物學(xué)、有限元分析、等許多領(lǐng)域。1.3.10科學(xué)計算可視化

將醫(yī)用CT掃描的數(shù)據(jù)轉(zhuǎn)化為三維圖象，并通過一定的技術(shù)生成在人體內(nèi)漫游的圖象，使得醫(yī)生能夠看到并準(zhǔn)確地判別病人的體內(nèi)的患處，然后通過碰撞檢測一類的技術(shù)實(shí)現(xiàn)手術(shù)效果的反饋，幫助醫(yī)生成功完成手術(shù)。

臺灣pcexpert公司研制的LSVR系統(tǒng)逼真地模擬了腹腔手術(shù)，進(jìn)行過程教學(xué)、手術(shù)成果檢驗(yàn)等

1.3.11虛擬手術(shù)仿真CAI，教學(xué)娛樂。在計算機(jī)控制下，對多種媒體信息進(jìn)行生成、操作、表現(xiàn)、存儲、通信、或集成的信息系統(tǒng)計算機(jī)處理的常見媒體：文本、圖形、圖像、語音、音頻、視頻、動畫特點(diǎn)：媒體的多樣性、操作的交互性、系統(tǒng)的集成性1.3.11多媒體應(yīng)用1.4計算機(jī)圖形學(xué)研究的基本問題

圖形描述

基本幾何：直線、圓弧等；高級幾何：曲線、曲面等圖形變換二、三維變換、三維到二維、觀察流程、幾何變換等圖形運(yùn)算基本幾何間的計算、裁剪、布爾運(yùn)算等圖形顯示/輸出基本圖形生成算法、消隱、繪圖、光照模型等圖形輸入交互技術(shù)、參數(shù)化設(shè)計、造型技術(shù)等算法和算法復(fù)雜性分析空間和時間等1.4.1圖形描述一個物體的計算機(jī)描述叫做模型，它能被計算機(jī)所懂得，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在顯示屏幕或繪圖機(jī)上輸出；而圖形是模型的一個具體可見像，是人們所看到的模型的表征。不能把兩者混為一談。在三維空間，描述的是幾何形體和幾何曲面，只有在平面上，它才是人們通常所稱的圖形。幾何形體以封閉的表面表示，一般為一個由平面和曲面圍成的多面體。一個幾何形體在空間上應(yīng)是完備的(幾何性和拓?fù)湫?，而且包含足夠的用于推導(dǎo)的任何空間函數(shù)(如直線方程、平面方程、曲面構(gòu)造等)以及進(jìn)行各種形體運(yùn)算與處理的信息。在多面體表示中，有關(guān)的基本元素（體、面、環(huán)棱和頂點(diǎn)）的信息分為二大類：幾何信息：用以確定每個分量在歐氏空間中的幾何位置(如點(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)孔。一個完全的三維幾何體描述，幾何信息和拓?fù)湫畔烧叨际潜匾摹?.4.1圖形描述1.4.1圖形描述描述一個多面體各元素之間的拓?fù)潢P(guān)系可以互相推導(dǎo)。故理論上只需存儲一種關(guān)系就行了，但由于關(guān)系的推導(dǎo)要付出代價，所以一般的系統(tǒng)常同時存儲若于種拓?fù)潢P(guān)系。這些拓?fù)潢P(guān)系，既要足夠地表示出幾何形體的構(gòu)造，又要盡量壓縮信息的存儲量，且要便于檢索和修改，而十分重要的是要便于計算機(jī)的自動生成。對于曲表面的幾何形體，需分別研究自由曲線和自由曲面的建立；用于插值和數(shù)學(xué)放樣的三次樣條函數(shù)是應(yīng)用得最早研究得最詳盡的一種。1.4.1圖形描述Bezier曲線和曲面與B樣條曲線和曲面是在計算機(jī)輔助幾何設(shè)計應(yīng)用最廣的曲線和曲面幾何構(gòu)型方法。關(guān)于這些方面的研究，至今仍在繼續(xù)發(fā)展中。平面上圖形的描述是基于直線和圓弧的描述。僅用這兩種基本幾何元素就可構(gòu)成平面上的任何圖形。因而直線段和圓弧段也叫基本幾何段，本教程將詳加闡述。數(shù)據(jù)結(jié)構(gòu)技術(shù)在圖形描述中起著關(guān)鍵的作用。線性鏈接表、樹結(jié)構(gòu)、堆棧、隊列等將廣泛應(yīng)用于幾何模型的描述、運(yùn)算和顯示中。1.4.2圖形輸入圖形輸入需要解決的問題是：交互輸入的方法。工程設(shè)計圖紙直接輸入（矢量識別）的方法。將自由手書的立體構(gòu)造或三視圖重構(gòu)的方法。計算機(jī)自動生成方法。從物體的多幅深度圖像重建三維幾何模型。通過三維激光掃描儀在物體表面測得一些離散點(diǎn)，再用重構(gòu)算法生成網(wǎng)格模型等等。圖形輸入的常規(guī)方法是將事先寫好的源程序(指令)在屏幕上輸入，即所謂的編程輸入，使得人、機(jī)之間的交互作用緩慢。對于工程上常用的一類規(guī)格化圖形，可以編制一個通用程序，采用格式數(shù)據(jù)輸入的辦法得到圖形。但是在處理三維的，或是形狀復(fù)雜的物體時還有較多的困難，輸入數(shù)據(jù)太多就是一個障礙。1.4.2圖形輸入除了這種圖形的直接輸入之外，通過對基本體元的構(gòu)型產(chǎn)生新的、復(fù)雜的三維物體也是一種輸入的手段，當(dāng)然這需要涉及更多的研究。從計算機(jī)圖形學(xué)的發(fā)展情況看，對圖形輸出的研究多于對圖形輸入的研究，許多人往往被計算機(jī)輸出的美妙圖形所迷惑，卻看不到為得到這些圖形所做的大量數(shù)據(jù)輸入的準(zhǔn)備工作。圖形輸入的工作量和難度并不亞于幾何算法和圖形輸出。

隨著時間的推移，圖形輸入將越來越成為計算圖形學(xué)應(yīng)用中的主要障礙。1.4.2圖形輸入1.4.3圖形變換一個圖形系統(tǒng)需具有圖形變換的功能。這種變換包括二維變換、三維變換和三維向二維的變換三種。對應(yīng)于幾何元素及其選定的坐標(biāo)系來說，則包括幾何變換和坐標(biāo)系變換兩種。這些變換系統(tǒng)稱為圖形變換。在構(gòu)造、產(chǎn)生、處理和輸出圖形的各個環(huán)節(jié)，圖形變換起著重要的作用。人們可以直接定義一個幾何圖形或幾何體，也可通過對某些幾何體的變換去構(gòu)造新的幾何體或其中的某個部份。這種變換可以是平移、放大(縮小)、旋轉(zhuǎn)、反射、錯切等。一個三維場景通常就是由一些基本幾何元素通過上述操作構(gòu)造的。例如，可以通過平移的辦法裝配一幢建筑物的大部份窗子，這使得圖形輸入大為簡化。在進(jìn)行圖形處理的過程中，還可以放大一個圖形以便使其某一部份能更清楚地顯示；縮小圖形以便看到圖形更多的部份。1.4.3圖形變換在顯示或繪制一個環(huán)境的時候，需要將三維信息映射到二維屏幕上。軸測投影、平行投影和透視投影用于完成這項(xiàng)工作。在視點(diǎn)改變得非常快或物體相對運(yùn)動的應(yīng)用場合，變換必須反復(fù)運(yùn)用。因此，找到一個有效的方法去實(shí)現(xiàn)圖形變換是十分重要的。采用向量、矩陣和齊次坐標(biāo)的形式去描述圖形變換是一種比較好的辦法，它允許將線性代數(shù)的一些基本理論應(yīng)用到圖形變換中。例如一個矩陣對應(yīng)于一個變換，圖形的連續(xù)變換可由矩陣的相乘實(shí)現(xiàn)，而逆矩陣對應(yīng)于一個逆變換。所有的變換都基于點(diǎn)變換，例如對一條線段的變換只需考慮其兩個端點(diǎn)的變換就可以了?；編缀卧孛枋龅淖儞Q也和點(diǎn)的變換有密切的聯(lián)系。例如描述一條直線的方程系數(shù)在不同坐標(biāo)下的關(guān)系也可由點(diǎn)變換的相應(yīng)變換矩陣求得。1.4.4圖形運(yùn)算在三維空間，圖形的運(yùn)算是一種幾何形體的運(yùn)算，它是CAGD的一個重要操作，這種操作通常叫做物體造型，或幾何造型。設(shè)計人員可通過修改立方體，圓柱體之類的基本體元來生成形體。例如通過縮放，通過用集合論中的并、交、非、差等概念所進(jìn)行的各種布爾運(yùn)算把一些基本物體體元組合起來。設(shè)計人員的職責(zé)是把各體元正確地定位下來，使得這些運(yùn)算能進(jìn)行下去。另一方面幾何造型系統(tǒng)還負(fù)責(zé)估計各體元之間的相互作用，各種相交出現(xiàn)的位置以及它們之間的相互關(guān)系，以確保生成法定的三維形體。系統(tǒng)還必須正確地、在計算機(jī)限制下內(nèi)盡可能精確地完成相交分析。幾何造型系統(tǒng)常處理一些比較簡單的體元：立方體、圓柱體、楔、嵌條，以直線或圓弧為邊界的薄片等。所涉及的線和面在幾何上是簡單的直線、圓弧、平面和圓柱面，處理這些由一個正確的方式構(gòu)造出來的物體的相交，從概念上是比較容易的。但主要困難在于：雖然幾何簡單，但多個元素的拼合卻是復(fù)雜的。故對于確實(shí)復(fù)雜的形體的組合問題，所需的幾何算法的效率就變得十分重要，需進(jìn)行幾何復(fù)雜性分析。1.4.4圖形運(yùn)算1.4.4圖形運(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ī)圖形系統(tǒng)一項(xiàng)基礎(chǔ)性的工作。1.4.4圖形輸出圖形輸出是人—機(jī)交互系統(tǒng)中人們能夠得到的最直觀的結(jié)果。它直接向人們顯示出計算機(jī)圖形系統(tǒng)的效果。相對而言，圖形輸出計算機(jī)圖學(xué)中研究得最早、最深入、解決得最好的一部份工作。一個物體的制造者可以從一張多視圖的圖樣里了解到許多內(nèi)容。因此，一個能在二維參考平面里提供綜合的，繪制直線和曲線的系統(tǒng)也就提供了畫出一個復(fù)雜而詳細(xì)的圖形或物體的基礎(chǔ)。但是，圖形只是三維物體的某一個特定的不完整的表示。而物體有一種圖里沒有的，與眾不同的特性——完全的三維定義。人們可以隨意地在三維空間中把物體旋轉(zhuǎn)和平移以及物體的綜合，但一般不能用圖形做到這一點(diǎn)。基本幾何（點(diǎn)、直線、圓及圓弧等）和文字的光柵化顯示，幾何裁剪算法。基本幾何的描述、相交算法，曲線擬合和雙圓弧逼近算法，動態(tài)顯示的插值算法。圖形顯示中的裁剪算法，通常稱為窗口算法；隱藏線、隱藏面消除算法。光照模型及算法。

紋理貼圖；

大規(guī)模場景顯示算法；圖形顯示軟件和打印機(jī)、繪圖機(jī)等的圖形輸出后處理軟件等等。1.4.4圖形輸出1.4.6幾何算法、幾何復(fù)雜性和計算效率一個動畫程序，一個游戲程序，用戶的起碼要求是“流暢”。支撐它的是幾何算法，幾何復(fù)雜性問題及計算的效率。許多通過交互設(shè)計各種形體的系統(tǒng)，其成功的主要斷依據(jù)是憑視覺。例如套料問題，這在造船、服裝等行業(yè)是極為有用的，然而至今存在的系統(tǒng)還是由人機(jī)交互作用來完成。而幾何造型系統(tǒng)在相交問題的正確算法和處理組合比較復(fù)雜問題的能力，這種系統(tǒng)的發(fā)展表明，需要多多研究幾何算法。1.4.6幾何算法、幾何復(fù)雜性和計算效率幾何相交問題在幾何算法中占有較大的比重，在平面上，它處理直線和直線，圓弧和直線，圓弧和圓弧等基本幾何的相交，在三維空間則是處理直線和平面，平面和平面的相互關(guān)系。但是，并不是所有的處理直線和直線的相交都是簡易的。例如，考慮兩個平面多邊形相交的狀態(tài)，按照Shamos(1978)算法，如果這兩個多邊形是凸的，對于n條邊的多邊形可以用O(n)的時間解決這個問題。而對于兩個任意非凸多邊形，為解決這個問題要花O(n2)的時間，可能形成達(dá)n2/4個不相疊的凸多邊形。觀察一個時間復(fù)雜性的例子：問題：設(shè)給定n個已經(jīng)排序的數(shù)的隊列，現(xiàn)在要插入一個新的數(shù)到這個隊列中，并保持隊列原有的次序，幾何復(fù)雜性為O(n)次主算。應(yīng)用二分法，可降為O(log2n)次。如果不計檢索到元素后對其處理所花費(fèi)的計算時間，而只對n的步數(shù)計算時間，那末當(dāng)n=60時：n：6×10-5秒n2：36×10-4秒

n3：216×10-3秒n5：13分鐘2n：366世紀(jì)3n：1.3×1013世紀(jì)1.4.6幾何算法、幾何復(fù)雜性和計算效率降低幾何復(fù)雜性是幾何算法的一個努力目標(biāo)，它可以提高算法的效率。過去開發(fā)僅僅能“工作”的算法就常常足夠了，即使在某些情況下效率低也無妨。隨著使用計算機(jī)進(jìn)行幾何設(shè)計的增加，以及要解決問題的范圍之?dāng)U大，效率、精度和正確性的問題就變得非常重要了。1.4.6幾何算法、幾何復(fù)雜性和計算效率1.5計算機(jī)圖形學(xué)的相關(guān)開發(fā)技術(shù)計算機(jī)圖形學(xué)經(jīng)過幾十年的發(fā)展，已經(jīng)達(dá)到了比較高的水平，目前已有若干圖形學(xué)軟件開發(fā)技術(shù)。利用這些開發(fā)技術(shù)，編寫圖形程序就容易多了，不必從底層開始，而只需將精力集中到圖形程序本身上。1.5.1OpenGLOpenGL：OpenGL是OpenGraphicsLib的縮寫，是一套三維圖形處理庫，也是該領(lǐng)域的工業(yè)標(biāo)準(zhǔn)。OpenGL源于SGI公司為其圖形工作站開發(fā)的IRISGL，在跨平臺移植過程中發(fā)展成為OpenGL。OpenGL被設(shè)計成獨(dú)立于硬件，獨(dú)立于窗口系統(tǒng)的，在運(yùn)行各種操作系統(tǒng)的各種計算機(jī)上都可用，并能在網(wǎng)絡(luò)環(huán)境下以客戶/服務(wù)器模式工作，是專業(yè)圖形處理、科學(xué)計算等高端應(yīng)用領(lǐng)域的標(biāo)準(zhǔn)圖形庫。1.5.1OpenGLMicrosoft、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í)際上是一個開放的三維圖形軟件包，它獨(dú)立于窗口系統(tǒng)和操作系統(tǒng)，以它為基礎(chǔ)開發(fā)的應(yīng)用程序可以十分方便地在各種平臺間移植；OpenGL與C++緊密接合，便于實(shí)現(xiàn)圖形的相關(guān)算法，并可保證算法的正確性和可靠性；OpenGL使用簡便，效率高。1.5.2ACISACIS是美國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)造一個面向終端用戶的2/3維軟件系統(tǒng)。ACIS是一個基于邊界表示法的造型引擎，集線框曲面和實(shí)體造型于一體，并允許這三種表示共存于統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)中。ACIS系統(tǒng)的造型方法有：覆蓋技術(shù)(covering)：覆蓋一個由曲線組成的閉合區(qū)域的曲面放樣技術(shù)(lofting)：通過一系列的曲線和與這些曲線相關(guān)聯(lián)的曲面來構(gòu)造新曲面的一種技術(shù)蒙面技術(shù)(skinning)：在一系列曲線之間構(gòu)造一個曲面1.5.2ACIS網(wǎng)格曲面(netsurfaces)：用一族曲線網(wǎng)來定義曲面的u和v參數(shù)方向，這為控制最終的曲面形狀提供了很大的自由度規(guī)則(law)和圖(graph)：提供規(guī)則類，直接用數(shù)學(xué)方程定義實(shí)體中的邊和面掃掠(sweeping)：通過掃描一個輪廓(profile)來生成實(shí)體（solidbody）或者薄片體(sheetbody)。ACIS有三種不同的掃掠操作：規(guī)則掃掠、垂直掃掠以及剛性掃掠1.5.2ACIS1.5.3DirectXDirectX是一種圖形應(yīng)用程序接口（API），它是一個提高系統(tǒng)性能的加速軟件，由微軟公司創(chuàng)建開發(fā)，微軟將其定義為“硬件設(shè)備無關(guān)性”。

DirectX就是一系列的DLL(DynamicLinkLib)，通過這些DLL，程序員可以在無視于設(shè)備差異的情況下訪問底層的硬件。

DirectX并不是一個單純的圖形API，它是一個用途廣泛的API，它包含有DirectGraphics(Direct3D+DirectDraw)、DirectInput、DirectPlay、DirectSound、DirectShow、DirectSetup和DirectMediaObjects等多個組件，它提供了一整套的多媒體接口方案。1.5.3DirectXDirectX主要應(yīng)用于游戲軟件的開發(fā)。微軟公司給眾多的軟、硬件商家提供一個共同開發(fā)的標(biāo)準(zhǔn)平臺(就是DirectX)，大家都遵循這個標(biāo)準(zhǔn)，硬件制造商按照此標(biāo)準(zhǔn)研發(fā)制造更好的產(chǎn)品，游戲程序員根據(jù)這套標(biāo)準(zhǔn)開發(fā)游戲。無論硬件是否支持某特殊效果，只要DirectX標(biāo)準(zhǔn)中有，程序員就可以把它寫到游戲中，當(dāng)這個游戲在硬件上運(yùn)行，如果此硬件根據(jù)DirectX標(biāo)準(zhǔn)把這個效果做到了此硬件驅(qū)動程序中，驅(qū)動程序駕馭其硬件算出此效果，用戶就可以欣賞到此效果。1.5.4Java3DJava3DAPI是Sun定義的用于實(shí)現(xiàn)3D