哈爾濱工業大學計算機學院唐好選2023年12月10日基本圖形生成算法基本圖形生成算法圖元掃描轉換直線段掃描轉換圓弧掃描轉換實區域填充圖形反走樣技術光柵圖形中點的表示…(x,y)坐標地址線性表1D表示顯示屏幕2D表示像素由其左下角坐標表示光柵圖形中點的表示地址=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址xyxmaxxminymaxymin每行像素點數行數行中位置光柵圖形中點的表示Address(x,y)=(xmax-xmin)*(y-ymin)+(x-xmin)+基地址

=k1+k2y+xAddress(x±1,y)=k1+k2y+(x±1)=Address(x,y)±1Address(x,y±1)=k1+k2(y±1)+x=Address(x,y)±k2Address(x±1,y±1)=k1+k2(y±1)

+(x±1)=Address(x,y)±k2±1對像素連續尋址時，如何減少計算量？增量法的優點？圖形顯示的幾種方式圖形顯示前需要：掃描轉換+裁剪裁剪→掃描轉換：最常用，節約計算時間掃描轉換→裁剪：算法簡單直線段掃描轉換假設像素間均勻網格，整型坐標系，直線段斜率0<m<1對m＞1，x、y互換直線段的掃描轉換算法直線的掃描轉換確定最佳逼近于該直線的一組象素按掃描線順序，對這些象素進行寫操作三個常用算法：-數值微分法（DDA）-中點畫線法-Bresenham算法數值微分(DDA)法(1/5)已知線段端點：P0(x0,y0),P1(x1,y1)直線方程

y=kx+b，

{(xi,

yi)},i=0,….n.浮點數取整:yi=round(yi)=(int)(yi+0.5)用到浮點數的乘法、加法和取整運算數值微分(DDA)法(2/5)增量算法yi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)→(xi+1,yi+k)缺點：有浮點數取整運算不利于硬件實現效率低僅適用于

k

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

k

1時，必須把x，y互換。數值微分(DDA)法(3/5)digitaldifferentialanalyzer基本思想用數值方法解微分方程

dx/dt=xdy/dt=y

xn+1=xn

+

?x

yn+1=yn

+?y

如何選取?？選取?的原則：使0.5≤|?x|,|?

y|≤1數值微分(DDA)法(4/5)簡單的DDA取?=1/max(|x

|,|

y|)使?|x

|,?|

y|中必有一個是單位步長

x為最大時，?x

=1,?y

=ky為最大時，?y

=1,?x

=1/k數值微分(DDA)法(5/5)缺點：浮點數運算不易硬件實現數值微分(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++)

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

中點畫線法（1/4）問題：判斷距離理想直線最近的下一個象素點已知：線段兩端點(x0,y0)，(x1,y1)直線方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判斷M點在Q點上方還是在Q點下方？MP1P2P直線上方點:F(x,y)＞0;直線下方點:F(x,y)＜0構造判別式：d=F(M)=F(Xp+1,Yp+0.5)由d＞0，d＜0可判定下一個象素(Xp+1,Yp+0.5)中點畫線法(2/4)分兩種情形考慮再下一個象素的判定：若d≥0，中點M在直線上方，取正右方象素P1(Xp+1,Yp)再下一個象素的判別式為：

d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+ad的增量為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+bMP1P2MP1P2d的初始值d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b=a+0.5b用2d代替d后，d0=2a+b=a+a+bd的增量都是整數優點：只有整數運算，不含乘除法可用硬件實現因(X0,Y0)在直線上，所以F(X0,Y0)=0中點畫線法（4/4）

AboutBresenhamE.JackBresenhamProfessorofComputerSciencePh.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959Retiredfrom27yearsserviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.Bresenham畫線算法（1/7）使用最廣泛與中點畫線法的思想類似由誤差項符號決定下一個象素取正右方像素還是右上方像素Bresenham畫線算法（2/7）基本思想比較從理想直線到位于直線上方的像素的距離d2和相鄰的位于直線下方的像素的距離d1根據距離誤差項的符號確定與理想直線最近的象素Bresenham畫線算法（3/7）最大位移方向每次走一步k<1時，x為最大位移方向y方向走步與否取決于誤差e值的大小誤差計算初值：e0=y/x當e≥0.5時，最接近P2(xi+1,yi+1),y方向走一步當e<0.5時，最接近P1(xi+1,yi),y方向不走步eP1P2Pe’eP1P2Pe’Bresenham畫線算法（4/7）為方便與0比較，設e=e-0.5e0=y/x-0.5當e≥0時，最接近P2(xi+1,yi+1),y方向走一步當e<0時，最接近P1(xi+1,yi),y方向不走步有除法，不宜硬件實現eP1P2Pe’eP1P2Pe’Bresenham畫線算法（5/7）設e=e×2x，不影響判斷的準確性e0=2y-x當e≥0時，最接近P2(xi+1,yi+1),y方向走一步當e<0時，最接近P1(xi+1,yi),y方向不走步eP1P2Pe’eP1P2Pe’Bresenham畫線算法（6/7）下一步誤差的計算當e≥0時，y方向走一步e’=2y/x-1=e+y/x-1e’=e+2y-2x當e<0時，y方向不走步e’=2y/x=e+y/xe’=e+2yeP1P2Pe’eP1P2Pe’Bresenham畫線算法（7/7）優點整數運算，速度快精度高乘2運算可用移位實現，適于硬件實現例題已知直線段起點(0,0)，終點(8,6)，利用Bresenham算法和中點畫線算法生成此直線段，寫出生成過程中坐標點及誤差ε的變化情況,并在下面的方格中，標出直線上各點（0，0）圓弧的掃描轉換算法圓弧的掃描轉換圓的八對稱性只考慮第二個八分圓假設圓心在原點

x2+y2=R2

yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR圓弧的掃描轉換兩種直接離散生成方法離散點開方運算離散角度三角函數運算缺點：計算量大所畫像素位置間的間距不一致中點畫圓法（1/3）F(X,Y)=X2+Y2-R2=0中點M=(Xp+1,Yp-0.5)當d＜0時，M在圓內，P1距離圓弧近，取P1當d＞0時，M在圓外，P2距離圓弧近，取P2中點畫圓法（2/3）若d<0,取P1為下一象素，再下一象素的判別式為若d>=0,取P2為下一象素，再下一象素的判別式為初始象素是（0,R），判別式d的初值為:d0=F(1,R-0.5)=1.25-RP1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替d,e0=1-R中點畫圓法（3/3）輸入圓的半徑R和圓心(xc,yc),先計算以原點為圓心，R為半徑的圓周上的點，令初始點為(x0,y0)=(0,R)設置初始決策參數d0=1-R在每一個xn的位置，從n=0開始，進行下列檢測：如果dn<0,則下一個點Pn+1(xn+1,yn+1)取為(xn+1,yn),且dn+1=dn+2xn+3=dn+2xn+1+1;否則,下一個點為(xn+1,yn-1),且dn+1=dn+2(xn-yn)+5=dn+2xn+1-2yn-1+1確定(xn+1,yn+1)在其余7個8分圓中的對稱點位置將計算出的每個象素位置平移到圓心位于(xc,yc)的軌跡上重復上述過程直到x>=y為止DDA畫圓法（1/3）圓的方程：f(x,y)=x2+y2-R2=0全微分：df(x,y)=2xdx+2ydy=0微分方程：dy/dx=-x/y遞推方程:(yn+1-yn)/(xn+1-xn)=-?xn/?ynxn+1-xn

=?yn

yn+1-yn

=-?xnDDA畫圓法（2/3）將遞推公式寫成矢量形式：構造一個行列式值為1的矩陣對應的圓方程遞推關系為

xn+1=xn

+

?yn

yn+1=-?xn+(1-?2)yn=yn-?xn+1

DDA畫圓法（3/3）針對不同象限及順逆時針畫圓，賦給?適當的符號

?不同，圓形狀不同，

?大近似橢圓Bresenham畫圓算法（1/7）順時針畫第一四分圓，下一步選擇哪個點？基本思想：通過比較像素與圓的距離平方來避免開方運算下一像素有3種可能的選擇mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2+(yi-1)2-R2|選擇像素的原則使其與實際圓弧的距離平方達到最小(xi,yi)HPi①VD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)②③④⑤Bresenham畫圓算法（2/7）圓弧與點(xi,yi)附近光柵網格的相交關系有5種右下角像素D(xi,yi)與實際圓弧的近似程度

i=(xi+1)2+(yi-1)2-R2當

i<0時，D在圓內，①②當

i>0時，D在圓外，③④當

i=0時，D在圓上，⑤(xi,yi)HPi①VD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)②③④⑤Bresenham畫圓算法（3/7）當

i<0時，D在圓內，①②情形①，選mH

，mD

中最小者d=mH

-mD

=|(xi+1)2+yi2-R2|-|(xi+1)2+(yi-1)2-R2|=(xi+1)2+yi2-R2+(xi+1)2+(yi-1)2-R2=2(

i+yi)-1若d<0，則選H若d>0，則選D若d=0，則選H情形②也適用Bresenham畫圓算法（4/7）當

i>0時，D在圓外，③④情形③，選mv

，mD

中最小者d’=mD

-mV=|(xi+1)2+(yi-1)2-R2|-|xi2+(yi-1)2-R2|=(xi+1)2+(yi-1)2-R2+xi2+(yi-1)2-R2=2(

i-xi)-1若d’<0，則選D若d’>0，則選V若d’=0，則選D情形④也適用Bresenham畫圓算法（5/7）當

i=0時，D在圓上，⑤按d判別，有d>0，應選D按d’判別，有d’<0，應選DBresenham畫圓算法（6/7）當

i<0時,若d≤0，選H若d>0，選D當

i>0時,若d’≤0，選D若d’>0，選V當

i=0時，選DBresenham畫圓算法（7/7）判別式的遞推關系當取H(xi+1,yi)時

i+1=(xi+1+1)2+(yi-1)2-R2=

i+2(xi+1)+1當取V(xi,yi-1)時

i+1=(xi+1)2+(yi-1-1)2-R2=

i-2(yi-1)+1當取D(xi+1,yi-1)時

i+1=(xi+1+1)2+(yi-1-1)2-R2=i+2(xi+1)-2(yi-1)+2多邊形逼近法當圓的正內接多邊形邊數足夠多時，可以用畫該多邊形近似代替畫圓“以直代曲”的代表方法之一內接正n邊形頂點為Pi(xi,yi)每條邊對應的圓心角為θ，則有

實區域填充實區域填充

給出一個區域的邊界，要求對邊界范圍內的所有像素單元賦予指定的顏色代碼我們的目的：多邊形填充解決的主要問題是什么？確定待填充的象素，即檢查光柵的每一像素是否位于多邊形區域內對于圖案填充還要確定用不同的顏色填充不同象素對于曲線圍成的區域，可考慮用多邊形逼近數學方法

掃描交點的奇偶數判斷法基本思想：將多邊形畫在平面上用一根水平掃描線自左向右通過多邊形從而與多邊形的邊界相交掃描線與邊界相交奇數次后進入該多邊形，相交偶數次后走出該多邊形ABCDEFG掃描線abcd射線法檢驗交點數ABCDEPABCDEP交點數=偶數（包括0）點在多邊形之外交點數=奇數點在多邊形之內yx存在的問題直線光柵化后變成了占有單位空間的離散點，進出多邊形的判斷不準確，造成錯誤填充現象如何改進？檢驗夾角之和若夾角和為0，則點P在多邊形外（左圖）若夾角和為360°，則點P在多邊形內（右圖）ABCDEPABCDEP夾角如何計算？大小：利用余弦定理方向：令當T<0時，AP斜率>BP斜率，為順時針角yxABP當T>0時，AP斜率<BP斜率，為逆時針角yxBAP包圍盒法凸多邊形凹多邊形逐點測試效率低不實用怎么辦？實區域填充算法分類掃描線填充（Scan-LineFilling）算法掃描線順序種子填充（SeedFilling）算法內部一個點出發掃描線填充算法求交：I4,I3,I2,I1排序：I1,I2,I3,I4交點配對：(I1,I2),(I3,I4)區間填色利用圖形的空間連貫性和掃描線的連貫性012345671234567yx88910掃描線5P4P1P2P3P5掃描線2I1I2I3I4填充擴大化問題解決方法：取中心掃描線y+0.5檢查交點右方像素的中心是否落在區間內xl≤x+0.5≤xr頂點交點的計數問題檢查交于該頂點的兩條邊的另外兩個端點的y值大于該頂點y值的個數543210P1P2P3P4I1I2I3I4P5掃描線5掃描線4掃描線3掃描線2掃描線1I5I6計數0次計數1次計數2次12/10/202356有序邊表算法影響一般掃描線填充算法效率的因素？求交和排序把多邊形所有邊放在一個表中，按順序取出，分別計算與每條掃描線的交點如何提高效率？首先要簡化交點計算建立每條掃描線的活性邊表何謂活性邊？(ActiveEdgeTable)有序邊表算法對每條掃描線建立新邊表(NET:NewEdgeTable)結點信息x0：掃描線與邊的初始交點△x：從當前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號邊結點不必排序yx0123456789101112345678P6P4P1P5P2P3新邊表8.57.56.55.54.53.52.51.50.5∧∧∧∧∧528.5-1.57∧1108∧207∧5-32.533∧P4P5P5P6P3P4P6P1P1P2P2P3有序邊表算法活性邊表(AET)的建立結點信息x：當前掃描線與邊的交點△x：從當前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號活性邊表的更新新邊插入舊邊刪除△x=1/k活性邊表(排序)5-32.533∧P1P2P2P3y=1.5207.833∧P6P1P2P3y=2.5207.1108∧P6P1P3P4y=3.5從新邊表中取出與掃描線y=1.5相交的初始邊排序放入活性邊表中，填充交點之間的區域更新邊表，刪除P1P2，插入新邊P6P1，填充交點之間的區域更新邊表，刪除P2P3，插入新邊P3P4，填充交點之間的區域528.P4P51108∧P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108∧P3P43.5-1.57P5P6207.P6P1y=6.5928.P4P51108∧P3P4y=7.5更新邊表，插入新邊P5P6和P4P5，填充兩對交點之間的區域更新邊表，填充兩對交點之間的區域更新邊表，刪除P6P1和P5P6，填充交點之間的區域更新邊表，刪除P4P5和P3P4，活性邊表為空，沒有新邊，填充算法結束step1：把新邊表NET[i]中的邊結點，用插入排序法插入活性邊表AET，使之按X坐標遞增順序排序；step2：遍歷AET表，把配對交點之間的區間(左閉右開)上的各象素(X,Y)，用drawpixel(x,y,color)改寫象素顏色值；step3：遍歷AET表，把Ymax=i的結點從AET表中刪除，并把

Ymax＞i的結果點的X值遞增△X；step4：重復各掃描線算法描述：(對每一條掃描線i)有序邊表算法優點：對每個像素只訪問一次與設備無關缺點：數據結構復雜只適合軟件實現邊填充算法(EdgeFillAlgorithm)優點：最適合于有幀緩存的顯示器可按任意順序處理多邊形的邊僅訪問與該邊有交點的掃描線上右方的像素，算法簡單缺點：對復雜圖形，每一像素可能被訪問多次，輸入/輸出量大圖形輸出不能與掃描同步進行，只有全部畫完才能打印邊填充算法(EdgeFillAlgorithm)

柵欄填充算法(FenceFillAlgorithm)引入柵欄的目的？種子填充算法假設多邊形區域內至少有一個像素已知區域定義法Interior-definedBoundary-definedFlood-fillalgorithmBoundary-fillalgorithm區域連通方式：4-connected8-connected12/10/202368區域連通方式對填充結果的影響4連通區域邊界填充算法的填充結果8連通區域邊界填充算法的填充結果簡單的種子填充算法（4連通邊界）種子像素入棧當棧非空時，重復以下步驟：棧頂像素出棧將出棧象素置成填充色

按左、上、右、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺點？4-connectedboundary-fill

voidBoundaryFill4(intx,int

y,int

fill,intboundary){

intcurrent;current=getpixel(x,y);if((current!=boundary)&&(current!=fill)){

putpixel(x,y,fill);BoundaryFill4(x+1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y-1,fill,boundary);}}4-c