第三章圖形的基本算法.本章內(nèi)容3.1圖形的表示3.2圖形模式與坐標(biāo)系3.3直線的掃描轉(zhuǎn)換3.4圓的生成算法3.5多邊形的填充.計算機(jī)圖形學(xué)是一門復(fù)雜而又多樣化的技術(shù)。要想了解這項技術(shù)必須把它分成幾個易于操作的部分。圖形是計算機(jī)圖形學(xué)的關(guān)鍵概念，處理圖形我們應(yīng)考慮以下問題：1.如何在計算機(jī)中表示圖形？2.如何準(zhǔn)備圖形的數(shù)據(jù)？3.如何顯示準(zhǔn)備好的圖形？4.如何實現(xiàn)人與圖形的交互？3.1圖形的表示.這里，圖形是一個廣義的概念，凡是可以在圖形設(shè)備上輸出的點、線、文本等的集合都可以稱為是圖形。.兩類圖形：線條圖形和點陣圖形。無論是哪一類，點是圖形的基本幾何元素。例如四邊形，可以用四個角點表示，生成時用直線順序連接四個角點。再例如曲線，也是由曲線上的點或控制多邊形定義或曲線方程定義，通常用短直線逼近表示。3.1.1圖形的表示方法.線條圖形和點陣圖形..3.1.2表示圖形的數(shù)據(jù)準(zhǔn)備圖形最終是由點和如何表示這些點的繪圖算法表示的。這些信息在顯示以前一般存儲在數(shù)據(jù)庫文件中，復(fù)雜的算法不僅數(shù)據(jù)庫文件復(fù)雜，其存取算法也復(fù)雜。這些復(fù)雜數(shù)據(jù)庫中的數(shù)據(jù)以各種方式組織在一起。例如，環(huán)結(jié)構(gòu)、二叉樹結(jié)構(gòu)、鏈表結(jié)構(gòu)、四叉樹結(jié)構(gòu)等等。這些結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)庫文件包含指針、子結(jié)構(gòu)和其他非圖的數(shù)據(jù)。.數(shù)據(jù)庫及其存取算法是當(dāng)前的一個研究領(lǐng)域。許多計算機(jī)圖形的應(yīng)用只是一些簡單圖形，這些圖形的數(shù)據(jù)結(jié)構(gòu)比較簡單，設(shè)計很容易。如線性表、鏈表，這些簡單數(shù)據(jù)結(jié)構(gòu)也可以應(yīng)付一些比較復(fù)雜的圖形。數(shù)據(jù)結(jié)構(gòu)是一門計算機(jī)專業(yè)的課程，我們將在第六章介紹。這一章介紹圖形的基本算法。.3.1.3圖形的顯示顯示的圖形分為二維和三維兩種。二維圖形比較簡單，通常只需要做平移和比例等變換。最簡單只需作平移變換。例如，畫圓程序：PrivateSubForm_click()’畫圓

Scale(0,0)-(1600,1200)pi=3.14159x0=800:y0=600:r=100:n=36Fori=0Ton’循環(huán)

ang=i*2/n*pi’圓心角

x=x0+r*Cos(ang)y=y0-r*Sin(ang)Ifi=0ThenPSet(x,y),RGB(255,255,0)ElseLine-(x,y),RGB(255,255,0)EndIfNextiEndSub.三維圖形的顯示通常要經(jīng)過三維裁剪、旋轉(zhuǎn)、平移、比例和投影變換及消隱、明暗處理。如果是線條圖形，則一般不需明暗處理。比較簡單的三維圖形顯示不需裁剪，這時所有圖形都顯示。.3.2圖形模式和坐標(biāo)系利用TurboC顯示圖形之前，必須先進(jìn)入圖形模式。進(jìn)入圖形模式的函數(shù)原形為：voidfarinitgraph（intfar*drive，intfar*mode，charfar*path）；VB為Scale(0,0)-(1600,1200)’設(shè)置圖形模式.屏幕坐標(biāo)系屏幕上每個象素根據(jù)它們的x，y坐標(biāo)確定進(jìn)入圖形模式之后，缺省的坐標(biāo)系原點（0，0）在屏幕左上角。(0,0)(1600,1200)xy.平移變換和比例變換采用如下的變換方法

Vx=x0+Wx;Vy=y0-Wy;則將原數(shù)學(xué)坐標(biāo)系中的圖形按原坐標(biāo)軸的方向畫到屏幕的合適位置。Vx，Vy為變換后坐標(biāo)；Wx，Wy為原數(shù)學(xué)坐標(biāo)系坐標(biāo)。

(x0,y0)VyVx.3.3直線的掃描轉(zhuǎn)換光柵掃描顯示器不是畫線設(shè)備，而是畫點設(shè)備，它不能精確的在兩點之間畫一條直線，而是由靠近這條直線的象素點表示。直線算法追求的目標(biāo)：選擇直線的最佳光柵位置。直線的掃描轉(zhuǎn)換算法有幾種，我們只介紹兩種：DDA算法和Bresenham算法。.怎樣選擇直線的最佳光柵位置（象素點），是Bresenham算法追求的目標(biāo)。為此，算法根據(jù)直線的斜率在計長方向（x或y）上，每次都遞增一個單位步長即一個象素單位，另一個方向的增量為0或1。這種算法的巧妙之處是只需檢查判別式的符號即可，而且計算量很小，只進(jìn)行整型數(shù)計算，不必做舍入操作。直線的Bresenham算法.

數(shù)學(xué)坐標(biāo)系下的直線近似表示屏幕坐標(biāo)系下的直線近似表示直線的近似表示.八分圓域12348765x.Bresenham算法的幾何原理(x2,y2)(x1,y1).先假設(shè)直線位于第一個八分圓域，即斜率在0~1之間。設(shè)（xi-1,yi-1）是已經(jīng)選定的離直線最近的象素點，現(xiàn)在要決定下一個象素點是Ti(xi,yi)還是Si(xi,yi-1)。不難看出，不論下一象素點是Ti還是Si

，x方向都增1，即xi=xi-1+1，要決定的是y方向是否增1。由圖不難看出：.現(xiàn)在需要一個判別式，來判斷每一步是選Ti還是選Si。下面導(dǎo)出Bresenham算法的判別式。若s<t，則Si較靠近理論直線，應(yīng)選Si，y不變；若s>t，則Ti較靠近理論直線，應(yīng)選Ti，y增1。.設(shè)一直線段由（x1,y1）至（x2,y2），（其中y2>y1，x2>x1）則直線方程可表示為式中經(jīng)變換后直線可表示為從（0，0）到（dx,dy），此時直線方程可簡化為判別式的導(dǎo)出.Si的坐標(biāo)為(xi-1+1,yi-1)，Ti的坐標(biāo)為(xi-1+1,yi-1+1)。因此.因dx>0，所以我們可以以dx(s-t)的正負(fù)作為選擇點的依據(jù)。若令其為di，則.這樣，我們就得到一個遞推公式，下一個di+1就可以由前一個di遞推得到。因xi-xi-1=1，所以當(dāng)di>=0時，選Ti。這時y方向增1，即yi-yi-1=1，因此當(dāng)di<0時，選Si。這時yi=yi-1，則.Bresenham算法的遞推公式+=dyddii+21dxdyddi-=21的初值：Sdii<0，此時時，選dxdyddii+=+1)-2(Tdii30，此時時，選.Bresenham算法的一般情況上式只包含加減法和左移(乘2)的運算,而且下一象素點的選擇只需檢查di的符號，因此Bresenham算法很簡單，速度也相當(dāng)快。.上面我們討論的直線位于第一八分圓域內(nèi)，即直線的斜率為0~1的情況。對于一般情況可作如下處理。1.當(dāng)斜率的絕對值大于1時，將dx和dy對換，即以y向作為計長方向，且總是增1(或減1)，x是否增減則根據(jù)di的符號：di0時，y增1（或減1）；di

0時，x不變。2.根據(jù)dx和dy的符號來控制x（或y）增1還是減1。一般情況的處理.x=x1:y=y1dx=Abs(x2-x1):dy=Abs(y2-y1)s1=Sgn(x2-x1):s2=Sgn(y2-y1)Ifdy>dxThenCallswaps(dx,dy)interchange=1Elseinterchange=0EndIfd=2*dy-dxFori=1TodxPSet(x,y),RGB(255,255,255)Whiled>=0Ifinterchange=1Thenx=x+s1Elsey=y+s2EndIfd=d-2*dxWendIfinterchange=1Then.

y=y+s2Elsex=x+s1EndIfd=d+2*dyNexti問題：為什么當(dāng)d>=0時，d=d-2*dx而不是d=d+2*(dy-dx)。答：因后面的d=d+2*dy總是執(zhí)行，已經(jīng)將2*dy加上了。.SubBresenhan_circle(xcAsInteger,ycAsInteger,rAsSingle)DimxAsInteger,yAsIntegery=r:d=3-2*rx=0While(x<=y)CallplotC(x,y,xc,yc)Ifd<0Thend=d+4*x+6Elsed=d+4*(x-y)+10y=y-1EndIfx=x+1WendEndSub.SubplotC(xAsInteger,yAsInteger,xcAsInteger,ycAsInteger)PSet(xc+x,yc+y),RGB(255,255,255)PSet(xc+x,yc-y),RGB(255,255,255)PSet(xc-x,yc+y),RGB(255,255,255)PSet(xc-x,yc-y),RGB(255,255,255)PSet(xc+y,yc+x),RGB(255,255,255)PSet(xc+y,yc-x),RGB(255,255,255)PSet(xc-y,yc+x),RGB(255,255,255)PSet(xc-y,yc-x),RGB(255,255,255)EndSub.X1=x(i)*Cos(agl1)-y(i)*Sin(agl1)Y1=x(i)*Sin(agl1)+y(i)*Cos(agl1).例3-1：用Bresenham直線算法計算從（0,1）到（4,3）線段的每一個像素的位置，并畫出。選擇T1點.選擇S2點選擇T3點選擇S4點.dxy01012-422033-443.介紹兩種算法：正多邊形逼近和Bresenham算法3.4.1正多邊形逼近算法3.4.2圓的Bresenham算法3.4圓的生成算法.其基本思想是：當(dāng)一個正多邊形的邊數(shù)足夠大時，則以此正多邊形代替它的外接圓。正多邊形的邊可用Bresenham算法生成。3.4.1正多邊形逼近算法.正多邊形逼近算法的改進(jìn)算法.3.4.2圓的Bresenham算法.上述的多邊形逼近算法必須用實型數(shù)運算，而Bresenham算法只需進(jìn)行整數(shù)運算，效率高，效果好。設(shè)圓心為P(xc,yc)，半徑為r，則圓的方程為下面以順時針生成1/8圓弧為例推導(dǎo)Bresenham算法，其它圓域的點可通過對稱變換得到，如圖3.6所示。.與直線的Bresenham算法類似，圓的Bresenham算法也是在每一步考察兩個可能的象素點中哪一個更靠近理論圓周，從而推出沿圓周的整數(shù)位置。.圓的Bresenham算法.圓的Bresenham算法為簡便，先將圓心平移Pc(xc,yc)到原點(0,0)算法沿x方向每次都遞增1個單位，y是否減1，要根據(jù)判別式的符號。算法從x=0開始，到x=y結(jié)束。起點坐標(biāo)為（0,r）。.圓的Bresenham算法算法中用的三個公式講義中給出了該算法的C程序。.3.4.3橢圓的掃描轉(zhuǎn)換以離心角為參數(shù)，橢圓的參數(shù)方程此方程生成長短軸在垂直和水平的位置的橢圓。如希望在任意位置，可進(jìn)行旋轉(zhuǎn)變換。由此生成橢圓速度較慢，可仿照圓的正多邊形逼近算法推出遞推算法。請大家自己考慮。.取第一象限的橢圓弧為例。設(shè)橢圓中心在坐標(biāo)原點，其方程為寫成隱式橢圓的Bresenham算法.由于橢圓的特殊性，我們進(jìn)一步將第一象限的橢圓弧分為兩段：上段和下段。以弧上斜率為-1的點作為分界點。為此，求出橢圓上一點處的法向量為即當(dāng)時為分界點。因此，可以由法向量的的分量來控制x和y方向的變化。.橢圓的分段.上半段.3.5多邊形的填充多邊形填充也稱多邊形的掃描線轉(zhuǎn)換。多邊形是構(gòu)成平面圖形的幾何元素，也可以是構(gòu)成三維物體的表面的投影。如果物體的表面是曲面，也可由適當(dāng)?shù)亩噙呅稳ケ平?。因此，多邊形填充是處理二、三維圖形的基本算法。.3.5多邊形的填充在一點一點填充多邊形的之前，算出每一點的光強或色彩，以此來決定該點的顏色。這就是所謂的明暗處理（shading)，具有真實感的圖形就是這樣繪制出來的。有多種填充多邊形的算法，通?？砂阉鼈兎譃閮纱箢悾簰呙柁D(zhuǎn)換算法和種子填充算法。.3.5多邊形的填充掃描轉(zhuǎn)換算法是按掃描線的順序確定其上的某一點是否位于多邊形范圍之內(nèi)。算法一般是從多邊形“頂部”開始進(jìn)行到它的“底部”。.3.5多邊形的填充種子填充算法首先假定封閉多邊形內(nèi)某點是已知的，然后算法開始搜索與種子點相鄰且位于多邊形內(nèi)的點。如果相鄰點不是位于多邊形內(nèi)，那么就達(dá)到多邊形的邊界。如果相鄰點位于多邊形以內(nèi)，那么這一點就成為新的種子點，然后繼續(xù)遞歸地搜索下去，直到到達(dá)邊界。種子填充算法只適用于光柵掃描設(shè)備。.3.3.1多邊形的掃描轉(zhuǎn)換.3.3.1多邊形的掃描轉(zhuǎn)換1.求交點設(shè)某條邊為斜邊，其兩個端點分別為P1(x1,y1)和P2(x2,y2)，則其參數(shù)方程掃描線代入上式得交點的坐標(biāo).當(dāng)時，掃描線與P1P2確實有一個交點（xs,ys）。否則交點在P1P2延長線上。.2.簡單的掃描線算法.掃描線轉(zhuǎn)換算法適用于封閉的簡單多邊形，通常將頂點定義的多邊形及其內(nèi)部用指定的象素予以填充。掃描線6與多邊形有4個交點，把多邊形分為五段2.簡單的掃描線算法.2.簡單的掃描線算法.掃描線6上的交點并不一定按自左至右的順序求出，若多邊形頂點逆時針順序給出，掃描線6與多邊形的交點就按7，3.5，2，11的順序求出。然后按的遞增順序?qū)ζ渑判?，即?，3.5，7，11。2.簡單的掃描線算法.在確定掃描線上象素的光強或顏色時，需要將經(jīng)過排序的交點配對，每對交點所確定的區(qū)間均取多邊形的光強或顏色，交點對之間的區(qū)間則取背景光強或顏色。顯然，從掃描線起點到第一個交點之間以及從最后一個交點到掃描線終點之間也應(yīng)取成背景光強或顏色。2.簡單的掃描線算法.特殊問題的解決在填充過程中，還有兩個特殊問題需要解決：一是當(dāng)掃描線恰好與多邊形相交時，交點的計數(shù)問題；二是多邊形邊界上象素的取舍問題。前者保證交點的正確配對，后者避免多邊形填充的擴(kuò)大化。.特殊問題的解決先解決交點的計數(shù)問題：當(dāng)掃描線與多邊形交于多邊形的局部最高點或局部最低點時，交點應(yīng)計為零個或兩個，否則計為一個。具體實現(xiàn)時，只需檢查交于該頂點的兩條邊另外兩個頂點的y值。按這兩個y值中大于交點y值的個數(shù)是0，1，2來決定是計零個，一個還是兩個。.邊界上象素的取舍對左下角為(1，1)，右上角為(4，3)的矩形填充時，若對邊界上所有象素都進(jìn)行填充，被填充的面積覆蓋4×3=12個單位，而實際面積應(yīng)為3×2=6個單位，.邊界上象素的取舍為了解決這個問題，規(guī)定右、上邊界的象素不予填充，只填充左、下邊界。具體實現(xiàn)時，只要對掃描線與多邊形的相交區(qū)間采用左閉右開的原則即可。顯然，下閉上開的原則已由第一個問題的處理方法所保證。.3.使用活化邊表的算法在計算每條掃描線與多邊形各邊的交點時，最簡單的方法是把多邊形所有的邊都放在一個邊表中。在處理每條掃描線時，按順序從表中取出每條邊與掃描線試求交點。但真正與當(dāng)前掃描線相交的往往只有少數(shù)的幾條邊，其它的處理都是無用的，白白浪費了時間。為避免不必要的求交，采用活化邊表。.一條掃描線只與幾個多邊形相交.活化邊表的算法為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進(jìn)行求交。為此要為這些邊建立一個鏈表。我們把與當(dāng)前掃描線相交的邊稱為活化邊，對應(yīng)的把為它們所建立的鏈表稱為活化邊表?；罨叡淼拿總€結(jié)點存放著對應(yīng)邊的有關(guān)信息：如掃描線與該邊交點的x坐標(biāo)；邊所跨的掃描線條數(shù)(Δy)或較低端點的y坐標(biāo)ymin等。

.活化邊表的算法在掃描轉(zhuǎn)換的過程中，活化邊表中的活化邊是不斷變化的。在當(dāng)前掃描線處理完之后，要將與下一條掃描線新交上的邊置入活化邊表，而將活化邊表中那些不再與下一條掃描線相交的邊從活化邊表中刪除。例如掃描線5和4。.掃描線5和4的活化邊表.利用連續(xù)性求交點預(yù)先求出每條掃描線與多邊形的交點即費時又需要大量的空間去存儲它們。容易看出，多邊形的邊和掃描線都具有連貫性（連續(xù)性），利用這個性質(zhì)可簡化求交的計算，而且不必事先求出交點，從而節(jié)省了大量的存儲空間。.假定當(dāng)前掃描線y=yi與多邊形的某條邊交點x的坐標(biāo)為xi，則下一條掃描線y=yi+1=yi-1與該邊交點的x坐標(biāo).dx可以存放在活化邊表中對應(yīng)邊的結(jié)點中。另外，還需知道何時不再與下一條掃描線相交。因此，活化邊表中的每個結(jié)點至少為對應(yīng)邊保存如下內(nèi)容：x：當(dāng)前掃描線與多邊形邊的交點；dx(Δx)：當(dāng)前掃描線到下一條掃描線之間的增量；ymin：該邊所交的最低掃描線的坐標(biāo)；next：指向下一條邊的指針。每個結(jié)點所保存的內(nèi)容.y桶的建立為了便于建立活化邊表和置入新邊，我們?yōu)樗袙呙杈€和多邊形的邊各建立一個表。為掃描線建的表稱為y桶，為多邊形建的表稱為數(shù)據(jù)鏈表，如圖所示。y桶的值為掃描線的y坐標(biāo)，它對應(yīng)著新交上邊的結(jié)點。.新y桶及數(shù)據(jù)鏈表.y桶表是一個一維數(shù)組，數(shù)組的每個元素對應(yīng)一條掃描線，每條掃描線的數(shù)組元素只含一個簡單指針，指向相應(yīng)的數(shù)據(jù)鏈表數(shù)組,如圖所示。數(shù)據(jù)鏈表采用二維數(shù)組，每行對應(yīng)4個元素：多邊形邊與它所通過的最高掃描線交點的x值；該多邊形邊與相鄰掃描線之間的增量dx；多邊形邊較低端點的y坐標(biāo)ymin；以及指向位于這條掃描線的下一條邊的數(shù)據(jù)行的鏈接指針next。新y桶及數(shù)據(jù)鏈表.掃描線轉(zhuǎn)換算法綜上所述，采用活化邊表的多邊形掃描線算法如下。1.數(shù)據(jù)的準(zhǔn)備工作(1)建立y桶和數(shù)據(jù)鏈表對于多邊形的每條邊求出與其相交的最高掃描線，即每條邊較高端點的y坐標(biāo)ymax，并把該多邊形的邊存入與這條掃描線對應(yīng)的y桶，以下簡稱舊y桶。.把最初交點的x（即較高端點的x坐標(biāo)），（邊斜率的負(fù)倒數(shù)）及較低端點的y坐標(biāo)ymin存入數(shù)據(jù)鏈表，以下簡稱舊數(shù)據(jù)鏈表。（2）形成新的y桶表和數(shù)據(jù)鏈表對每條掃描線，當(dāng)所對應(yīng)的舊y桶非空時，將其中各邊的數(shù)據(jù)從舊數(shù)據(jù)鏈表移入新數(shù)據(jù)鏈表，并建立指針域，對應(yīng)的新y桶指向第一條邊。繼續(xù)下去，直至所有的掃描線都處理完。.新y桶和新數(shù)據(jù)鏈表建立后應(yīng)將舊y桶和舊數(shù)據(jù)鏈表刪除，以釋放它們所占用的空間。.建立活化邊表數(shù)據(jù)鏈表和活化邊表都是一個單向鏈表，采