游戲開發小組內部資料

20051029

計算機圖形學講義

Equinox_D制作PDF

版權歸原文作者所有

第一章緒論

計算機圖形學是利用計算機研究圖形的表示、生成、處理、顯示的學

科。經過30多年的發展，計算機圖形學已成為計算機科學中，最為活躍的分

支之一，并得到廣泛的應用。本章將介紹計算機圖形學的研究內容、發展歷

史、應用和圖形學前沿的發展方向，同時介紹一些圖形硬件的基本原理，使

讀者對圖形學的有關內容有個概括性的了解。

L1計算機圖形學的研究內容

如何在計算機中表示圖形、以及利用計算機進行圖形的計算、處理和顯

示的相關原理與算法，構成了計算機圖形學的主要研究內容。圖形通常由

點、線、面-、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。

從處理技術上來看，圖形主要分為兩類，一類是基于線條信息表示的，如工

程圖、等高線地圖、曲面的線框圖等，另一類是明暗圖(Shanding),也就是

通常所說的真實感圖形。

可以說，計算機圖形學一個主要的目的就是要利用計算機產生令人賞心

悅目的真實感圖形。為此，必須建立圖形所描述的場景的幾何表示，再用某

種光照模型，計算在假想的光源、紋理、材質屬性下的光照明效果。所以計

算機圖形學與另一門學科計算機輔助幾何設計有著密切的關系。事實上，圖

形學也把可以表示幾何場景的曲線曲面造型技術和實體造型技術作為其主要

的研究內容。同時，真實感圖形計算的結果是以數字圖象的方式提供的，計

算機圖形學也就和圖象處理有著密切的關系。圖形與圖象兩個概念間的區別

越來越模糊，但我們認為還是有區別的；圖象純指計算機內以位圖出血叩)

形式存在的灰度信息，而圖形含有兒何屬性，或者說更強調場景的兒何表示,

是由場景的幾何模型和景物的物理屬性共同組成的。

計算機圖形學的研究內容非常廣泛，如圖形硬件、圖形標準、圖形交互

技術、光柵圖形生成算法、曲線曲面造型、實體造型、真實感圖形計算與顯

示算法，以及科學計算可視化、計算機動畫、自然景物仿真、虛擬現實等。

作為一本面向計算機專業本科生和非計算機專業研究生的圖形學教材，本書

著重討論與光柵圖形生成、曲線曲面造型和真實感圖形生成相關的原理與算

法。

1.2計算機圖形學的發展簡史

1950年，第一臺圖形顯示器作為美國麻省理工學院(MIT)旋風I號值hirl-

』indD計算機的附件誕生了。該顯示器用一個類似于示波器的陰極射線管

(CRT)來顯示一些簡單的圖形。1958年美國Cakomp公司由聯機的數字記錄

儀發展成滾筒式繪圖儀，GerBer公司把數控機床發展成為平板式繪圖儀。在

整個50年代，只有電子管計算機，用機器語言編程，主要應用于科學計算，

為這些計算機配置的圖形設備僅具有輸出功能。計算機圖形學處于準備和醞

釀時期，并稱之為：“被動式”圖形學。到50年代末期，MIT的林肯實驗室

在“旋風”計算機上開發SAGE空中防御體系，第一次使用了具有指揮和控制

功能的CRT顯示器，操作者可以用筆在屏幕上指出被確定的目標。與此同時，

類似的技術在設計和生產過程中也陸續得到了應用，它預示著交互式計算機

圖形學的誕生。

1962年，MIT林肯實驗室的1\冏1￡.511丘麗(3發表了一篇題為“Sketr

phpad：一個人機交互通信的圖形系統”的博士論文，他在論文中首次使用

了計算機圖形學“ComputerGraphics”這個術語，證明了交互計算機圖形學

是一個可行的、有用的研究領域，從而確定了計算機圖形學作為一個嶄新的

科學分支的獨立地位。他在論文中所提出的一些基本概念和技術，如交互技

術、分層存儲符號的數據結構等至今還在廣為應用。1964年MIT的教授Steven

A.C00n遍出了被后人稱為超限插值的新思想，通過插值四條任意的邊界曲

線來構造曲面。同在60年代早期，法國雷諾汽車公司的工程師PierreBCzfer

發展了一套被后人稱為B6zier曲線、曲面的理論，成功地用于幾何外形設計，

并開發了用于汽車外形設計的UN3SURF系統。Coons方法和B6zLr方法是CAGD

最早的開創性工作。值得一提的是，計算機圖形學的最高獎是以CoonsW名

字命名的，而獲得第一屆(1983)和第二屆(1985)StevenA.Coon毀的，

恰好是IvanE.Sutherland和PieneBCzier,這也算是計算機圖形學的一段

佳話。

70年代是計算機圖形學發展過程中一個重要的歷史時期。由于光柵顯示

器的產生，在60年代就已萌芽的光柵圖形學算法，迅速發展起來，區域填充、

裁剪、消隱等基本圖形概念、及其相應算法紛紛誕生，圖形學進入了第一個

興盛的時期，并開始出現實用的CAD圖形系統。又因為通用、與設備無關的

圖形軟件的發展，圖形軟件功能的標準化問題被提了出來。1974年，美國國

家標準化局(ANSI)在ACMSKGRAPH的一個與“與機器無關的圖形技術”的

工作會議上，提出了制定有關標準的基本規則。此后ACM專門成立了一個圖

形標準化委員會，開始制定有關標準。該委員會于1977、1979年先后制定和

修改了"核心圖形系統"(CoreGlaphicsSystem)。ISO隨后又發布了計算

機圖形接口CGI(ComputerGraphicsInterlace)＞計算機圖形元文件標準CGM

(ComputerGraphi;sMetafile)、計算機圖形核心系統GKS(Graphicsmel

system)、面向程序員的層次交互圖形標準PHIGSprogrammer'sKellieiar-

-chicalirteractiveGraphicsStandarti)等。這些標準的制定，為計算機

圖形學的推廣、應用、資源信息共享，起了重要作用。

70年代，計算機圖形學另外兩個重要進展是真實感圖形學和實體造型技

術的產生。1970年Bouknigh嘿出了第一個光反射模型，1971年Gourand提出

“漫反射模型+插值”的思想，被稱為Gouiand明暗處理。1975年Phong提出

了著名的簡單光照模型-Phong模型。這些可以算是真實感圖形學最早的開

創性工作。另外，從1973年開始，相繼出現了英國劍橋大學CAD小組的BuiM

系統、美國羅徹斯特大學的PADLT系統等實體造型系統。

1980年Whitted提出了一^^光透視模型7hitted模型，并第一次給出光

線跟蹤算法的范例，實現Whitted模型；1984年，美國Come妖學和日本廣

島大學的學者分別將熱輻射工程中的輻射度方法引入到計算機圖形學中，用

輻射度方法成功地模擬了理想漫反射表面間的多重漫反射效果；光線跟蹤算

法和輻射度算法的提出，標志著真實感圖形的顯示算法已逐漸成熟。從80年

代中期以來，超大規模集成電路的發展，為圖形學的飛速發展奠定了物質基

礎。計算機的運算能力的提高，圖形處理速度的加快，使得圖形學的各個研

究方向得到充分發展，圖形學已廣泛應用于動畫、科學計算可視化、CAD/

CAM、影視娛樂等各個領域。

最后，我們以SIGGRAPH會議的情況，來結束計算機圖形學的歷史回顧。

ACMSIGGRAPH會議是計算機圖形學最權威的國際會議，每年在美國召開，參

加會議的人在50,000人左右。SIGGRAPH會議很大程度上促進了圖形學的發展，

世界上不會有第二個領域會每年召開如此規模巨大的專業會議。SIGGRAPH是

大約60年代中期，由Brown大學的教授AndrfesvanDam(Andy)和］BM公司

的SamMatsa發起的。全稱是''theSpeciallnteiestGn)uponComputer

GraphicsandIniBractiveTechniques“。1974年，在Colorado大學召開

了第一屆SIGGRAPH年會，并取得了巨大的成功，當時有大約600位來自世界

各地的專家參加了會議。到了1997年，參加會議的人數已經增加到48,700。

因為每年只錄取大約50篇論文，在ComputerGraphic磔志上發表，因此論

文的學術水平較高，基本上代表了圖形學已經的主流方向。

1.3應用及研究前沿

1.計算機輔助設計與制造

CAD《AM是計算機圖形學在工業界最廣泛、最活躍的應用領域。計算機

圖形學被用來進行土建工程、機械結構和產品的設計，包括設計飛機、汽車、

船舶的外形和發電廠、化工廠等的布局以及電子線路、電子器件等。有時，

著眼于產生工程和產品相應結構的精確圖形，然而更常用的是對所設計的系

統、產品和工程的相關圖形進行人-機交互設計和修改，經過反復的迭代設

計，便可利用結果數據輸出零件表、材料單、加工流程和工藝卡，或者數據

加工代碼的指令。在電子工業中，計算機圖形學應用到集成電路、印刷電路

板、電子線路和網絡分析等方面的優勢是十分明顯的。一個復雜的大規模或

超大規模集成電路版圖根本不可能用手工設計和繪制，用計算機圖形系統不

僅能進行設計和畫圖，而且可以在較短的時間內完成，把其結果直接送至后

續工藝進行加工處理。在飛機工業中，美國波音飛機公司已用有關的CAD系統

實現波音777飛機的整體設計和模擬，其中包括飛機外型、內部零部件的安裝

和檢驗。

隨著計算機網絡的發展，在網絡環境下進行異地異構系統的協同設計，

已經成為CAD領域最熱門的課題之一。現代產品設計已不再是一個設計領域

內孤立的技術問題，而是綜合了產品各個相關領域、相關過程、相關技術資

源和相關組織形式的系統化工程。它要求設計團隊在合理的組織結構下，采

用群體工作方式來協調和綜合設計者的專長，并且從設計一開始就考慮產品

生命周期的全部因素，從而達到快速響應市場需求的目的，協同設計的出現

使企業生產的時空觀發生了根本的變化。異地設計、異地制造、異地裝配成

為可能，從而為企業在市場競爭中贏得了寶貴的時間。

CAD領域另一個非常重要的研究領域是基于工程圖紙的三維形體重建。

三維形體重建就是從二維信息中提取三維信息，通過對這些信息進行分類、

綜合等一系列處理，在三維空間中重新構造出二維信息所對應的三維形體，

恢復形體的點、線、面及其拓撲關系，從而實現形體的重建。二維圖紙設計

在在工程界中仍占有主導地位，工程上有大量的舊的透視圖和投影圖片可以

利用、借鑒，許多新的設計可憑借原有的設計基礎做修改即可完成。同時三

維兒何造型系統，因為可以做裝配件的干涉檢查、以及有限元分析、仿真、

加工等后續操作，代表CAD技術的發展方向。目前主要的三維形體重建算法是

針對多面體和對主軸方向有嚴格限制的二次曲面體的。任意曲面體的三維形

體重建，至今仍是一個未解決的世界難題。

(a)工程圖

(b)線框圖

(c)實體圖

CAutomaticReconstructionSystem可x

的FFileEditViewInsertToolsWindowHelp?|X

Engineeringdrawings

Ready332.8572.32,18

(a)工程圖

Ready100.0015.76,刁14

(b)線框圖

(c)實體圖

圖1.3.1兩個三維重建的例子

2.可視化

科學技術的迅猛發展，數據量的與日俱增使得人們對數據的分析和處理

變得越來越難，人們無法從數據海洋中得到最有用的數據，找到數據的變化

規律，提取最本質的特征。但是如果能將這些數據用圖形的形式表示出來，

情況就不一樣了，事物的發展趨勢和本質特征將會很清楚地呈現在人們面前。

1986年，美國科學基金會(NSF)專門召開了一次研討會，會上提出了“科

學計算可視化(VisualizationinScientificComputing)”。第二年，

美國計算機成像專業委員會向NSF提交了“科學計算可視化的研究報告”后，

VISC就迅速發展起來了。

目前科學計算可視化廣泛應用于醫學、流體力學、有限元分析、氣象分

析當中。尤其在醫學領域，可視化有著廣闊的發展前途。依靠精密機械做腦

部手術已經由機械人和醫學專家配合做遠程手術是目前醫學上很熱門的課題,

而這些技術的實現的基礎則是可視化。可視化技術將醫用CT掃描的數據轉化

為三維圖象，并通過一定的技術生成在人體內漫游的圖象，使得醫生能夠看

到并準確地判別病人的體內的患處，然后通過碰撞檢測一類的技術實現手術

效果的反饋，幫助醫生成功完成手術。從目前的研究狀況來看,這項技術還

遠未成熟，離實用還有一定的距離。主要難點在于生成人體內漫游圖象的三

維體繪制技術還沒有達到實時的程度，而且現在大多的體繪制技術是基于平

行投影的，而漫游則需要真實感更強的透視投影技術，然而體繪制的透視投

影技術到還沒有很好地解決。另外在漫游當中還要根據CT圖象區分出不同的

體內組織，這項技術叫Segmentatbn。目前的Segmentatbn主要是靠人機交

互來完成，遠未達到自動實時的地步。

3.圖形實時繪制與自然景物仿真

在計算機中重現真實世界的場景叫做真實感繪制。真實感繪制的主要任

務是模擬真實物體的物理屬性，簡單的說就是物體的形狀、光學性質、表

面的紋理和粗糙程度，以及物體間的相對位置、遮擋關系等等。這其中光照

和表面屬性是最難模擬的。為了模擬光照，已有各種各樣的光照模型。從簡

單到復雜排列分別是：簡單光照模型、局部光照模型和整體光照模型。從繪

制方法上看有模擬光的實際傳播過程的光線跟蹤法，也有模擬能量交換的輻

射度方法。除了建造計算機可實現的逼真物理模型外，真實感繪制還有一個

研究重點是研究加速算法，力求能在最短時間內繪制出最真實的場景。例如

求交算法的加速、光線跟蹤的加速等等，象包圍體樹、自適應八叉樹都是著

名的加速算法。實時的真實感繪制已經成為當前真實感繪制的研究熱點，而

當前真實感圖形實時繪制的兩個熱點問題則是物體網格模型的面片簡化和基

于圖象的繪制(1BR向ageBasedRendering)。網格模型的面片簡化，就

是指對網格面片表示的模型，在一定誤差的精度范圍內，刪除點、邊、面，

從而簡化所繪制場景的復雜層度，加快圖形繪制速度。RR完全摒棄傳統的

先建模，然后確定光源的繪制的方法。它直接從一系列已知的圖象中生成未

知視角的圖象。這種方法省去了建立場景的幾何模型和光照模型的過程，也

不用進行如光線跟蹤等極費時的計算。該方法尤其適用于野外極其復雜場景

的生成和漫游。

另外，真實感繪制已經從最初繪制簡單的室內場景發展到現在大量模擬

野外自然景物，比如繪制山、水、云、樹、火等等。人們提出了多種方法來

繪制這些自然景物，比如繪制火和草的粒子系統(PartxfeSystem),基于

生理模型的繪制植物的方法，繪制云的細胞自動機方法等。也出現了一些自

然景物仿真繪制的綜合平臺，如德國Lintemann和Deussen的繪制植物的平

臺Xfing,以及清華大學自主開發的自然景物設計平臺。

圖L3.2由清華大學自然景物平臺生成的野外場景

圖1.3.3日本YodiinoriDobadi爵人繪制的真實感云（Siggraph，2000）

圖1.3.4Xfiog3.0生成的挪威云杉

4.計算機動畫

隨著計算機圖形學和計算機硬件的不斷發展，人們已經不滿足于僅僅生成

高質量的靜態場景，于是計算機動畫就應運而生。事實上計算機動畫也只是

生成一幅幅靜態的圖象，但是每一幅都是對前一幅做一小部分修改（如何修

改便是計算機動畫的研究內容），這樣，當這些畫面連續播放時一，整個場景

就動起來了。

早期的計算機動畫靈感來源于傳統的卡通片，在生成幾幅被稱做“關鍵

幀”的畫面后，由計算機對兩幅關鍵幀進行插值生成若干“中間幀”，連續

播放時兩個關鍵幀就被有機地結合起來了。計算機動畫內容豐富多彩，生成

動畫的方法也多種多樣，比如基于特征的圖象變形，二維形狀混合，軸變形

方法、三維自由形體變形?FT）,Free干omDefomatbn）等。

近年來人們普遍將注意力轉向基于物理模型的計算機動畫生成方法。這

是一種嶄新的方法，該方法大量運用彈性力學和流體力學的方程進行計算，

力求使動畫過程體現出最適合真實世界的運動規律。然而要真正到達真實的

運動是很難的，比如人的行走或跑步是全身的各個關節協調的結果，要實現

很自然的人走路的動畫，計算方程非常復雜和計算量極大，基于物理模型的

計算機動畫還有許多內容需要進一步研究。

20世紀90年代是計算機動畫應用輝煌的十年。DEey公司每年都要出一

部制作精美的卡通動畫片，好萊塢的大片屢屢大量運用計算機生成各種各樣

精彩絕倫的特技效果，廣告設計，電腦游戲也頻頻運用計算機動畫。計算機

動畫也因這些商業應用的大力推動而有了極大的發展。

圖1.3.5基于特征的圖象變形（貓變虎）

圖1.3.6三維FFD得到的魚變形圖

5.用戶接口

用戶接口是人們使用計算機的第一觀感。一個友好的圖形化的用戶界面

能夠大大提高軟件的易用性，在DOS時代，計算機的易用性很差，編寫一個圖

形化的界面要費去大量的勞動，過去傳統的軟件中有60%的程序是用來處理

與用戶接口有關的問題和功能的。進入80年代后，隨著Xwindow標準的提出，

蘋果公司圖形化操作系統的推出，特別是微軟公司Window凝作系統的普及，

標志著圖形學已經全面融入計算機的方方面面。如今在任何一臺普通計算機

上都可以看到圖形學在用戶接口方面的應用。操作系統和應用軟件中的圖形、

動畫比比皆是，程序直觀易用。很多軟件兒乎可以不看任何說明書，而根據

它的圖形、或動畫界面的指示進行操作。

目前幾個大的軟件公司都在研究下一代用戶界面，開發面向主流應用的

自然、高效多通道的用戶界面。研究多通道語義模型、多通道整合算法及其

軟件結構和界面范式是當前用戶界面和接口方面研究的主流方向，而圖形學

在其中起主導作用。

6.計算機藝術

現在的美術人員、尤其是商業藝術人員都熱衷于用計算機軟件從事藝術

創作。可用于美術創作的軟件很多，如二維平面的畫筆程序（如CoieDiaw,

Photodiop,PairtShop）、專門的圖表繪制軟件（如Visb）、三維建模和

渲染軟件包（如3DMAX,Maya）、以及一些專門生成動畫的軟件（如Abas,

Softinage）等，可以說是數不勝數。這些軟件不僅提供多種風格的畫筆畫

刷，而且提供多種多樣的紋理貼圖，甚至能對圖象進行霧化，變形等操作。

好多功能是一個傳統的藝術家無法實現也不可想象的。

當然，傳統藝術的一些效果也是上述軟件所不能達到的，比如鋼筆素描

的效果，中國毛筆書法的效果，而且在傳統繪畫中有許多個人風格化的效果

也是上述軟件所無法企及的。然而圖形學工作者們是不廿失敗的，就在真實

感圖形學如火如荼發展的同時，模擬藝術效果的非真實感繪制（NPRNon-

HPhotorealisticRendering）也在逐漸發展。鋼筆素描是非真實感繪制的

一個重要內容，目前仍然是一個非常活躍的研究領域。鋼筆素描產生于中世

紀，從19世紀開始成為一門藝術，然而用計算機模擬鋼筆繪畫卻是20世紀90

年代的事情了。由于鋼筆素描與傳統的圖形學繪制方法差別很大，所以研究

起來難度也頗大，但是很多學者已經在這方面做了卓有成效的工作，比如華

盛頓大學的GeorgesWinkenbach,MichaelP.Sa險ury,德國Magdeburg

大學的0liverDeussen等人都在Siggraph會議上發表了高水平的論文。

1.3.7GeorgesWinkenbhch繪制的壺和碗(Siggiaph'96)

圖1.3.8Sa的ury繪制的茶壺(Siggraph'97)

圖1.3.9SaMiury繪缶!］的熊（Siggraph

圖L3.100liverDeussen繪制的素描樹(Siggraph2000)

1.4圖形設備

高質量的計算機圖形離不開高性能的計算機圖形硬件設備。一個圖形系

統通常由圖形處理器，圖形輸出設備和輸入設備構成。這一節我們將逐個探

討這些圖形硬件設備。

1.圖形顯示設備

圖形輸出包括圖形的顯示和圖形的繪制，圖形顯示指的是在屏幕上輸出

圖形，圖形繪制通常指把圖形畫在紙上，也稱硬拷貝，打印機和繪圖儀是兩

種最常用的硬拷貝設備。我們將不介紹打印機和繪圖儀，而將重點放在圖形

顯示設備上。

現在的圖形顯示設備絕大多數是基于陰極射線管(CRTCalhode—Ray

Tube)的監視器。歷史上CRT顯示器經歷了多個發展階段，出現過各種不同類

型的CRT監視器，如：存儲管式顯示器，隨機掃描顯示器(又稱矢量顯示器)，

但是這些顯示器的缺點是很明顯的，圖形表現能力也很弱。70年代開始出現的

刷新式光柵掃描顯示器是圖形顯示技術走向成熟的一個標志，尤其是彩色光柵

掃描顯示器的出現更將人們帶到一個多彩的世界。

彩色CRT監視器

圖141給出了CRT的工作原理。高速的電子束由電子槍發出，經過聚焦

系統、加速系統和磁偏轉系統就會到達熒光屏的特定位置。熒光物質在高速

電子的轟擊下會發生電子躍遷，即電子吸收到能量從低能態變為高能態。由

于高能態很不穩定，在很短的時間內熒光物質的電子會從高能態重新回到低

能態，這時將發出熒光，屏幕上的那一點就會亮了。顯然從這發光原理可以

看出這樣的光不會持續很久的，因為很快所有的電子都將回到低能態，不會

再有光發出。所以要保持顯示一幅穩定的畫面，必須不斷地發射電子束。

電子檢聚集系統加速系統磁偏轉系統

月子束

加熱燈絲

熒光屏T

金屬陰極電平空制器水平轉板垂直偏轉板

圖L4.1CRT顯示器簡易結構圖

那么電子束是如何發出的，又是如何控制它的強弱的呢？由圖141,我

們可以看出，電子槍是由一個加熱器，一個金屬陰極和一個電平控制器組成。

當加熱器加到一定高溫時，金屬陰極上的電子就會擺脫能壘的束縛，迸射出

去。而電平控制器是用來控制電子束的強弱的，當加上正電壓時，電子束就

會大量通過，將會在屏幕上形成較亮的點，當控制電平加上負電壓時，依據

所加電壓的大小，電子束被部分或全部阻截，通過的電子很少，屏幕上的點

也就比較暗。

顯然，電子槍發射出來的電子是分散的，這樣的電子束是不可能精確定

位的，所以發射出來的電子束必須通過聚焦。聚焦系統是一個電透鏡，能使

眾多的電子聚集于一點。

聚集后的電子束通過一個加速陽極達到轟擊激發熒光屏應有的速度。最

后由磁偏轉系統來達到指定位置。很明顯，如果電子束要到達屏幕的邊緣時，

偏轉角度就會增大。到達屏幕最邊緣的偏轉角度被稱為最大偏轉角。屏幕造

大偏轉角度就越大。但是磁偏轉的最大角度是有限的，為了達到大屏幕的要

得越大，要求的最求，只能將管子加長。所以我們平時看到的CRT顯示器屏

幕越大整個顯象管就越長。

我們剛才講過，要保持熒光屏上有穩定的圖象就必須不斷地發射電子束。

刷新一次指電子束從上到下將熒光屏掃描一次，其掃描過程如下圖所示。只

有刷新頻率高到一定值后，圖象才能穩定顯示。大約達到每秒60幀即6011z時，

人眼才能感覺到屏幕不閃爍，要使人眼覺得舒服，一般必須有85Hz以上的刷

新頻率。

掃描線

圖142電子束掃描過程示意圖

有些掃描速度較慢的顯示器，為了能得到好的顯示效果，采用一種叫隔

行掃描的技術。首先從第0行開始，每隔一行掃描，將偶數行都掃描完畢垂直

回掃后，電子束從第1行開始掃描所有奇數行。這樣的技術相當于將掃描頻率

加倍，比如逐行掃描30Hz人們會覺得閃爍，但是同樣的掃描頻率，如果用隔

行掃描技術人們就不會覺得閃爍。當然這樣的技術和真正逐行60Hz的效果還

是有差距的。

那么彩色CRT顯示器的彩色又是如何生產的呢？下面就讓我們來看看彩色

CRT顯示器顯示彩色的原理。

彩色CRT顯示器的熒光屏上涂有三種熒光物質，它們分別能發紅、綠、蘭

種三顏色的光。而電子槍也發出三束電子來激發這三種物質，中間通過一個

控制柵格來決定三束電子到達的位置。根據屏幕上熒光點的排列不同，控制

柵格也就不一樣。普通的監視器一般用三角形的排列方式，這種顯象管被稱

為蔭罩式顯象管。它的工作原理如下圖所示：

圖1.4.3蔭罩式彩色CRT顯色原理示意圖

三束電子經過蔭罩的選擇，分別到達三個熒光點的位置。通過控制三個

電子束的強弱就能控制屏幕上點的顏色。如將紅、綠兩個電子槍關了，屏幕

上就只顯示蘭色了。如果每一個電子槍都有256級（8位）的強度控制，那么

這個顯象管所能產生的顏色就是我們平時所說的24位真彩色了。

由于蔭罩式顯示器的固有缺點，如熒光屏是球面的，幾何失真大，而且

三角形的熒光點排列造成即使點很密很細也不會特別清晰。所以最近幾年蔭

柵式顯示器逐漸流行起來。其工作原理如下圖所示：

紅綠蘭

RGB

圖1.4.4蔭柵工作原理原理示意圖

事實上從原理來說兩者的區別只是光線的選擇方式和熒光點的排列不同

而已，但是兩者的顯示效果區別是很明顯的，蔭柵式顯象管亮度更高，色彩

也更鮮艷。常用的蔭柵式顯象管有日本索尼公司的特麗瓏管(Trinitron)

和三菱公司的鉆石瓏管(Diamondton),兩者稍有不同。采用蔭柵式顯象管

的顯示器有柱面顯示和平面顯示器，柱面顯示器的表面在水平方向仍然略微

凸起，但是在垂直方向上卻是筆直的，呈圓柱狀，故稱之為“柱面管”。柱

面管由于在垂直方向上平坦，因此與球面管相比幾何失真更小，而且能將屏

幕上方的光線反射到下方而不是直射入人眼中，因而大大減弱了眩光。平面

顯示器是最近兩年剛剛推出的產品，熒光屏為完全平面，大大提高了圖形的

顯示質量。由于玻璃的折射，屏幕會產生內凹的現象，但是通過一定的補償

技術，就能產生真正平面的感覺。由于平面顯示器的高清晰度、低失真以及

對人眼的低傷害，已經越來越得到人們的喜愛。

下圖表示了一個蔭柵示與蔭罩式的熒光屏的點排列，其中距離d就是人

們平常所說的點距了。

oato?

O??

點距為.25的柱點距為.28的球

面顯示器面顯示器

圖145柱面、球面點距定義示意圖

1-2LCI）顯示器

CRT顯示器歷經發展，目前技術已經越來越成熟，顯示質量也越來越好，

大屏幕也逐漸成為主流，但CRT固有的物理結構限制了它向更廣的顯示領域發

展。正如我們前面所說的屏幕的加大必然導致顯象管的加長，顯示器的體積

必然要加大，在使用時候就會受到空間的限制。另外，由于CRT顯示器是利用

產電子槍發射電子束來生圖像，產生輻射與電磁波干擾便成為其最大的弱點，

而且長期使用會對人們健康產生不良影響。在這種情況下，人們推出了LCD

（LiquidCrystalD卸by液晶顯示器）。

圖1.4.6Sony公司的兩款LCD外形

基本原理:

液晶是一種介于液體和固體之間的特殊物質，它具有液體的流態性質和

固體的光學性質。當液晶受到電壓的影響時一，就會改變它的物理性質而發生

形變，此時通過它的光的折射角度就會發生變化，而產生色彩。

液晶屏幕后面有一個背光，這個光源先穿過第一層偏光板，再來到液晶

體上，而當光線透過液晶體時，就會產生光線的色澤改變，從液晶體射出來

的光線，還必得須經過一塊彩色濾光片以及第二塊偏光板。由于兩塊偏光板

的偏振方向成90度，再加上電壓的變化和一些其他的裝置，液晶顯示器就能

顯示我們想要的顏色了。

液晶顯示有主動式和被動式兩種，其實這兩種的成像原理大同小異，只

是背光和源偏光板的設計和方向有所不同。主動式液晶顯示器又使用了FET場

效晶體管以及共通電極，這樣可以讓液晶體在下一次的電壓改變前一直保持

電位狀態。這樣主動式液晶顯示器就不會產生在被動式液晶顯示器中常見的

鬼影、或是畫面延遲的殘像等。現在最流行的主動式液晶屏幕是TFT（Thh

FibTransisto腐膜晶體管），被動式液晶屏幕有STN（SuperTN超扭曲向

列LCD）和DSTN（DoubkbyerSupeiTN雙層超扭曲向列LCD）等。

基本技術指標：

1.可視角度

由于液晶的成像原理是通過光的折射而不是象CRT那樣由熒光點直接發

光，所以在不同的角度看液晶顯示屏必然會有不同的效果。當視線與屏幕中

心法向成一定角度時，人們就不能清晰地看到屏幕圖象，而那個能看到清晰

圖象的最大角度被我們稱為可視角度。一般所說的可視角度是指左右兩邊的

最大角度相加。工業上有CR10（ContrastRatb）.CR5兩種標準來判斷液晶

顯示器的可視角度。

2.點距和分辨率

液晶屏幕的點距就是兩個液晶顆粒（光點）之間的距離，一般0.28~

0.32mm就能得到較好的顯示效果。

分辨率在液晶顯示器中的含義并不和CRT中的完全一樣。通常所說的液晶

顯示器的分辨率是指其真實分辨率，比如1024X768的含義就是指該液晶顯示

器含有1024X768個液晶顆粒。只有在真實分辨率下液晶顯示器才能得到最佳

的顯示效果。其它較低的分辨率只能通過縮放仿真來顯示，效果并不好。而

CRT顯示器如果能在1024X768的分辨率下能清晰顯示的話，那么其它如800義

600,640X480都能很好地顯示。

展望：

雖然目前的液晶顯示器在顯示效果上和傳統的CRT顯示器仍有一定的差距,

但是由于它的眾多優點，大有后來居上的勢頭。首先它的外觀小巧精致，厚

度只有6.5~8cm左右，比起CRT那個龐然大物體積實在是不可同日而語。其次

由于液晶象素總是發光，只有加上不發光的電壓是該點才變黑，所以不會產

生CRT那樣的因為刷新頻率低而出現的閃爍現象。而且它的工作電壓低，功耗

小，節約能源；沒有電磁輻射;對人體健康沒有任何影響。可以說這些優點

都極其符合現代潮流，相信隨著制造技術的進一步提高，價格進一步地降低，

液晶顯示器在新世紀一定能成為主流。

2.圖形處理器

一個光柵顯示系統離不開圖形處理器，圖形處理器是圖形系統結構的重

要元件，是連接計算機和顯示終端的紐帶。

應該說有顯示系統就有圖形處理器（俗稱顯卡），但是早期的顯卡只包

含簡單的存儲器和幀緩沖區，他們實際上只起了一個圖形的存儲和傳遞作用，

一切操作都必須有CPU來控制。這對于文本和一些簡單的圖形來說是足夠的，

但是當要處理復雜場景特別是一些真實感的三維場景，單靠這種系統是無法

完成任務的。所以以后發展的圖形處理器都有圖形處理的功能。它不單單存

儲圖形，而且能完成大部分圖形函數，這樣就大大減輕了CPU的負擔，提高了

顯示能力和顯示速度。隨著電子技術的發展，顯卡技術含量越來越高，功能

越來越強，許多專業的圖形卡已經具有很強的3D處理能力，而且這些3D圖形

卡也漸漸地走向個人計算機。一些專業的顯卡具有的晶體管數甚至比同時代

的CPU的晶體管數還多。比如2000年加拿大ATI公司推出的RADEON顯卡芯片含

有3千萬顆晶體管，達到每秒15億個像素填寫率。

一個顯卡的主要配件有顯示主芯片、顯示緩存（簡稱顯存）、數字模擬

轉換器（RAMDAOo

模擬信號輸出

算

計

控

機口主芯片

信

制

顯存

圖1.4.7顯卡工作原理簡單示意圖

顯示主芯片是顯卡的核心，俗稱GPU,它的主要任務是對系統輸入的視頻

信息進行構建和渲染，各圖形函數基本上都集成在這里頭。比如現在許多3D

卡都支持的。penGL硬件加速功能和DirectiC功能以及各種紋理渲染功能就是在

這里實現的。顯卡主芯片的能力直接決定了顯卡的能力。人們常聽說的3d伙

公司的Voodoo系列，S3公司的GX系列，nVlDIA公司的TNT2,GeForce256以及

用于專業領域的Quadro(俗稱GeFoireGL)都指的是顯卡主芯片的代號。

顯存是用來存儲將要顯示的圖形信息以及保存圖形運算的中間數據的，

它與顯示主芯片的關系，就像計算機的內存之于CPU一樣密不可分。顯存的

大小和速度直接影響著主芯片性能的發揮，簡單地說當然是越大越好、越快

越好。早期的顯存類型有FPM(FastPageMode)RAM和ED。ExtendedData

0ut)RAM,現在很流行的是SGRAM(SynchronousGraphicsRAMMUSDRAM

(SynchronousDRAM)。

RAMDAC就是視頻存儲數字模擬轉換器。它在視頻處理中，它的作用就是

把二進制的數字轉換成為和顯示器相適應的模擬信號。

3.圖形輸入設備

事實上最常用的圖形輸入設備就是基本的計算機輸入設備一一鍵盤和鼠

標。人們一般通過一些圖形軟件由鍵盤和鼠標直接在屏幕上定位和輸入圖形，

如人們常用的cAD系統就是用鼠標和鍵盤命令生產各種工程圖的。此外還有跟

蹤球、空間球、數據手套、光筆、觸摸屏等輸入設備。

跟蹤球和空間球都是根據球在不同方向受到的推或拉的壓力來實現定位

和選擇。數據手套則是通過傳感器和天線來獲得和發送手指的位置和方向的

信息。這幾種輸入設備在虛擬現實場景的構造和漫游中特別有用。

光筆是一種檢測光的裝置，它直接在屏幕上操作，拾取位置。光筆的形

狀和大小象一支圓珠筆，筆尖處開有一個圓孔，讓熒光屏的光通過這個孔進

入光筆。光筆的頭部有一組透鏡，把所收集的光聚集至光導纖維的一個端面

上，光導纖維再把光引至光筆另一端的光電倍增管，從而將光信號轉換成電

信號，經過整形后輸出一個有合適信噪比的邏輯電平，并作為中斷信號送給

計算機。光筆的這種結構和工作過程如下圖所示：

息

隹號

通轉蛆

圖148光筆結構示意圖

數字化儀是一種把圖形轉變成計算機能接收的數字形式專用設備，其基

本工作原理是采用電磁感應技術。它通常由一塊數據板和一根觸筆組成。數

據板中布滿了金屬柵格，當觸筆在數據板上移動時一，其正下方的金屬柵格上

就會產生相應的感應電流。根據已產生電流的金屬柵格的位置，就可以判斷

出觸筆當前的幾何位置。許多數字化儀提供了多種壓感電流，用不同的壓力

就會有不同的信息傳向計算機。這對于電腦藝術家來說尤其有用，他們可以

通過控制筆的壓力來產生不同風格的筆畫。現在非常流行的漢字手寫系統就

是一種數字化儀，可見數字化儀已經由一種專業工具變為一種普通的電腦外

設。

從專業工具變為家用電腦外設的最典型代表，要數圖形掃描儀。圖形掃

描儀是直接把圖形和圖象掃描到計算機中以象素信息進行存儲的設備。現在

市面上能見到的一般是36位或48位真彩色掃描儀，絕大多數是采用的固態器

件是電荷耦合器件(CCDChai^eCoupledDevice)。

下圖是常用圖形掃描儀的模塊框圖：

圖149掃描儀模塊框圖

CCD掃描儀的工作原理其實很簡單，用光源照射原稿，投射光線經過一組

光學鏡頭射到CCD器件上，得到元件的顏色信息，再經過模徵轉換器，圖象

數據暫存器等，最終輸入到計算機。為了使投射在原稿上的光線均勻分布，

掃描儀中使用的是長條形光源。掃描儀的兩個重要指標是分辨率和支持的顏

色，比如600dpi,36位真彩色。不用說，這兩項指標當然是越高越好，但是

制造難度和價格當然也會越高了。

早幾年掃描儀一般是幾萬元的天價，但是近兩年來由于技術的成熟以及

國內廠商的崛起，掃描儀性能不斷上揚，價格持續走低，一臺普通掃描儀甚

至不到一千元人民幣(專業掃描儀另當別論)，真正走進了千家萬戶。

圖形輸入設備中還有一個特殊的領域，那就是真實物體的三維信息的輸

入。在實際的產生過程中許多零件和樣板要進行大規模的生產就必須在計算

機中生成三維實體模型，而這個模型有時要通過已有的實物零件得到，這時

候就需要一種設備來采集實物表面各個點的位置信息。一般的方法是通過激

光掃描來實現，現在國外已經有許多這樣的商業儀器。這項技術的另一個應

用就是掃描保存古代名貴的雕塑和其它藝術品的三維信息，這樣可以在計算

機中產生這些藝術品的三維模型。美國斯坦福大學計算機系的著名圖形學專

家MarcLevoy曾經帶領他的30人的工作小組（包括美國斯坦福大學及美國華

盛頓大學的教師和學生）于1998?1999學年專門在意大利對文藝復興時代的

雕刻大師米開朗基羅的眾多藝術品進行掃描，保存其形狀和面片信息。當然

工作難度是相當大的，他們為此專門設計了一套硬件和軟件系統。數據量也

是驚人的，光大衛像（theDavid）就有20億個多邊形和7000張彩色圖象，總

共需要72G的磁盤容量。這次工作可以說是實體圖形輸入的一個顛峰之作。

圖1.4.10MareLevoy小組的工作現場（S^giaph，2000）

第二章光柵圖形學

光柵圖形顯示器可以看作一個象素的矩陣。在光柵顯示器上顯示任何一

種圖形，實際上都是一些具有一種或多種顏色的象素集合。確定最佳逼近圖

形的象素集合，并用指定屬性寫象素的過程稱為圖形的掃描轉換或光柵化。

對于一維圖形，在不考慮線寬時，用一個象素寬的直、曲線來顯示圖形。二

維圖形的光柵化必須確定區域對應的象素集，并用指定的屬性或圖案顯示之,

即區域填充。

任何圖形進行光柵化時，必須顯示在屏幕的一個窗口里，超出窗口的圖

不形予顯示。確定一個圖形的哪些部分在窗口內，必須顯示；哪些部分落在

窗口之外，不該顯示的過程稱為裁剪。裁剪通常在掃描轉換之前進行，從而

可以不必對那些不可見的圖形進行掃描轉換。

對圖形進行光柵化時，由于顯示器的空間分辨率有限，對于非水平、垂

直、士45。直線，因象素逼近誤差，使所畫圖形產生畸變(臺階、鋸齒)的

現象稱之為走樣；用于減少或消除走樣的技術稱為反走樣(antialiasing)。

提高顯示器的空間分辨率可以減輕走樣問題，但這是以提高設備成本為代價

的。實際上，當顯示器的象素可以用多亮度顯示時，可以通過調整圖形上各

象素的亮度來減輕走樣問題。

由于存在不透光的物體，因此阻擋了來自某些物體部分的光線到達觀察

者，這些物體部分成為隱藏部分。隱藏部分是不可見的，如果不把隱藏的線

或面刪除，還可能發生對圖的錯誤理解。為了使計算機圖形能夠真實的反映

這一現象，必須把隱臧的部分從圖中消除，習慣上稱作消除隱藏線和隱臧

面，或簡稱為消隱。

2.1直線段的掃描轉換算法

2.2圓弧的掃描轉換算法

2.3多邊形掃描轉換與區域填充

2.4字符

2.5裁剪

2.6反走樣

2.7消隱

2.8練習題

2.1直線段的掃描轉換算法

在數學上，理想的直線是沒有寬度的，由無數個點構成的集合。當我們

對直線進行光柵化時一，只能在顯示器所給定的有限個象素組成的矩陣中，確

定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操

作，這就是通常所說的用顯示器繪制直線或直線的掃描轉換。

由于一個圖中可以包含成千上萬條直線，所以要求繪制算法應盡可能的

快。本節我們介紹一個象素寬直線的三個常用算法：數值微分法（DDA）、中

點畫線法和Bipsenham算法。

2.1.1數值微分（DDA）法

已知過端點「060,丫0）11&1,丫1）的直線段1@011）,;直線斜率為

k=—~~邑畫線過程從x的左端點xO開始，向x右端點步進，步長=1（個象

%-%

素），計算相應的y坐標尸kx+B；取象素點（x,round（y））作為當前點的坐標。

計算yiH=kXiH+B

=kixi+B+kDx

=yi+kDx

當Dx=l;yiu=yi+k

即：當X每遞增1,y遞增k(即直線斜率)；

DDA畫線算法程序

voidDDALine(intxo,intyO,intxl,htyi,intcobr)

{intx；

fbatdx,dy,y,k

dx=xl-xo,dy=yi^o；

k=dy/dx,y=yo；

for(x=xo；x￡xi,x++)

{drawpixel(x,int(y+0.5),cobr);

y=y+k;

)

)

舉例：用DDA方法掃描轉換連接兩點PO(0,0)和Pl(5,2)的直線段。

xint(y+(X5)y+0.5

000

Line：P0(0,0)—Pl(5,2)

210.8+0.5

311.2+0.5

421.6+0.5圖2.1.1直線段的掃描轉換

注意上述分析的算法僅適用于|k|Wl的情形。在這種情況下，x每增

加l,y最多增加1。當k|>1時，必須把x,y地位互換，y每增加1,x相應

增加在這個算法中，y與k必須用浮點數表示，而且每一步都要對y進行

四舍五入后取整。這使得它不利于硬件實現。

2.1.2中點畫線法

畫直線段的過程中，當前象素點為(xp,yp),一個象素點有兩種可選擇

點pi(xp+l,yp)或p2(xp+l,yp+l)。若M=(xp+1,yp+0⑸，為pl與p2之中點，

Q為理想直線與x=xp+l垂線的交點。當M在Q的下方，則P2應為下一個象素點;

M在Q的上方，應取P1為下一點。就是中點畫線法的基本原理。

圖2.1.2中點畫線法每步迭代涉及的象素和中點示意圖

下面討論中點畫線法的實現。令直線段L(p0(x0,y0),pl(xl,yl)),其方程

式F(x,y)=ax+by+c=O。其中，a=yO-yl,b=xl-xO,c=xOyl-xlyO;點與L的

關系：on:F(x,y)=0;up:F(x,y)>0;down:F(x,y)<0;因此，欲判斷中M在Q點的上方還是下

方，只要把M代入F(x,y),并判斷它的符號。構造判

別式：

d=FM)=F(xp+1,yp+0.5)=a(xp+l)+b(yp+0.5)+c

當d<0,M在L(Q點)下方，取P2為下一個象素；

當d>0,M在L(Q點)上方，取P1為下一個象素；

當d=0,選Pi或P2均可，約定取P1為下一個象素；

注意到d是xp,yp的線性函數，可采用增量計算，提高運算效率。

若當前象素處于d30情況，則取正右方象素Pl(xp+l,yp)，要判下一個象素

位置，應計算di=F(xp+2,yp+(X5)=a(xp+2)+b(yp+0.5)=d+a；增量為a

若d<0時，則取右上方象素P2(xP+l,yP+l)o要判斷再下一象素，則要計算

d2=F(xp+2,yp+L5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量為a+b

畫線從(xo,yo)開始，d的初值dO=F(xo+1,yo+O.5)=F(xo,yo)+a+O.5b因

F(xo,yo)=0,則do=a+0.5b。

由于我們使用的只是d的符號，而且d的增量都是整數，只是初始值包含小數。

因此，我們可以用2d代替d來擺脫小數，寫出僅包含整數運算的算法。

中點畫線算法程序

voidMidpointLine(intxO,intyO,intxl,htyl,intcobr)

{hta,b,dl,d2,d,x,y;

apyopi,b=xi-xo,d=2*a+b;

di=2*a,d2=2*(a+b);

x=xo,y=yo;

drawpixel(x,y,cobr);

while(x<xl)

{if(d<0){x++,y++,d+=d2;}

else{x++,d+=dl;}

drawpixel(x,y,cobp;

}代whHe*/

}AmidPoirtLhe*/

舉例用中點畫線方法掃描轉換連接兩點PO(0,0)和Pl(5,2)的直線段。

a=y0*yl=-2;b=xl-x0=5;d0=2*a+b=1;dl=2*a=-4;d2=2*(a+b)=6,

xyd

012345

001

10-3425圖2.1.3

213

31-1

用中點畫線法對連接兩點的直線進行光柵化

5215

問題1：若上述算法往下取二步①三2）,則算法和象素的取法將變成怎樣？

2.1.3Bresenham算法

Bresenham算法是計算機圖形學領域使用最廣泛的直線掃描轉換算法。該

方法類似于中點法，由誤差項符號決定下一個象素取右邊點還是右上點。

算法原理如下：過各行各列象素中心構造一組虛擬網格線。按直線從起

點到終點的順序計算直線與各垂直網格線的交點，然后確定該列象素中與此

交點最近的象素。該算法的巧妙之處在于采用增量計算，使得對于每一列，

只要檢查一個誤差項的符號，就可以確定該列的所求象素。

如下圖所示。設直線方程為，%+]=%+化（馬+i-玉）=乂+發其中k=dy

/dxo假設x列的象素已經確定為xi,其行坐標為yk那么下一個象素的列

坐標為xi+1,而行坐標要么不變為yi,要么遞增1為yi+L是否增1取決于

如圖所示誤差項d的值。因為直線的起始點在象素中心，所以誤差項d的初值

do=0oX下標每增加1,d的值相應遞增直線的斜率值k,EPd=d+ko一旦

d2l,就把它減去1,這樣保證d在0、1之間。當d?0.5時，直線與xi+1

列垂直網格交點最接近于當前象素（xi,yi）的右上方象素（xi+1,yi

+1）;而當d<0.5時，更接近于右方象素（xi+1,yi）o為方便計算，令

e=d—0.5,e的初值為-0.5,增量為k。當eNO時，取當前象素（xi,yD

的右上方象素（xi+1,yi+1）；而當e〈0時，更接近于右方象素（xi+1,

yi）o

圖2.1.4Bresenham算法所用誤差項的幾何含義

Bresenham畫線算法程序：

voidBresenhamline(intxO,htyO,intxl,cobr)

{intx,y,dx,dy;

fbatk,e;

dx=xl-xO,dy=yl-yO,k=dy/dx;

所-0.5,x=x0,y=yO;

for(F0;i￡dx;6+)

{drawpixel(x,y,color)；

x=x+l,e=e+k;

if(e30)

{y++,e=e-l;}

舉例：用Br^senham方法掃描轉換連接兩點PO(0,0)和Pl(5,2)的直線段。

xye

00-0.5

10-0.1

21-0.7

31-0.3

42-0.9

52-0.5

上述bre史nham算法在計算直線斜率與誤差項時用到小數與除法。可以改用整

數以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：

&'=2*e*dx

改進的Biesenham畫線算法程序：

voidInterBresenhamline(intxO,intyO,intxl,intyl,htcobi)

{dx=xl-xO,dy=yl-yO,e=-dx;

x=xO,y=yO;

for(F0;i￡dx;-e+)

{drawpixel(x,y,cobp;

x++,即e+2*dy;

if(e30){y++;e=e-2*dx;}

第二章光柵圖形學

2.2圓弧的掃描轉換算法

2.2.1圓的特征

圓被定義為到給定中心位置(xc,yc)距離為曲］點集。圓心位于原點的

圓有四條對稱軸x=O,y=O,x=y/Ux=-y。若已知圓弧上一點(x,y)，可以得

到其關于四條對稱軸的其它7個點，這種性質稱為八對稱性。因此，只要掃

描轉換八分之一圓弧，就可以求出整個圓弧的象素集。

顯示圓弧上的八個對稱點的算法：

voidCircJePoints(intx,inty,intcobr)

{drawpixel(x,y,cobr);dn?vpixel(y,x,cobi);

drawpixel(-x,y,cobD;drawpixel@,-x,cobp;

drawpixel(x,-y,cobr);drawpixel(-y,x,cobr);

drawpixel(-x,-y,cobr);drawpixel(-y,-x,color);

)

222中點畫圓法

構造圓函數。對于圓上的點，F(x,y)=x2+y2-R2：對于圓外的點，

F(x,y)=0；對于圓內的點>0。與中點畫線法一樣，構造判別式

F(")<0o

d==尸(勺+1,小一0。=(勺+川+⑶。一0.5)2—爐

若則應取P1為下一象素，而且再下一象素的判別式為

d=F(x,+2),-0.5)=(勺+2)2+3/一0。'一五2=d+2x,+3

H之0若則應取P2為下一象素，而且下一象素的判別式為

d=F（勺+2,%-1.5）=（勺+2）2+0？-15）2-R2=d+2（馬-%）+5

我們這里討論的是按順時針方向生成第二個八分圓。則第一個象素是（0,

R）,判別式d的初始值為四=F（l,K-0.5）=1.25-五

圖221當前象素與下一象素的候選者

MhPoinCircle(intrintcobi)

{htx,y;

fbatd;

x=O;y=r;d=1.25-r;

circlepoints(x,y,cobD;

whi]e(x<=y)

{if(d<0)d+=2*x+3;

else{d+=2*(x-y)+5;y-;}

x++;

circlepoints(x,y,cob?;

為了進一步提高算法的效率，可以將上面的算法中的浮點數改寫成整數，將

乘法運算改成加法運算，即僅用整數實現中點畫圓法。

2.3多邊形的掃描轉換與區域填充

在計算機圖形學中，多邊形有兩種重要的表示方法：頂點表示和點陣表

示。頂點表示是用多邊形的頂點序列來表示多邊形。這種表示直觀、兒何意

義強、占內存少，易于進行兒何變換，但由于它沒有明確指出哪些象素在多

邊形內故不能直接用于面著色。點陣表示是用位于多邊形內的象素集合來刻

畫多邊形。這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面

著色所需要的圖形表示形式。光柵圖形的一個基本問題是把多邊形的頂點表

示轉換為點陣表示。這種轉換稱為多邊形的掃描轉換。

2.3.1多邊形的掃描轉換

多邊形分為凸多邊形、凹多邊形、含內環的多邊形。

①凸凸多邊形：②凹多邊形③含內環的多邊形

任意兩頂點間的任意兩頂點間的

連線均在多邊形連線有不在多邊

內形內的部分

圖231多邊形的種類

掃描線算法

掃描線多邊形區域填充算法是按掃描線順序，計算掃描線與多邊形的相

交區間，再用要求的顏色顯示這些區間的象素，即完成填充工作。區間的端

點可以通過計算掃描線與多邊形邊界線的交點獲得。對于一條掃描線，多邊

形的填充過程可以分為四個步驟：

(1)求交：計算掃描線與多邊形各邊的交點；

(2)排序：把所有交點按x值遞增順序排序；

(3)配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線

與多邊形的一個相交區間，

(4)填色：把相交區間內的象素置成多邊形顏色，把相交區間外的象素置

成背景色。

圖232一個多邊形與若干掃描線

為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進行

求交運算。我們把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線

交點x坐標遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET)。

P4P「F3F4

?P7~2|8]~~一1二I。I8|?|

LA