圖形學基本圖元

圖形學基本圖元第1頁，課件共91頁，創(chuàng)作于2023年2月引言什么是基本圖元？基本圖元，即基本圖形元素，指圖形系統(tǒng)能夠產生的最基本的圖形包括點、直線、圓、圓弧、區(qū)域填充、字符等這些圖形元素是生成復雜圖形圖像的基礎也稱為圖形基元，或輸出圖形元素第2頁，課件共91頁，創(chuàng)作于2023年2月

光柵圖形顯示器可以看作一個像素的矩陣，每個像素可以用一種或多種顏色顯示；在光柵顯示器上顯示任何圖形，實際上都是一些具有一種或多種顏色的像素的集合！光柵圖形學主要研究內容：直線、圓弧、多邊形的掃描轉換算法區(qū)域填充、字符、裁剪、反走樣、消隱等光柵圖形學顯示的圖形←→像素的集合第3頁，課件共91頁，創(chuàng)作于2023年2月掃描轉換將圖形描述轉換成用像素矩陣表示的過程每次的圖形改變都要進行掃描轉換，因此高效快速的掃描轉換算法顯得尤為重要！在選擇算法時，計算速度與圖形質量的權衡折中是一個基本問題！圖形描述→像素矩陣第4頁，課件共91頁，創(chuàng)作于2023年2月§3基本圖元的生成§3-1直線的掃描轉換算法DDA畫線算法中點畫線算法Bresenham畫線算法§3-2圓的掃描轉換算法中點畫圓算法Bresenham畫圓算法§3-3區(qū)域填充算法第5頁，課件共91頁，創(chuàng)作于2023年2月§3-1直線的掃描轉換算法直線的掃描轉換確定最佳逼近于該直線的一組像素按掃描線的順序，對這些像素進行寫操作此即用顯示器繪制直線，或直線的掃描轉換三個常用算法1DDA畫線算法（數值微分法）2中點畫線算法3Bresenham畫線算法第6頁，課件共91頁，創(chuàng)作于2023年2月好算法的判斷標準繪制出的線段應盡可能地逼近原直線；線的亮度應均勻且與線的方向無關；線段兩端截斷要精確；要盡可能快速地畫出整條線段！

…………第7頁，課件共91頁，創(chuàng)作于2023年2月討論的前提假設條件像素間均勻網格整型坐標系討論直線段斜率0<k<1的情況；對k＞1的情況，將x、y互換即可第8頁，課件共91頁，創(chuàng)作于2023年2月光柵圖形中點的表示每個像素由其左下角的坐標表示第9頁，課件共91頁，創(chuàng)作于2023年2月直線段的兩個端點：

P0(x0,y0)，P1(x1,y1)其直線方程為：y=kx+b…………①式其中:k=(y1-y0)/(x1-x0)

b=(x1y0-x0y1)/(x1-x0)………………②式已知條件第10頁，課件共91頁，創(chuàng)作于2023年2月最直接的畫線算法根據上述已知條件，得到直線掃描轉換最直接的算法，步驟如下：給出端點坐標P0(x0,y0)和P1(x1,y1)；利用②式，求出k和b的值；當∣k∣≤1時，利用①式進行乘法&加法運算求出y值，再取整;當∣k∣≥1時，則通過y計算x值！第11頁，課件共91頁，創(chuàng)作于2023年2月算法評價

優(yōu)點：既直觀，又可行！

缺點：效率低，計算量大（每步均包含乘法&加法運算、取整運算）作為最底層的光柵圖形算法，在CAD等圖形系統(tǒng)中會被大量應用，因此哪怕節(jié)約一個加法或減法，也是很了不起的改進！由此出發(fā)，引出了增量算法的思想！

請思考：何謂增量算法？第12頁，課件共91頁，創(chuàng)作于2023年2月一、DDA畫線算法數值微分法DDAdigitaldifferentialanalyzer基本思想已知過端點P0(x0,y0)，P1(x1,y1)的直線從直線起點P0開始，向終點P1步進：令x每步遞增1(個像素)，計算相對應的y坐標；?。▁,round(y)）作為當前點的坐標！第13頁，課件共91頁，創(chuàng)作于2023年2月基本思想第14頁，課件共91頁，創(chuàng)作于2023年2月數值微分(DDA)法

增量算法推導：其中，xi+1=xi+△x增量：當△x=1時，△y=k對應點的坐標：(xi,yi)→(xi+1,yi+k)第15頁，課件共91頁，創(chuàng)作于2023年2月DDA算法本質用數值方法解微分方程

通過同時對x和y各增加一個小增量，計算下一步的x、y的值在一個迭代算法中，如果每一步的x和y的值是用前一步的值加上一個增量來獲得，那么這種算法就稱為增量算法

DDA算法是一個增量算法！數值微分(DDA)法第16頁，課件共91頁，創(chuàng)作于2023年2月練習題—DDA法2251.6241.2130.8120.401000Y值Round(y)X值Line:P0(0,0)—P1(5,2)012345321第17頁，課件共91頁，創(chuàng)作于2023年2月DDA算法參考程序voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x≤x1,x++)

setpixel(x,int(y+0.5),color); y=y+k;

第18頁，課件共91頁，創(chuàng)作于2023年2月數值微分(DDA)法DDA算法的不足之處包含浮點數取整運算不利于硬件實現效率低僅適用于k

≤1的情形:x每增加1,y最多增加1；當k

1時，必須把x，y互換！第19頁，課件共91頁，創(chuàng)作于2023年2月引申與思考采用增量思想的DDA算法，每計算一個像素，只需計算一個加法，是否最優(yōu)？如非最優(yōu)，如何改進？

改進的目標－>

進一步將一個加法運算改進為一個整數加法運算

新思路－>DDA算法采用點斜式直線表示方式，可否采用其他的直線表示方式？第20頁，課件共91頁，創(chuàng)作于2023年2月基本思想當前像素點為(xp,yp),下一像素點為P1或P2；設M點為P1與P2之中點，Q點為理想直線與垂線x=xp+1的交點；將Q與M的y坐標進行比較：若M在Q的下方，則取P2為下一個像素點；若M在Q的上方，則取P1為下一點像素點！二、中點畫線算法第21頁，課件共91頁，創(chuàng)作于2023年2月中點法示意圖P=(xp,yp)QP2P1M第22頁，課件共91頁，創(chuàng)作于2023年2月中點畫線算法需要解決的問題判斷距離理想直線最近的下一個像素點已知條件線段兩端點(x0,y0)和(x1,y1)直線方程：F(x,y)=ax+by+c=0，其中：a=y0-y1b=x1-x0c=x0y1-x1y0第23頁，課件共91頁，創(chuàng)作于2023年2月M如何判斷M點在Q點上方還是下方？第24頁，課件共91頁，創(chuàng)作于2023年2月如何判斷M與Q的關系？構造判別式d=F(M)

=

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

其中：a=y0-y1,b=x1-x0,c=x0y1-x1y0當d<0時，M在直線(Q)下方，取P2為下一個像素當d>0時，M在直線(Q)上方，取P1為下一個像素當d=0時，選P1或P2均可，約定取P1點！由直線方程F(x,y)=ax+by+c=0M點坐標（xp+1,yp+0.5）第25頁，課件共91頁，創(chuàng)作于2023年2月MP1P2P(Xp+1,Yp+0.5)中點畫線法演示第26頁，課件共91頁，創(chuàng)作于2023年2月進一步思考上述算法，每一個像素的計算量包括加法與乘法是否也可以采用增量算法呢？由于d是xp,yp的線性函數，因此可采用增量計算，以提高運算效率！第27頁，課件共91頁，創(chuàng)作于2023年2月分兩種情形考慮再一下個像素的判定當d≥0時，M在直線上方，取正右P1(xp+1，yp)再下一個像素的判別式為d1=F((xp+1)+1,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a

第一種情況，d的增量為a！當d＜0時，M在直線下方，取右上方P2(xp+1,yp+1)再下一個像素的判別式為：d2=F((xp+1)+1,(yp+1)+0.5)=a(xp+2)+b(yp+1.5)+c=d+a+b第二種情況，d的增量為a+b！MP1P2MP1P2第28頁，課件共91頁，創(chuàng)作于2023年2月再討論d的初始值d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b=a+0.5b令：2d代替d，則d0=2a+b從而使得d的增量都是整數因為(X0,Y0)在直線上，所以F(X0,Y0)=0中點畫線法當d≥0時，△d=2a當d＜0時，△d=2(a+b)d的初始值第29頁，課件共91頁，創(chuàng)作于2023年2月優(yōu)點：只有整數運算，擺脫了小數，提高了運算效率不含乘除法，計算速度快有利于硬件實現

……留待上機驗證中點畫線法第30頁，課件共91頁，創(chuàng)作于2023年2月練習題—中點法用中點畫線法：（0，0）→（5，2）12565245-11343123-30121001dyixii012345321第31頁，課件共91頁，創(chuàng)作于2023年2月中點法參考程序voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++,y++,d+=d2;}else{x++,d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/第32頁，課件共91頁，創(chuàng)作于2023年2月三、Bresenham畫線算法引言DDA算法采用點斜式，中點法采用隱式表示中點法可以有整數算法其他表示可以推出整數算法嗎？基本思想與中點畫線法的思想類似由誤差項符號決定下一個點取正右方像素還是右上方像素第33頁，課件共91頁，創(chuàng)作于2023年2月Bresenham畫線算法基本思想比較d1和d2根據距離誤差項的符號確定與理想直線最近的像素若d1＜d2，選B點若d1≥d2，選A點AB第34頁，課件共91頁，創(chuàng)作于2023年2月Bresenham畫線算法構造判別量p=△x（d1-d2）結論初始值：p=2△y-△x增量：當p≥0時，△p=2(△y-△x)當p＜0時，△p=2△y已知條件給定端點坐標P0(x0,y0)和P1(x1,y1)則△x=x1-x0；△y=y1-y0AB第35頁，課件共91頁，創(chuàng)作于2023年2月Bresenham算法參考程序voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy，p;x=x0;y=y0;dx=x1-x0,dy=y1-y0;p=2*dy-dx;for(x=x0;xx1;x++){setpixel(x,y,color);if(p0){y++,p+=2*(dy-dx);}else{p+=2*dy;}}}第36頁，課件共91頁，創(chuàng)作于2023年2月練習題-Bresenham法已知(0,0)→(5,2)△x=5;△y=2;P初始=2△y-△x=-1△p(≥0)=2(△y-△x)=-6△p(＜0)=2△y=4-125-524113-312301-100pyx★p≥0,y加1★p＜0,y不變★第37頁，課件共91頁，創(chuàng)作于2023年2月Bresenham畫線算法優(yōu)點整數運算，速度快計算精度高乘2運算可用移位實現，適于硬件實現

……留待上機驗證第38頁，課件共91頁，創(chuàng)作于2023年2月后續(xù)展望至此，直線光柵化算法是否終結？新方法：

BRDC:binaryrepresentationofdisplacementcodeforlineMiaoLF,LiuXG,PengQS,BaoHJCOMPUTERS&GRAPHICS-UK26(3):401-408JUN2002第39頁，課件共91頁，創(chuàng)作于2023年2月§3-2圓的掃描轉換算法圓的掃描轉換在光柵網格中挑選出最靠近圓周的像素假設條件

圓心在原點，半徑為R；圓的方程：x2+y2=R2；對于圓心不在原點的圓，可以通過平移變換，化為中心在原點的圓！第40頁，課件共91頁，創(chuàng)作于2023年2月最直接的畫圓方法令x以單位步長從0增至R；求出每一步對應將y值取整從而可以得到1/4圓周！包括乘方和開方運算，效率不高在x接近R時，圓周上點間隔較大

R2-x2y=第41頁，課件共91頁，創(chuàng)作于2023年2月尋求更好的算法圓的特征八對稱性—只要能生成八分之一的圓弧，就可以得到整個圓！令x從0→求出對應y值其它點即可相應得出如何畫這1/8圓周？yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR2/R第42頁，課件共91頁，創(chuàng)作于2023年2月一、中點畫圓法當前點P(xi,yi)下一點可能是P1(xi+1,yi)P2(xi+1,yi-1)第43頁，課件共91頁，創(chuàng)作于2023年2月構造函數：F(x,y)=x2+y2-R2圓上的點，F(x,y)=0圓外的點，F(x,y)>0圓內的點，F(x,y)<0

P1和P2的中點M（xp+1,yp-0.5）d=F(M)<0時，M在圓內，取P1點

d=F(M)>0時，M在圓外，取P2點

d=F(M)=0時，P1或P2均可，約定取P2

中點畫圓法P=(xp,yp)P1P2M第44頁，課件共91頁，創(chuàng)作于2023年2月中點畫圓法判別式：若d＜0,取P1為下一像素，再下一像素的判別式為若d≥0,取P2為下一像素，再下一像素的判別式為222)5.0()1()5.0,1()(RyxyxFMFdpppp--++=-+==32)5.0()2()5.0,2('222++=--++=-+=pppppxdRyxyxFd5)(2)5.1()2()5.1,2('222+-+=--++=-+=ppppppyxdRyxyxFd第45頁，課件共91頁，創(chuàng)作于2023年2月中點畫圓法設初始像素是P0（0，R）判別式d的初值為d0=F（1，R-0.5）=1.25-R設當前點為P（xp，yp）,則下一點的選擇當d＜0時,取P1為下一像素，且△d=2xp+3當d≥0時,取P2為下一像素，且△d=2(xp-yp)+5第46頁，課件共91頁，創(chuàng)作于2023年2月中點畫圓法參考程序voidMidpointCircle(intR){intx,y;doubled; x=0;y=R;d=1.25-R; SetPixel(x,y); while(x<y) {if(d<0){d+=2*x+3;x++;

} else{d+=2*(x-y)+5;x++;y--; } SetPixel(x,y); }}第47頁，課件共91頁，創(chuàng)作于2023年2月改進—中點法為了進一步提高算法的效率，可以將上述算法中的浮點數改寫成整數，將乘法運算改成加法運算，即僅用整數實現中點畫圓法改進措施：令e=d-0.25代替d初始值：e0=1-Re初始值為整數，運算中增量也為整數再次改進：只有整數運算，且不含乘法第48頁，課件共91頁，創(chuàng)作于2023年2月中點畫圓法參考程序（改進）voidMidpointCircle2(intR){intx,y,deltax,deltay,d; x=0;y=R;d=1-R;deltax=3;deltay=5-R-R; SetPixel(x,y); while(x<y) {if(d<0) {d+=deltax;deltax+=2;x++;

} else {d+=(deltax+deltay);deltax+=2;deltay+=2; x++;y--;} SetPixel(x,y); }}第49頁，課件共91頁，創(chuàng)作于2023年2月二、Bresenham畫圓算法

在0≤x≤y的1/8圓周上，像素坐標x值單調增加，y值單調減少。設：第i步已確定（xi,yi）是要畫圓上的像素點，看第i+1步像素點（xi+1,yi+1）應如何確定：可能是(xi+1,yi)可能是(xi+1,yi-1)第50頁，課件共91頁，創(chuàng)作于2023年2月21)i(y21)i(x2RDd2R2iy21)i(xHd--+-=-++=判別量Bresenham畫圓法第51頁，課件共91頁，創(chuàng)作于2023年2月Bresenham畫圓法若精確圓弧是③則dH>0和dD>0若pi<0，即dH<dD應選H點若pi≥0，即dH≥dD應選D點若精確圓弧是①或②，顯然H是應選擇點此時dH≤0，dD>0，必有pi<0若精確圓弧是④或⑤，顯然D是應選擇點此時dH>0，dD≤0，必有pi>0結論：pi做判別量：當pi＜0時，選H點為下一個像素點當pi≥0時，選D點為下一個像素點第52頁，課件共91頁，創(chuàng)作于2023年2月voidBresenhamCircle(intR){intx,y,p; x=0;y=R;p=3-2*R; for(;x<=y;x++) {SetPixel(x,y); if(p>=0) {p+=4*(x-y)+10;y--;}else {p+=4*x+6; } }}Bresenham算法參考程序第53頁，課件共91頁，創(chuàng)作于2023年2月

只需修改語句SetPixel(x,y)，畫八個對稱的點，即可畫出整個圓；若加一個平移變換，就可以畫出圓心在任意位置的圓！圓的完成第54頁，課件共91頁，創(chuàng)作于2023年2月§3-3區(qū)域填充算法區(qū)域填充本節(jié)將討論如何用一種顏色或圖案來填充一個二維區(qū)域需要討論的兩個問題確定需要填充哪些像素確定用什么顏色或圖案來填充第55頁，課件共91頁，創(chuàng)作于2023年2月區(qū)域填充算法

填充算法

掃描線填充算法

按照掃描線順序

種子填充算法

從區(qū)域內部的一個點出發(fā)第56頁，課件共91頁，創(chuàng)作于2023年2月一、掃描線填充算法多邊形域的填充

這里討論的多邊形可以是凸多邊形、凹多邊形，或者是含內環(huán)的多邊形！第57頁，課件共91頁，創(chuàng)作于2023年2月掃描線填充算法算法的基礎一條直線與任意封閉的曲線相交時，總是從第一個交點進入內部，再從第二個交點退出即奇數次進入，偶數次退出算法的思想按照掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用指定顏色顯示這些區(qū)間的像素！第58頁，課件共91頁，創(chuàng)作于2023年2月算法思想以掃描線“6”為例與多邊形的邊界交于A、B、C、D四個點把掃描線劃分為五個區(qū)間①②③④⑤其中②和④落在多邊形內，該區(qū)間內像素應取填充色，其余區(qū)間的像素取背景色！0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)①②③④⑤多邊形P1P2P3P4P5P6，注意相交順序及交點排序問題第59頁，課件共91頁，創(chuàng)作于2023年2月算法填充過程1．求交計算掃描線與多邊形各邊的所有交點；2．排序按x坐標遞增順序對交點進行排序；3．交點配對第1、2個，第3、4個為一對等等，每對代表一個區(qū)間4．區(qū)間填色區(qū)間內像素置成填充色，區(qū)間外像素置成背景色第60頁，課件共91頁，創(chuàng)作于2023年2月需要注意的兩個問題問題一掃描線過頂點的情況問題二邊界上像素的取舍問題第61頁，課件共91頁，創(chuàng)作于2023年2月請分析：掃描線“2”的情況0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第62頁，課件共91頁，創(chuàng)作于2023年2月分析過程按照前述方法分析掃描線“2”的情況掃描線“2”分別與多邊形的P1P2、P2P3、P6P1邊相交交點排序后的x坐標為：2，2，8填充：區(qū)間【2，2】置為填充色不填充：區(qū)間【2，8】置為背景色從而出現異常情況！第63頁，課件共91頁，創(chuàng)作于2023年2月修正措施當掃描線與多邊形頂點相交時，相同的點只取一個！由此，掃描線“2”與多邊形交于2，8；填充區(qū)間【2，8】，從而得到期望的結果！請根據新規(guī)定再分析：掃描線“7”的情況！第64頁，課件共91頁，創(chuàng)作于2023年2月請再分析：掃描線“7”的情況0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第65頁，課件共91頁，創(chuàng)作于2023年2月分析過程根據新規(guī)定分析掃描線“7”的情況掃描線“7”分別與多邊形的P3P4、P4P5、P5P6、P6P1邊相交交點排序后的x坐標為：2，9，11填充：區(qū)間【2，9】置為填充色不填充：區(qū)間【9，11】置為背景色從而，又出現異常情況！第66頁，課件共91頁，創(chuàng)作于2023年2月解決問題一針對掃描線過頂點的情況，如何進行交點的取舍？情況1：共享頂點的兩邊分別落在掃描線的兩邊交點只算一個！情況2：共享頂點的兩邊落在掃描線的同一邊交點取為零個或兩個！具體實現時：檢查頂點所在兩條邊的另外兩外端點的y值；按照兩個y值大于交點處y值的個數是0，1，2

…來決定取交點個數是0，1，2個第67頁，課件共91頁，創(chuàng)作于2023年2月結論對于局部最高點→取0個交點例如：P6對于局部最低點→取2個交點例如：P2、P5對其它點→取1個交點例如：P1第68頁，課件共91頁，創(chuàng)作于2023年2月問題二：邊界像素的取舍問題請?zhí)畛鋱D中的矩形區(qū)域P1P2P3P4

請分析

請仔細觀察填充結果存在什么問題012345671234567yxP1P2P3P4第69頁，課件共91頁，創(chuàng)作于2023年2月填充結果存在問題：矩形實際面積4×3；而填充后面積為5×4！產生面積擴大化的問題！012345671234567yx012345671234567yxP1P2P3P4第70頁，課件共91頁，創(chuàng)作于2023年2月解決問題二問題分析面積擴大是由于對邊界上的所有像素均進行填充而引起的如何解決制定填充規(guī)則：

“左閉右開”

“下閉上開”012345671234567yx第71頁，課件共91頁，創(chuàng)作于2023年2月算法討論AET的概念活性邊表（Active-Edge-Table）與當前掃描線相交的邊稱為活性邊，把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，此鏈表稱為活性邊表！引入活性邊表的概念，目的在于提高計算效率，在處理每一條掃描線時，不必將其與所有邊求交，只需考慮與活性邊求交即可！第72頁，課件共91頁，創(chuàng)作于2023年2月AETAET中結點內容x：當前掃描線與邊的交點坐標△x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymax例：掃描線6的活性邊表第73頁，課件共91頁，創(chuàng)作于2023年2月0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第74頁，課件共91頁，創(chuàng)作于2023年2月AET的更新每離開一條掃描線，進入下一條掃描線之前，應做的工作：將與當前掃描線相交而與下一條掃描線不相交的邊，從AET表中清除！將下一條掃描線新交上的邊，加入AET中適當的位置！第75頁，課件共91頁，創(chuàng)作于2023年2月請做練習請寫出掃描線“7”的活性邊表0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)第76頁，課件共91頁，創(chuàng)作于2023年2月答案掃描線7的活性邊表AET結點內容x：當前掃描線與邊的交點坐標△x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymaxP4P5P3P49281108∧FG第77頁，課件共91頁，創(chuàng)作于2023年2月AET&NETAET的作用通過AET，可以充分利用邊的連貫性和掃描線的連貫性，減少求交計算量，提高排序效率NET概念的引入為了方便活性邊表的建立與更新，為每條掃描線建立一個新的邊表稱之為NET（New-Edge-Table）第78頁，課件共91頁，創(chuàng)作于2023年2月NET的概念新邊表（NET）存放在該掃描線中第一次出現的邊！即：若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中第7