第2講 計(jì)算機(jī)圖形學(xué)基礎(chǔ)-基本圖形生成

2.1．計(jì)算機(jī)圖形學(xué)概述2.2．圖形顯示原理

—CRT顯示器工作原理

—LCD顯示器工作原理2.3．基本圖形生成算法

—

直線生成算法

—

圓弧生成算法

—

其它基本圖形生成2.4．圖形裁減算法2.5．多邊形填充算法（選學(xué)）2.6．圖形反走樣算法（選學(xué)）2.7．基于OpenGL圖形庫生成圖形（選學(xué)）第2講計(jì)算機(jī)圖形學(xué)基礎(chǔ)——基本圖形生成本章目的：(1)介紹顯示器顯示圖形的基本原理；

(2)介紹基本圖形元素的生成算法。思考問題：1）圖形如何在屏幕上顯示出來？？2）CAD圖形如何生成？？2.1．計(jì)算機(jī)圖形學(xué)概述

計(jì)算機(jī)圖形學(xué)主要研究用計(jì)算機(jī)進(jìn)行圖形信息的表達(dá)、輸入、存儲(chǔ)、顯示、輸出、檢索及圖形運(yùn)算等。具體地說，大致有以下內(nèi)容：

(1)圖形的輸入：研究如何把要處理的圖形輸入到計(jì)算機(jī)內(nèi)，以便讓計(jì)算機(jī)進(jìn)行各種處理。

(2)產(chǎn)生圖形的算法：研究在顯示器或其它輸出設(shè)備上產(chǎn)生圖形的算法；

(3)圖形的數(shù)據(jù)結(jié)構(gòu)：研究圖形在計(jì)算機(jī)內(nèi)的表示方法；

(4)圖形的變換：研究圖形的各種幾何變換；

(5)圖形運(yùn)算：包括圖形的分解、組合等；

(6)圖形語言：各種圖形處理功能的語言;(7)圖形軟件的標(biāo)準(zhǔn)化：圖形軟件與設(shè)備無關(guān)及接口兼容性。總的來說，計(jì)算機(jī)圖形學(xué)應(yīng)該解決和研究下列一些問題：

(1)圖形表示和處理的數(shù)學(xué)方法及其實(shí)現(xiàn)的計(jì)算機(jī)算法；

(2)設(shè)計(jì)一個(gè)好的圖形軟件支撐系統(tǒng)；

(3)設(shè)計(jì)與實(shí)際應(yīng)用相結(jié)合的圖形應(yīng)用系統(tǒng)。一類是線條，如工程圖、地圖、曲線圖表等；另一類是明暗圖，與照片相似。為了生成圖形，首先要有原始數(shù)據(jù)或數(shù)學(xué)模型，如工程人員構(gòu)思的機(jī)械零件模型，飛機(jī)的總體方案模型，科學(xué)數(shù)據(jù)的可視化等等。這些數(shù)字化的輸入經(jīng)過計(jì)算機(jī)處理后變成圖形輸出。本課程重點(diǎn)從CAD需求角度來介紹相關(guān)研究?jī)?nèi)容：工程產(chǎn)品設(shè)計(jì)中的二維工程圖、三維實(shí)體模型的顯示本章主要介紹：基本圖形生成原理圖形的具體應(yīng)用范圍很廣，但是從基本的處理技術(shù)看主要有兩類：2.2、圖形顯示原理

–顏色2.2、圖形顯示原理顯示器是計(jì)算機(jī)上最常用的輸出設(shè)備，用于顯示文本和圖形圖像。目前顯示器多為平板顯示器（LCD，LED、PDP，OLED），陰極射線管（CRT）。CRT是通過電子槍發(fā)射電子束，經(jīng)過聚焦系統(tǒng)、加速電極、偏轉(zhuǎn)系統(tǒng)，按行列次序掃描點(diǎn)矩陣，轟擊到熒光屏的不同點(diǎn)陣部位，被其內(nèi)表面的熒光物質(zhì)吸收，在該點(diǎn)發(fā)光產(chǎn)生可見的圖形?！?/p>

陰極射線管顯示器（CRT）彩色CRT顯示器包含數(shù)以百萬計(jì)的磷光點(diǎn)，成陣列排列。每個(gè)陣列點(diǎn)（稱為象素）有三個(gè)熒光點(diǎn)（紅、綠、藍(lán)三色），由三支電子槍控制各自電子束強(qiáng)度實(shí)現(xiàn)不同亮度顏色，分別為紅色、綠色和藍(lán)色（即紅、綠、藍(lán)三基色），當(dāng)通過屏幕的電子束擊中它們時(shí)，就會(huì)發(fā)光呈彩色圖像。若紅（R）、綠（G）、藍(lán)（B）三色每支電子槍發(fā)出的電子束強(qiáng)度為256個(gè)等級(jí)，則顯示器能同時(shí)顯示256*256*256=16M種顏色，稱為真彩色系統(tǒng)。象素（Pixel）熒光屏上畫面的每一光點(diǎn)稱為一個(gè)象素。若屏幕尺寸一定，水平和豎直方向上能識(shí)別的最大像素個(gè)數(shù)用分辨率來描述，如800*600，1024*768，1280*1024等。

分辨率（Resolution）每秒鐘重繪屏幕的次數(shù)，CRT產(chǎn)生穩(wěn)定圖像所需要的最小刷新頻率：

=1秒/熒光物質(zhì)的持續(xù)發(fā)光時(shí)間（Hz）刷新頻率（僅CRT）與電視工作原理類似，CRT電子束從上到下、從左到右掃描進(jìn)行，每掃描一遍稱為一幀。注：液晶顯示器原理不同于CRT，不受刷新頻率影響。但液晶顯示有拖尾現(xiàn)象，是因液晶偏轉(zhuǎn)延遲所致，延時(shí)越長，拖尾越重。幀掃描每個(gè)象素都對(duì)應(yīng)于Buffer中的一個(gè)存儲(chǔ)單元，用來存儲(chǔ)象素顏色（灰度）值的存儲(chǔ)器，稱為幀緩沖存儲(chǔ)器。目前，顯示器均采用32bit來表示顏色，其中Ｒ、Ｇ、Ｂ各８位，另８位可用于表示色彩透明度，此即顏色的ＲＧＢＡ表示。分辨率1024x1024的一幀圖像，其顯存所需容量：

＝1024x1024x32bit/8＝４Ｍ（byte）幀緩沖存儲(chǔ)器簡(jiǎn)稱幀緩存俗稱顯存

象素的亮度值控制電子束對(duì)熒光屏的轟擊強(qiáng)度，象素在幀緩存寄存器中的位置編碼控制電子束的偏轉(zhuǎn)位置。圖形系統(tǒng)為靈活控制圖形顏色變化，往往不直接將幀緩沖器中的數(shù)值作為顯示的亮度值，而是先經(jīng)過顏色查找表（稱調(diào)色板)

產(chǎn)生變換值來控制光點(diǎn)亮度。其工作方式：顯存中某位值

顏色表地址

屏幕上的亮度LCD顯示系統(tǒng)原理示意圖——液晶顯示器（LCD）液晶是一種介于液體和固體之間的特殊物質(zhì)，它具有液體的流態(tài)性質(zhì)和固體的光學(xué)性質(zhì)。當(dāng)液晶受到電壓的影響時(shí)，就會(huì)改變它的物理性質(zhì)而發(fā)生偏轉(zhuǎn)形變，此時(shí)通過它的光的折射角度就會(huì)發(fā)生變化，而產(chǎn)生色彩。當(dāng)視線與屏幕中心法向成一定角度時(shí)，就不能清晰看到屏幕圖象，其最大角度稱為可視角度。目前CRT顯示器被淘汰，LCD顯示器是主流。家用電視也以液晶及平板電視為主流。新一代LED顯示器正以其超薄、節(jié)能和全高清等技術(shù)發(fā)展迅猛，3D電視是未來發(fā)展方向。我國在高端液晶面板技術(shù)受制于人(日韓廠商)，LED面板技術(shù)不容樂觀。2.3．基本圖形生成算法無論是液晶顯示器（LCD），還是陰極射線管顯示器（CRT），都是通過改變屏幕上象素點(diǎn)的顏色及亮度來顯示圖形。對(duì)于一個(gè)二維CAD系統(tǒng)來說，直線、圓、圓弧、自由曲線是最常見的基本幾何要素。對(duì)于一個(gè)三維CAD系統(tǒng)來說，除了具備上述要素外，還需平面、圓柱面、球面、圓環(huán)面及自由曲面。曲線、曲面及三維形體將在后面章節(jié)介紹，本章僅介紹直線、圓弧的生成。思考：直線和圓弧如何在生成并顯示??畫直線是CAD中最常用的操作，在光柵顯示器上畫線只能以點(diǎn)近地似顯示。如下圖，從（x1,y1）到（x2,y2）畫直線實(shí)質(zhì)上是尋找最佳逼近直線的象素序列，并填入色彩數(shù)據(jù)，該過程稱為直線光柵化，也稱直線掃描轉(zhuǎn)換。常用算法有：直線DDA算法、中點(diǎn)算法、Bresenham算法等,其中以Bresenham算法效率高，應(yīng)用最廣泛。——

直線生成算法直線y

=kx+b中每一點(diǎn)坐標(biāo)(xi+1,yi+1)都可由前一點(diǎn)坐標(biāo)(xi,yi)加一個(gè)增量（△x,△y）而得到，即：xi+1=xi+△x，yi+1=yi+△y，且△

y=k·

△x。設(shè)直線的起點(diǎn)（x1,y1）為所畫直線的初值，考慮到象素為整數(shù)，于是畫線算法過程可表述為：1）直線DDA算法（即微分算法）△x＝x2－x1，△

y＝y(tǒng)2－y1，k＝△

y/△xyi+1=kxi+1+b=k(xi+1)+b=(kxi+b)+k=yi+k(xi,yi)→(xi+1

,yi+k)yi=round(yi)=(int)(yi+0.5)

上述算法簡(jiǎn)單，易實(shí)現(xiàn)，但有浮點(diǎn)數(shù)取整運(yùn)算，不利于硬件實(shí)現(xiàn)，效率低；算法僅適用于k≤1的情形：x每增加1，y最多增加1。當(dāng)k

1時(shí)，必須把x，y互換。k≤1k

1DDA算法實(shí)現(xiàn)算法應(yīng)用舉例設(shè)直線起點(diǎn)P0（0，0），終點(diǎn)P1（5，2）2）Bresenham算法原理Bresenham算法是使用最廣泛的直線生成算法。該算法假設(shè)過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素中與此交點(diǎn)最近的象素（如圖）。算法思想：設(shè)直線方程為：yi+1=yi+k(xi

+1

–xi)，斜率k<1

，并設(shè)初始象素坐標(biāo)為（xi，yi)

，誤差初值d0＝0。顯然，若下一象素橫坐標(biāo)為xi＋1，則縱坐標(biāo)yi+1可能為yi，或yi＋1。根據(jù)方程可知，x坐標(biāo)每增加1，d的值相應(yīng)遞增斜率值k，即d＝d＋k；yi+1是否增1，則取決于誤差項(xiàng)d的值，具體如下：

如果d≥1，就把它減去1，這樣保證d在0、1之間；

當(dāng)d≥0.5時(shí)，直線與垂線x=xi＋1交點(diǎn)最接近于當(dāng)前象素

(xi，yi)的右上方象素(xi＋1，yi＋1)；

而當(dāng)d<0.5時(shí)，更接近于右方象素(xi＋1，yi)。為加速計(jì)算，令e＝d－0.5，e的初值為－0.5，增量為k，則可轉(zhuǎn)化為下式判斷：

當(dāng)e≥0時(shí)，取當(dāng)前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；

而當(dāng)e<0時(shí)，取(xi，yi)右方象素(xi＋1，yi)。voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy；

floatk,e;

dx=x1-x0；dy=y1-y0；k=dy/dx；

e=-0.5；x=x0；y=y0；

for(i=0；i<dx；i++)

{drawpixel(x,y,color);

x=x+1；e=e+k;

if(e≥0)

{y++；e=e-1;}

}}－算法程序－算法舉例用Bresenham方法生成兩點(diǎn)P0（0,0）和P1（5,2）的直線段xye00-0.510-0.121-0.731-0.342-0.9

52-0.5上述計(jì)算直線斜率與誤差項(xiàng)時(shí)用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項(xiàng)e（e=dy/dx-0.5）的符號(hào)，對(duì)此誤差等式兩邊同時(shí)乘以2*dx，并作替換：e=2*e*dx，則誤差判斷式變?yōu)椋篹=2*dy－dx。voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy，e；

x=x0；y=y0;dx=x1-x0；dy=y1-y0；

e=2*dy-dx;//替換：e=k-0.5

for(i=0;i<dx;i++)

{drawpixel(x,y,color);

x++；e=e+2*dy;//替換：e=e+k

if(e≥0){y++;e=e-2*dx;}//替換：e=e-1

}}－算法特點(diǎn)算法避免了除法及浮點(diǎn)運(yùn)算，速度加快，精度高。進(jìn)一步改進(jìn)：2的倍數(shù)可采用移位操作，便于硬件實(shí)現(xiàn)，速度更快。Bresenham算法改進(jìn)：圓也是圖形系統(tǒng)中常用的元素。我們將圓定義為所以距離中心位置(xc,yc)為給定值r的點(diǎn)集。圓的方程為：定義：為敘述方便，僅考慮圓心在原點(diǎn)的圓（其它位置圓可平移到原點(diǎn)位置）。不妨設(shè)函數(shù)：顯然有：F（x，y）<0，則（x,y)位于圓邊界內(nèi)

F（x，y）＝0，則（x,y)位于圓邊界上

F（x，y）>0，則（x,y)位于圓邊界外考慮到圓的八對(duì)稱性，不妨以第二個(gè)八分圓進(jìn)行分析，其它八分圓則可通過鏡像實(shí)現(xiàn)?！獔A弧生成算法yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oRPP1MP2圓的掃描轉(zhuǎn)換算法有：直接離散法、中點(diǎn)法、Bresenham算法等。如右圖，圓上的點(diǎn)滿足判別式：PP1MP2

F(x,y)=x2+y2–R2=0中點(diǎn)M：M=(xp+1,yp-0.5)，將中點(diǎn)M代入上式得：當(dāng)d＜0時(shí)，M在圓內(nèi)，P1距離圓弧近，取P1(xp+1,yp)當(dāng)d＞0時(shí)，M在圓外，P2距離圓弧近，取P2(xp+1,yp-1)若d<0,取P2為下一象素，再下一象素的判別式為：若d≥0,取P1為下一象素，再下一象素的判別式為：第一個(gè)象素點(diǎn)是（0,R），判別式d的初始值為：增量——圓的中點(diǎn)算法算法中點(diǎn)算法（續(xù)前）為提高算法的效率，將算法中的浮點(diǎn)數(shù)改寫成整數(shù)，用e=d－0.25代替

d，增量不變，取e0=1－R，則改進(jìn)后的中點(diǎn)算法為：MidpointCircle(r,color){x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++;}else{d+=2*(x-y)+5;x++;y++;}drawpixel(x,y,color);}}MidpointCircle_1(r,color){x=0;y=r;e=1-r;drawpixel(x,y,color);while(x<y){if(e<0){e+=2*x+3;x++;}else{e+=2*(x-y)+5;x++;y--;}drawpixel(x,y,color);}}中點(diǎn)算法示例：圓的多邊形逼近算法

其它畫圓算法圓的Bresenham算法圓的多邊形逼近算法自由曲線算法：轉(zhuǎn)化為多直線段逼近，再調(diào)用畫直線算法。三維線框圖：本質(zhì)上都轉(zhuǎn)化為多直線段組合，直接調(diào)用畫直線算法?！?/p>

其它基本圖形生成算法圖形基本生成算法小結(jié)研究圖形的基本生成算法，其宗旨是盡快提高算法的計(jì)算速度、精度及可靠性，為各種圖形平臺(tái)提供算法支撐。原則：盡量避免除法、浮點(diǎn)運(yùn)算，盡可能采用整數(shù)加減及移位等運(yùn)算。

(寫算法要力爭(zhēng)精益求精哦!!!)思考問題：1）如何提高基本圖形的生成算法效率2）直線的Bresenham算法比DDA算法、中點(diǎn)算法優(yōu)勢(shì)在哪？還有哪些需要改進(jìn)。通常，直線邊和窗口的關(guān)系分為如下三類：

（a）整條直線在窗口內(nèi)。不剪裁，全顯示。

（b）整條直線在窗口外。不剪裁，不顯示。

（c）部分直線在窗口之內(nèi)，部分在窗口之外。此時(shí)，需要求出直線與窗框之交點(diǎn)，并將窗口外的直線部分剪裁掉，顯示窗口內(nèi)的部分。2.4、圖形裁剪算法圖形裁剪是CAD系統(tǒng)的基本功能，其作用是確定圖形中落在顯示區(qū)內(nèi)的那部分圖形，這個(gè)選擇過程稱為裁剪。只有窗口內(nèi)的物體才能顯示，窗口之外的物體都是不可見的。1）直線的裁減算法算法思路：介紹一種Cohen-Sutherland直線裁剪算法——Cohen-Sutherland直線裁剪算法Cohen-Sutherland直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口及其周圍以4bit的二進(jìn)制數(shù)進(jìn)行編碼，4個(gè)bit分別代表窗外上、下、右、左空間的編碼值。如右圖左上區(qū)域編碼為1001，右上區(qū)域編碼為1010。窗內(nèi)編碼為0000。將窗口及其鄰域分為5個(gè)區(qū)域：上域：區(qū)域（1001，1000，1010）下域：區(qū)域（0101，0100，0110）左域：區(qū)域（1001，0001，0101）右域：區(qū)域（1010，0010，0110）內(nèi)域：區(qū)域（0000）1）端點(diǎn)編碼。根據(jù)直線兩端點(diǎn)坐標(biāo)值相對(duì)位置，對(duì)直線兩端點(diǎn)進(jìn)行分類編碼；2）去除不需剪裁的直線。規(guī)則是：如果一條直線的兩端在同一區(qū)域，則該直線不需剪裁，否則該直線為可能剪裁直線；3）剪裁可能直線。規(guī)則是：如果直線的一個(gè)端點(diǎn)在上（下、左、右）域，則此直線與上邊框求交，然后刪去上（下、左、右）邊框以上（下、左、右）的部分；對(duì)直線的另一端點(diǎn)也按該規(guī)則判斷。算法思路：首先將不需剪裁的直線找出，并刪去其中在窗外的直線；然后對(duì)其余直線，逐條與窗框求交點(diǎn)，并將窗外部分刪去。算法步驟：2）多邊形裁剪算法每次用窗口的一條邊界(包括延長線)對(duì)要裁剪的多邊形進(jìn)行裁剪，裁剪時(shí)，順序地測(cè)試多邊形各頂點(diǎn)，保留邊界內(nèi)側(cè)頂點(diǎn)，刪除外側(cè)頂點(diǎn)，同時(shí)，適時(shí)地插入新頂點(diǎn)，即交點(diǎn)和窗口頂點(diǎn)，從而得到一個(gè)新多邊形頂點(diǎn)序列。然后以此新的頂點(diǎn)序列作為輸入，相對(duì)第二條窗邊界線進(jìn)行裁剪，又得到一個(gè)更新的多邊形頂點(diǎn)序列。依次下去，相對(duì)于第三條、第四條邊界線進(jìn)行裁剪，最后輸出的多邊形頂點(diǎn)序列即為所求的裁剪好了的多邊形，如下圖所示。(1)(2)(3)(4)算法思路：多邊形圖形的裁減算法有許多，這里僅介紹Sutherland-Hodgeman算法。新的多邊形頂點(diǎn)序列產(chǎn)生規(guī)則：在用窗口一條邊界及其延長線裁剪一個(gè)多邊形時(shí)，該邊界線把平面分成兩個(gè)部分：邊界內(nèi)側(cè)和邊界外側(cè)。如下圖，依次考慮有序多邊形的各邊。假設(shè)當(dāng)前處理的邊為SP(箭頭表示順序，S為前一點(diǎn)，P為當(dāng)前點(diǎn))，邊SP與裁剪線的位置關(guān)系有四種情況：

1）S在外側(cè)，P在內(nèi)側(cè)。則交點(diǎn)Q與當(dāng)前點(diǎn)P均保存到新多邊形中；

2）S、P均在內(nèi)側(cè)。則當(dāng)前點(diǎn)P保存到新多邊形中；

3）S在內(nèi)側(cè)，P在外側(cè)。則交點(diǎn)Q保存到新多邊形中；

4）S、P均在外側(cè)。則沒有點(diǎn)被保存到新多邊形中。算法加速思想：關(guān)鍵在于提高相交判斷速度，尤其圖形復(fù)雜是更是如此!!!多邊形裁減算法示例cde(f)去除多余懸邊區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。區(qū)域填充一般分兩類：

多邊形填充

和種子填充。1）多邊形填充算法2.5、區(qū)域填充算法（選學(xué)）這類算法建立在多邊形邊邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可用交互填色。該算法基于幾何求交算法，步驟如下：輸入多邊形頂點(diǎn)坐標(biāo)；求多邊形頂點(diǎn)中最大和最小y坐標(biāo)，以確定范圍；計(jì)算每條掃描線起止點(diǎn)（交點(diǎn)），并掃描填充，直至所有掃描線處理完畢。——掃描線多邊形填充算法（Scan-LineFilling）多邊形填充算法很多，這里主要介紹掃描線多邊形填充算法?！倪M(jìn)的邊相關(guān)掃描線填充算法相鄰掃描線上的交點(diǎn)與多邊形的邊相關(guān)；對(duì)同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為xi+1=xi+1/m；利用相關(guān)性可省去大量求交運(yùn)算。（具體算法參考圖形學(xué)教材）關(guān)鍵在于如何快速求掃描線與多邊形交點(diǎn)。

1）掃描線填充利用畫水平直線快速畫法提問題(為什么不用斜線)？？

2）利用掃描線與多邊形交點(diǎn)的連貫性加速求交算法（下一條掃描線交點(diǎn)可直接計(jì)算，不必解方程）算法改進(jìn)思路：思考：工程圖中的剖面線生成算法如何加速??這類算法建立在多邊形邊界的圖象數(shù)據(jù)之上，并需提供多邊形界內(nèi)一點(diǎn)的坐標(biāo)，一般用于人機(jī)交互填色，而難以用于程序自動(dòng)填色。從多邊形內(nèi)部點(diǎn)出發(fā)，沿四連通方向（或八連通方向）擴(kuò)散搜索區(qū)域內(nèi)所有待填充的象素點(diǎn)，適用于交互繪圖。算法思想：用4連通填充算法的填充結(jié)果用8連通填充算法的填充結(jié)果2）種子填色算法（SeedFilling）給定多邊形邊界顏色及內(nèi)部填充顏色；從內(nèi)部點(diǎn)(x,y)開始，檢測(cè)該點(diǎn)與邊界和填充色是否相同，均不相同則填充該點(diǎn)；檢測(cè)相鄰點(diǎn)與邊界和填充色是否相同，均不相同則填充該點(diǎn)；重復(fù)第③步直至所有象素點(diǎn)被填充。算法步驟：算法特點(diǎn)：該算法直接基于象素，用遞歸算法，不必求交。但遞歸太多，存儲(chǔ)不夠，易造成堆棧溢出。（可用一個(gè)大的矩陣記錄象素填充的狀態(tài)來避免遞歸算法）3）圖案填充算法（選學(xué)）實(shí)際應(yīng)用中，有時(shí)需要用圖案來填充平面區(qū)域，只需將種子填充算法中寫象素的那部分代碼修改。（種子點(diǎn)顏色改寫為定義圖案對(duì)應(yīng)點(diǎn)顏色查表即可）定義填充圖案：定義一個(gè)M×N的位圖，并用數(shù)組存放。M、N常比需要填充區(qū)域尺寸小得多（8×8、16×16等），圖案設(shè)計(jì)成周期性的，使之重復(fù)使用構(gòu)成任意尺寸圖案。算法思路：例：磚墻圖案定義圖案定位方法相對(duì)定位法：把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊；當(dāng)被填充的多邊形移動(dòng)時(shí)，圖案也跟著移動(dòng)，看起來比較自然；對(duì)于多邊形，可取邊界上最左邊的頂點(diǎn)，對(duì)于圓和橢圓這樣具有光滑邊界的區(qū)域，最好取區(qū)域內(nèi)部某一點(diǎn)，如取中心與圖案原點(diǎn)對(duì)齊。絕對(duì)定位法：把圖案原點(diǎn)與屏幕原點(diǎn)對(duì)齊。將整個(gè)屏幕看成被要填充的圖案布滿，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來，其它區(qū)域?qū)Υ藞D案卻是不透明的，圖案被全部擋住。這種方法比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無縫連接的效果。但它有一個(gè)潛在的缺點(diǎn)，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)，其效果是區(qū)域內(nèi)的圖案變了。2.6、圖形反走樣算法（選學(xué)）反走樣基本概念：

在光柵顯示器上顯示圖形時(shí)，直線段或圖形邊界或多或少會(huì)呈鋸齒狀。原因是圖形信號(hào)是連續(xù)的，而在光柵顯示系統(tǒng)中，用來表示圖形的卻是一個(gè)個(gè)離散的象素。這種用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)；用于減少或消除這種效果的技術(shù)稱為反走樣(antialiasing)。光柵圖形的走樣現(xiàn)象：

階梯狀邊界，如圖(a)所示，畫出的直線邊界實(shí)際上是階梯狀；

圖形細(xì)節(jié)失真（比象素更窄的細(xì)節(jié)變寬，如圖(b)）；

狹小圖形遺失（如圖(c)，在動(dòng)畫序列中將時(shí)隱時(shí)現(xiàn)，產(chǎn)生閃爍）。圖(a)圖(b)圖(c)因?yàn)橛?jì)算機(jī)屏幕是不連續(xù)的離散象素組成，每個(gè)象素覆蓋一定面積，而每個(gè)象素只能顯示一種顏色。也就是說，該象素只能顯示該覆蓋區(qū)域某一點(diǎn)處的顏色，不可能反映整個(gè)區(qū)域顏色，于是出現(xiàn)失真或圖形丟失。常用的反走樣方法主要有：提高分辨率、區(qū)域采樣、加權(quán)區(qū)域采樣等。提高分辨率方法

方法簡(jiǎn)單，代價(jià)大。如顯示器水平與豎直分辯率提高1倍，則顯示器點(diǎn)距減1倍，幀緩存容量則增加到原來的4倍，掃描轉(zhuǎn)換同樣大小的圖元卻要花4倍時(shí)間。思考問題：數(shù)碼相機(jī)照片也存在走樣問題，分析走樣的主要因素有哪些??區(qū)域采樣反走樣方法1）將直線段看作具有一定寬度的狹長矩形；2）直線段與某象素有交（或覆蓋）時(shí)，求相交（或覆蓋）區(qū)域面積；3）根據(jù)相交區(qū)域面積，確定該象素的亮度值加權(quán)區(qū)域采樣方法A'

從開發(fā)CAD軟件角度而言，基本圖形生成算法可以自己編程實(shí)現(xiàn)，但受編程人員能力的制約。目前許多商業(yè)化CAD軟件的基本圖形生成算法均采用標(biāo)準(zhǔn)的圖形庫軟件。典型的圖形庫中的基本函數(shù)用來描述圖元（直線、多邊形、球面、立體圖形及其他對(duì)象）、設(shè)定顏色、進(jìn)行旋轉(zhuǎn)或其他變換等。通用圖形程序設(shè)計(jì)軟件包有OpenGL、VRML、DirectX、Java2D和Java3D等。由于圖形函數(shù)庫提供了程序設(shè)計(jì)語言（如C++）和硬件之間的接口，所以這一組圖形函數(shù)稱為計(jì)算機(jī)圖形應(yīng)用編程接口。如果使用C＋＋編寫應(yīng)用程序時(shí)，可以使用圖形函數(shù)進(jìn)行組織并在輸出設(shè)備上顯示圖形。2.7、基于OpenGL圖形庫生成圖形（選學(xué)）基于VC++的OpenGL編程

當(dāng)前，OpenGL是用于開發(fā)簡(jiǎn)捷的交互式二維和三維圖形應(yīng)用程序的最佳環(huán)境，任何高性能的圖形應(yīng)用程序，從3D動(dòng)畫、CAD輔助設(shè)計(jì)到可視化訪真，都可以利用OpenGL高質(zhì)量、高性能的特點(diǎn)。OpenGL自1992年出現(xiàn)以來，逐漸發(fā)展成為一個(gè)開放的，獨(dú)立于應(yīng)用平臺(tái)的圖形標(biāo)準(zhǔn)，OpenGL應(yīng)用程序可以在任何平臺(tái)上運(yùn)行，只需要使用目標(biāo)系統(tǒng)的OpenGL庫重新編譯一下。雖然微軟有自己的三維編程開發(fā)工具DirectX，但它也提供OpenGL圖形標(biāo)準(zhǔn)，因此，OpenGL可以在微機(jī)中廣泛應(yīng)用。

OpenGL圖形庫除了提供基本的點(diǎn)、線、多邊形的繪制函數(shù)外，還提供了復(fù)雜的三維物體，如球、錐、多面體、茶壺以及復(fù)雜曲線和曲面。為此，本節(jié)簡(jiǎn)單介紹OpenGL在VisualC++6.0開發(fā)環(huán)境中的編程實(shí)現(xiàn)。OpenGL的基本圖元

任何復(fù)雜的三維模型都是由基本的幾何圖元：點(diǎn)、線段和多邊形組成的，有了這些圖元，就可以建立比較復(fù)雜的模型。OpenGL圖元是抽象的幾何概念，不是真實(shí)世界中的物體，因此須用相關(guān)的數(shù)學(xué)模型來描述。所有的圖元都是由一系列有順序的頂點(diǎn)集合來描述的。

OpenGL中繪制幾何圖元，必須使用glBegain()和glEnd()這一對(duì)函數(shù)，傳遞給glBegain()函數(shù)的參數(shù)唯一確定了要繪制何種幾何圖元，同時(shí)，在該函數(shù)對(duì)中給出了幾何圖元的定義，函數(shù)glEnd()標(biāo)志頂點(diǎn)列表的結(jié)束。下面的代碼繪制了一個(gè)多邊形：

glBegin(GL_POLYGON);

glVertex2f(0.0,0.0);

glVertex2f(0.0,3.0);

glVertex2f(3.0,3.0);

glVertex2f(4.0,1.5);

glVertex2f(3.0,0.0);

glEnd();GL_POLYGON為多邊形圖元類型，其它類型見上表OpenGL的基本工作流程

根據(jù)這個(gè)流程歸納出在OpenGL中渲染繪制出三維圖形的基本步驟：

1）根據(jù)基本圖形單元建立景物模型，并且對(duì)所建立的模型進(jìn)行數(shù)學(xué)描述（OpenGL中把點(diǎn)、線、多邊形、圖像和位圖都作為基本圖形單元）；

2）把景物模型放在三維空間中的合適的位置，并且設(shè)置視點(diǎn)（viewpoint）以觀察所感興趣的景觀；

3）計(jì)算模型中所有物體的色彩，其中的色彩根據(jù)應(yīng)用要求來確定，同時(shí)確定光照條件、紋理粘貼方式等；

4）把景物模型的數(shù)學(xué)描述及其色彩信息轉(zhuǎn)換至計(jì)算機(jī)屏幕上顯示。例：在黑色的背景下繪制一個(gè)彩色的填充三角形#include<stdlib.h>

#include<GL/glut.h>

voidbackground(void)

{

glClearColor(0.0,0.0,0.0,0.0);//設(shè)置背景顏色為黑色

}

voidmyDisplay(void)

{

glClear(GL_COLOR_BUFFER_BIT);//buffer設(shè)置為顏色可寫

glBegin(GL_TRIANGLES);//開始畫三角形

glShadeModel(GL_SMOOTH);//設(shè)置為光滑明暗模式

glColor3f(1.0,0.0,0.0);//設(shè)置第一個(gè)頂點(diǎn)為紅色

glVertex2f(-1.0,-1.0);//設(shè)置第一個(gè)頂點(diǎn)的坐標(biāo)為（-1.0，-1.0）

glColor3f(0.0,1.0,0.0);//設(shè)置第二個(gè)頂點(diǎn)為綠色

glVertex2f(0.0,-1.0);//設(shè)置第二個(gè)頂點(diǎn)的坐標(biāo)為（0.0，-1.0）

glColor3f(0.0,0.0,1.0);//設(shè)置第三個(gè)頂點(diǎn)為藍(lán)色

glVertex2f(-0.5,1.0);//設(shè)置第三個(gè)頂點(diǎn)的坐標(biāo)為（-0.5，1.0）

glEnd();//三角形結(jié)束

glFlush();//強(qiáng)制OpenGL函數(shù)在有限時(shí)間內(nèi)運(yùn)行

}（續(xù)前）voidmyReshape(GLsizeiw,GLsizeih)

{

glViewport(0,0,w,h);//設(shè)置視口

glMatrixMode(GL_PROJECTION);//指明當(dāng)前矩陣為