1、2022-1-6p 如何在指定的輸出設備上根據坐標描述構造基如何在指定的輸出設備上根據坐標描述構造基本幾何圖形（點、直線、圓、橢圓、多邊形域、本幾何圖形（點、直線、圓、橢圓、多邊形域、字符串及其相關屬性等）字符串及其相關屬性等）?第第3 3章章 基本圖形生成算法基本圖形生成算法2022-1-62p 圖形生成的概念圖形生成的概念p 直線段的掃描轉換直線段的掃描轉換p 圓的掃描轉換圓的掃描轉換p 多邊形的掃描轉換與區域填充多邊形的掃描轉換與區域填充p 屬性處理屬性處理p 反走樣技術反走樣技術第第3 3章章 基本圖形生成算法基本圖形生成算法2022-1-62022-1-63點的生成點的生成 點是圖形

2、中最基本的圖元，直線、曲線以及其它的圖元都是點是圖形中最基本的圖元，直線、曲線以及其它的圖元都是點的集合。點的集合。 在幾何學中，一個點既沒有大小，也沒有維數，點只是表示在幾何學中，一個點既沒有大小，也沒有維數，點只是表示坐標系統中一個位置。坐標系統中一個位置。 在計算機圖形學中，點是用數值坐標來表示的。在直角坐標在計算機圖形學中，點是用數值坐標來表示的。在直角坐標系中點由（系中點由（x,yx,y) ) 兩個數值組成的坐標表示，在三維坐標系中點兩個數值組成的坐標表示，在三維坐標系中點是由（是由（x,y,zx,y,z) )三個數值組成的坐標表示。三個數值組成的坐標表示。 在輸出設備上輸出一個點，

3、就要把應用程序中的坐標信息轉在輸出設備上輸出一個點，就要把應用程序中的坐標信息轉換成所用輸出設備的相應位置。對于一個換成所用輸出設備的相應位置。對于一個CRTCRT監視器來說，輸出監視器來說，輸出一個點就是要在指定的屏幕位置上打上電子束，使該位置上的熒一個點就是要在指定的屏幕位置上打上電子束，使該位置上的熒光點亮。光點亮。 在在PCPC機中，點亮屏幕上一個點是由機中，點亮屏幕上一個點是由BIOSBIOS控制完成的，各種程控制完成的，各種程序語言中都有描點語句。例如序語言中都有描點語句。例如C C語言為語言為putpixel(x,y,colorputpixel(x,y,color) ) , ,p

4、utpixelputpixel( (放放, ,擺擺- -像素像素) )。3.1 圖形生成的概念圖形生成的概念2022-1-62022-1-6o 圖形的生成：是在指定的圖形的生成：是在指定的輸出設備上，根據坐標描輸出設備上，根據坐標描述構造二維幾何圖形。述構造二維幾何圖形。o 圖形的掃描轉換圖形的掃描轉換：在光柵：在光柵顯示器等數字設備上確定顯示器等數字設備上確定一個最佳逼近于圖形的像一個最佳逼近于圖形的像素集的過程。素集的過程。 用像素點集逼近直線用像素點集逼近直線3.1 圖形生成的概念圖形生成的概念2022-1-62022-1-63.1 圖形生成的概念圖形生成的概念2022-1-62022-

5、1-6 在數學上，理想的直線是沒有寬度的、由在數學上，理想的直線是沒有寬度的、由無數個點構成的集合。當我們對直線進行光柵無數個點構成的集合。當我們對直線進行光柵化時，只能在顯示器所給定的有限個像素組成化時，只能在顯示器所給定的有限個像素組成的矩陣中，的矩陣中，確定最佳逼近該直線的一組像素，確定最佳逼近該直線的一組像素，并且按掃描線順序對這些像素進行寫操作并且按掃描線順序對這些像素進行寫操作，這，這就是通常所說的直線的掃描轉換。就是通常所說的直線的掃描轉換。 通常用于直線光柵化的算法有數值微分法（通常用于直線光柵化的算法有數值微分法（DDADDA）、中點畫線法和）、中點畫線法和Bresenham

6、Bresenham畫線算法。畫線算法。3.2 直線的掃描轉換直線的掃描轉換2022-1-62022-1-6直線光柵化算法直線光柵化算法o 直線段生成直線段生成o 求與直線段充分接近的像素集求與直線段充分接近的像素集2022-1-62022-1-6o 直線的繪制要求直線的繪制要求 （1 1）直線要直；）直線要直； （2 2）直線的端點要準確，無定向性無斷裂；）直線的端點要準確，無定向性無斷裂； （3 3）直線的亮度、色澤要均勻；）直線的亮度、色澤要均勻； （4 4）畫線的速度要快；）畫線的速度要快； （5 5）具有不同的色澤、亮度、線型等。）具有不同的色澤、亮度、線型等。3.2 直線的掃描轉換直

7、線的掃描轉換2022-1-62022-1-6o解決的問題解決的問題：給定直線兩端點：給定直線兩端點P0(x0,y0)和和P1(x1,y1)，畫出該直線。畫出該直線。o 數值微分法數值微分法(DDA算法算法)o 中點畫線算法中點畫線算法o Bresenhan算法算法3.2 直線的掃描轉換直線的掃描轉換2022-1-62022-1-6 已知一條直線段已知一條直線段L（P0, P1）,其端點坐標為：其端點坐標為：P0 (x0, y0), P1(x1, y1)。可計算出直線的斜率。可計算出直線的斜率k為：為：0101xxyyk DDA（Digital Differential Analyzer）畫線算

8、法也）畫線算法也稱數值微分法，是一種增量算法。它的算法實質是用數值方法稱數值微分法，是一種增量算法。它的算法實質是用數值方法解微分方程，通過同時對解微分方程，通過同時對x和和y各增加一個小增量，計算下一各增加一個小增量，計算下一步的步的x、y值。值。3.2.1 數值微分法數值微分法(DDA法法)2022-1-62022-1-6o 假定端點坐標均為整數，取假定端點坐標均為整數，取直線起點直線起點P0 (x0, y0)作為初作為初始坐標。畫線過程從始坐標。畫線過程從x的左端的左端點點x0開始，向開始，向x右端點步進，右端點步進，每步每步x遞增遞增1，計算相應的，計算相應的y坐標，坐標， y=kx+

9、b，取像素點，取像素點（x，round（y）作為當）作為當前點的坐標。前點的坐標。o 問題問題:每步需要每步需要用到浮點數的用到浮點數的乘法、加法和取整運算，效乘法、加法和取整運算，效率不高。怎么辦率不高。怎么辦?3.2.1 數值微分法數值微分法(DDA法法)2022-1-62022-1-6o 增量算法增量算法o 因為因為: y=kx+b,所以所以:y yi+1i+1=kx=kxi+1i+1+b=k(x+b=k(xi i+1)+b=+1)+b=kxkxi i+b+b+k+k= =y yi i+k+k(x(xi i,y,yi i)(x)(xi i+1,y+1,yi i+k)+k)3.2.1 數值

10、微分法數值微分法(DDA法法) r例圖中例圖中 k1 X=1 Y=k r將算得的直線上每個點的當前坐標，按四舍五入得到光柵點的位置將算得的直線上每個點的當前坐標，按四舍五入得到光柵點的位置 r浮點數取整浮點數取整 : yi=round(yi)=(int)(yi+0.5)2022-1-62022-1-6有：有：yi+1=yi+k Xr若若0k yq因光柵單位為因光柵單位為1 1，q可以采用每次可以采用每次x x方向增加方向增加1 1，q而而y y方向增加方向增加k k的辦法得到下一個直線點。的辦法得到下一個直線點。0101xxyyk因因:3.2.1 數值微分法數值微分法(DDA法法)演示演示說明

11、說明2022-1-62022-1-6例：例：畫直線段P0(0,0)-P1(5,2)解：斜率解：斜率K=2/5=0.4，所以，所以X方方向每次步長為向每次步長為1，Y方向遞增方向遞增K。初。初始點為（始點為（0，0）。）。x int(y+0.5) y000100.4210.8311.2421.6522.00 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)當當 k 1時，必須把時，必須把x，y地位互換地位互換y yi+1i+1= =y yi i+k+k0101xxyyk2022-1-62022-1-6 程序實現：程序實現：void DDALine(int x0,int y

12、0,int x1,int y1,int color) int x; float dx,dy,k,y; dx=x1-x0; dy=y1-y0; k=dy/dx; y=y0; for(x=x0;x=x1;) drawpixel(x,int(y+0.5),Color); x+; y=y+k; 0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2022-1-62022-1-6通常情況下，直線的通常情況下，直線的方向分為方向分為8個不同的區域，個不同的區域，每個區域的處理方法有所不每個區域的處理方法有所不同。同。K=y/x區域dxdy1a(1)1k1b(2)1/k12a(4)-

13、1k2b(3)-1/k13a(5)-1-k3b(6)-1/k-14a(8)1-k4b(7)1/k-13.2.1 數值微分法數值微分法(DDA法法)2022-1-62022-1-63.2.1 數值微分法數值微分法(DDA法法)2022-1-62022-1-618o 增量算法增量算法o 直觀、易實現直觀、易實現o 不利于用硬件實現不利于用硬件實現 數值微分法數值微分法(DDA法法)特點特點2022-1-62022-1-63.2.2 中點畫線算法中點畫線算法中點畫線算法的基本思想中點畫線算法的基本思想為了討論方便，假設直線的斜率在為了討論方便，假設直線的斜率在0 0到到1 1之間，若直線在之間，若直

14、線在x x方向上增加一個光柵單位，則方向上增加一個光柵單位，則在在y y方向上的增量只能在方向上的增量只能在0 0到到1 1之間。設之間。設P P（x xp p,y,yp p）是直線上的一點，與是直線上的一點，與P P點最近的網格點為點最近的網格點為（x xi i, , y yi i）, ,那么，下一個與直線最近的像素只能那么，下一個與直線最近的像素只能是正右方的網格點是正右方的網格點P P1 1（x xi i+1, +1, y yi i）或右上方的網或右上方的網格點格點P P2 2（x xi i+1,y+1,yi i+1+1）兩者之一。再以點兩者之一。再以點M M（x xi i+1, y+1

15、, yi i+0.5+0.5）表示表示P P1 1和和P P2 2的中點，設的中點，設Q Q是直線是直線與垂直線與垂直線x= xx= xi i+1+1的交點。顯然，若的交點。顯然，若M M在在Q Q的下方的下方，則，則P P2 2離直線較近，應取離直線較近，應取P P2 2為下一個像素點，否為下一個像素點，否則應取則應取P P1 1做為下一個像素點，做為下一個像素點，這就是中點畫線這就是中點畫線算法的基本思想。算法的基本思想。 n問題：如何判斷問題：如何判斷M與與Q點的關系？點的關系？2022-1-62022-1-6圖圖 直線將平面分為三個區域直線將平面分為三個區域3.2.2 中點畫線算法中點

16、畫線算法點在直線下方點在直線上方點在直線上面0,0,0,yxFyxFyxF假設直線的起點、終點分別為：（假設直線的起點、終點分別為：（X X0 0,Y,Y0 0),(X),(X1 1,Y,Y1 1) ) 則直線方程可表示為：則直線方程可表示為： F(x,yF(x,y)=a)=a* *x+bx+b* *y+cy+c （1 1） 其中：其中： a=Ya=Y0 0-Y-Y1 1, b=X, b=X1 1-X-X0 0, c=X, c=X0 0* *Y Y1 1-X-X1 1* *Y Y0 0 空間某點（空間某點（x,yx,y）與直線的關系：）與直線的關系： 當：當：2022-1-62022-1-6

17、設直線的起點和終點分別為（設直線的起點和終點分別為（x x0 0,y ,y0 0) )和和( (x x1 1,y ,y1 1) ) 則直線方程為則直線方程為F(x,yF(x,y)=)=ax+by+cax+by+c=0 =0 （1） 欲判斷中點欲判斷中點M點是在點是在Q點上方還是在點上方還是在Q點下點下方，只需方，只需:o 將中點將中點M坐標代入（坐標代入（1）式，并判斷其符號）式，并判斷其符號o 即可確定像素點的選取。即可確定像素點的選取。構造構造如下如下判別式判別式：采用增量計算采用增量計算 d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+cd=F(M)=F(x+1

18、, y+0.5)=a(x+1)+b(y+0.5)+c在在d0d0的情況下的情況下( (M在直線上在直線上(Q點點)或上方或上方)，取，取正右方像素正右方像素P P1 1在在d0dM在直線上方在直線上方-取取P1;此時此時再下一個再下一個像素的判別式為像素的判別式為 d1 1=F(x+2, y+0.5)(F(x,y)=(F(x,y)=ax+by+cax+by+c=0 )=0 ) =a(x+2)+b(y+0.5)+c = a(x +1)+b(y +0.5)+c +a =d+a； 增量為增量為ad=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c2022-1-62022-1-

19、6若若dM在直線下方在直線下方-取取P2;此時此時再下一個再下一個象素的判別式為象素的判別式為 d2 2= F(x+2, y+1.5) =a(x+2)+b(y+1.5)+c = a(x+1)+b(y+0.5)+c +a +b =d+a+b ； 增量為增量為ab3.2.2 中點畫線算法中點畫線算法d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c2022-1-62022-1-6o 畫線從畫線從(x0 0, y0 0)開始，開始，d的初值的初值（F(x,y)=a*x+b*y+c） o d0 0=F(x0 0+1, y0 0+0.5)= a(x0 0 +1)+b(y0 0+

20、0.5)+c = ax0 0 +a+by0 0+0.5b+c = ax0 0+by0 0+c+a+0.5b =F(x0 0, y0 0)+a+0.5b = a+0.5b注：由于（注：由于（ x0 0, y0 0）在直線上，故）在直線上，故F(x0 0, y0 0)=0o 所以，所以，d的初始值的初始值d0 = a+0.5b 3.2.2 中點畫線算法中點畫線算法2022-1-62022-1-6 由于只用由于只用d 的符號作判斷，為了只包含整數運算的符號作判斷，為了只包含整數運算, 可以用可以用2d代替代替d來擺脫小數，提高效率。用來擺脫小數，提高效率。用2d代替代替d后，后，d0 0=2a+bn

21、 d的增量都是整數的增量都是整數(d1 1:2a, d2 2:2(a+b) 如果進一步把算法中如果進一步把算法中2*a改為改為a+a等等，那么這等等，那么這個算法不僅只包含整數變量，而且不包含乘除法，個算法不僅只包含整數變量，而且不包含乘除法，適合硬件實現。適合硬件實現。3.2.2 中點畫線算法中點畫線算法演示說明演示說明d的初始值的初始值d0 = a+0.5b2022-1-62022-1-6 解解: K=dy/dx=2/5=0.41,故故x方向增方向增1,y方向根據方向根據d的符號判斷的符號判斷. a=y0-y1=-2; b=x1-x0=5; d0=2a+b=1; d1=2a=-4; d2=

22、2(a+b)=6; x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 1例例:按照中點畫線算法，確定直線（按照中點畫線算法，確定直線（0，0）（）（5，2）的點亮像素。列出計算過程，并列出所選像素坐標。的點亮像素。列出計算過程，并列出所選像素坐標。在在d0的情況下，取正右方像素的情況下，取正右方像素P1，判斷判斷再下一再下一像素應計算像素應計算 d1=a(x+2)+b(y+0.5)+c =d+a ,故故d的增量為的增量為a.在在d0的情況下，取右上方像素的情況下，取右上方像素P2，判斷判斷再下一再下一像素應計算像素應計算 d2=a(x+2)+b(y+1.5)

23、= d+a+b,故故d的增量為的增量為a+b.d的初始值的初始值d0 = a+0.5b用用2d代替代替d后，后，d0=2a+bd的增量都是整數的增量都是整數 d1：2a d2：2(a+b) 2022-1-62022-1-6程序實現：程序實現：void MidpointLine (int x0,int y0,int x1, int y1,int color) int a, 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 (xx

24、1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); 在在d=0的情況下的情況下(M在直線在直線(Q點點)上方上方)，取正右方像素，取正右方像素P1,再下再下一個一個像素的判別式為像素的判別式為d1.2022-1-62022-1-63.2.3 Bresenham畫線算法畫線算法 Bresenham算法是計算機圖形學領域使用最廣算法是計算機圖形學領域使用最廣泛的直線生成算法。假設直線斜率泛的直線生成算法。假設直線斜率 k 0, 1。Bresenham畫線算法的基本原理是：畫線算法的基本原理是：按直線從按直線從起點到終

25、點的順序計算直線與各垂直網格線的交點起點到終點的順序計算直線與各垂直網格線的交點，然后確定該列像素中與此交點最近的像素。，然后確定該列像素中與此交點最近的像素。 這是計算機科學教授Jack Elton Bresenham最知名的一項創新，開發于1962年。 2022-1-62022-1-6o 因為斜率較小，所以每條垂直線上最多選取一因為斜率較小，所以每條垂直線上最多選取一個像素。如果像素點個像素。如果像素點 Pi-1 (xi-1，yi-1) 是已經是已經選定的離直線最近的像素點，現在要決定下一選定的離直線最近的像素點，現在要決定下一個像素點個像素點Pi是是Ti 還是還是Si。如圖。如圖3-5所

26、示。所示。由圖由圖3-5不難看出：若不難看出：若st，則則Si比較靠近理想直線，應比較靠近理想直線，應選選Si;若若st，則，則Ti比較靠近比較靠近理想直線，應選理想直線，應選Ti。3.2.3 Bresenham畫線算法畫線算法2022-1-62022-1-6令令dx=x2-x1，dy=y2-y1遞推公式遞推公式 ：di的初值：的初值： 當當di0時，選時，選Ti，當當di0時，選時，選Si， 由于只包含加、減法和左移（乘由于只包含加、減法和左移（乘2）的運算，而）的運算，而且下一個像素點的選擇只需檢查且下一個像素點的選擇只需檢查di的符號，因此的符號，因此Bresenham畫線算法很簡單，速

27、度也相當快。畫線算法很簡單，速度也相當快。 )(2211iiiiyydxdydddxdyd 21)(21dxdyddiidyddii213.2.3 Bresenham畫線算法畫線算法請看下面的推導過程請看下面的推導過程結論結論2022-1-62022-1-6 已知，已知，Pi (xi , yi)，xi xi11，當當PiTi時，時，yi yi-1 +1 ；當；當PiSi時，時，yi yi-1顯然，無論下一個像素點是顯然，無論下一個像素點是Ti還是還是Si ，x方向都增方向都增1，即，即xi xi11，要，要決定的是決定的是y方向是否增方向是否增1。由圖。由圖3-5不難看出不難看出 :o若若s0

28、，所以可將，所以可將dx (s-t) 的正負作為選擇的正負作為選擇Ti 或或Si的依的依據。若記其為據。若記其為di，則：，則：(1) 3.2.3 Bresenham畫線算法畫線算法注注:Si的坐標的坐標(xi-1+1,yi-1), Ti的坐標的坐標(xi-1+1,yi-1+1)f(x)=kx(di 0時，選時，選Ti , 否則選否則選S i )2022-1-62022-1-6將每一個下標加將每一個下標加1，則有：，則有：兩式相減得兩式相減得(2-1)因為因為xi - xi-1 =1，所以得到遞推公式：，所以得到遞推公式：因此，當因此，當di 0時，選時，選Ti 。這時。這時y方向增方向增1，

29、即，即yi - yi-1 =1，則，則(2)3.2.3 Bresenham畫線算法畫線算法注注:當當di 0時時,說明說明:s=t,反之反之 ts問問:當當di 0時，為什時，為什么選么選Ti ?2022-1-62022-1-6當當di 0時，選時，選Si 。這時。這時yi - yi-1 =0，則：，則：o di的初值可由的初值可由(1)式得出，當式得出，當i=1時時(x0, y0)=(0,0)即即d1 d1 = 2(x0 dy - y0 dx) +2dy -dx 。o 由我們的假設，由我們的假設，x0 =0, y0 =0。即。即3.2.3 Bresenham畫線算法畫線算法2022-1-62

30、022-1-6 例例: :請指出用請指出用BresenhamBresenham算法掃描轉換算法掃描轉換 從像素點從像素點p1p1（0 0，0 0）到）到p2p2（5 5，2 2）的線段時的像素位置。）的線段時的像素位置。 解解:K=dy/dx=2/5=0.4=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d0 點點M在圓外在圓外,應取應取p2作為下一個像素作為下一個像素 d=0 點點M在圓上在圓上,約定取約定取p2作為下一個像素作為下一個像素 d0 點點M在圓內在圓內,應取應取p1作為下一個像素作為下一個像素即根據每一個像素計算判別式即根據每一個像素計算判別式

31、d,根據它的符號確定下一個像素根據它的符號確定下一個像素.與中點畫線一樣與中點畫線一樣,d也可以采用增量計算也可以采用增量計算:3.3.2 中點畫圓算法中點畫圓算法2022-1-62022-1-6o 在在d0的情況下的情況下，取右下方像素，取右下方像素P2，再下一個像素取哪個，再下一個像素取哪個應計算應計算: 故故d的增量為的增量為2(xp-yp)+5o 在在d0的情況下的情況下，取正右方像素，取正右方像素P1，再下一個像素取哪個，再下一個像素取哪個應計算應計算: 故故d的增量為的增量為2xp+33.3.2 中點畫圓算法中點畫圓算法2022-1-62022-1-6o 這樣得到了這樣得到了dp的

32、遞推公式，從中可以導出圓的的遞推公式，從中可以導出圓的中點算法。當然，還需要一個初始條件。在中點算法。當然，還需要一個初始條件。在1b區域，假定區域，假定x0=0, y0=R。則。則RRRRFyxFd25. 1 )5 . 0(1 )5 . 0, 1 ()5 . 0, 1(220003.3.2 中點畫圓算法中點畫圓算法如果半徑是整數如果半徑是整數,則可以對則可以對d0簡單簡單取整取整: d0=1-R(R是整數是整數)2022-1-62022-1-6void midpointcircle(int r,int color) int x,y; float d; x=0;y=r;d=1.25-r; Ci

33、rcle_Points(x,y,color); while(x=y) if(d0) d=d+2*x+3; else d=d+2(x-y)+5; y-; x+; Circle_Points(x,y,color); 使用中點畫圓算法繪制一個使用中點畫圓算法繪制一個1/8光柵圓程序光柵圓程序void Circle_Points(int x,int y, int color) Putpixel (x, y, color); Putpixel (x, -y, color); Putpixel (-x, y, color); Putpixel (-x, -y, color); Putpixel (y, x

34、, color); Putpixel (y, -x, color); Putpixel (-y, x, color); Putpixel (-y, -x, color);2022-1-62022-1-6例例: :利用中點畫圓算法利用中點畫圓算法, ,繪制一條圓弧繪制一條圓弧: :中心在坐標原點中心在坐標原點, ,半徑半徑R R為為10,10,從從x=0 x=0到到x=yx=y的的1/81/8圓弧圓弧. .解解 判別式判別式d的初始值為的初始值為:d0=1-R =1-10=-9 初始點初始點(x0,y0)的坐標為的坐標為(0,10),則則 2x0=0,2y0=20 繪制初始點繪制初始點(0,10

35、),并確定沿圓弧路并確定沿圓弧路徑的其余像素位置為徑的其余像素位置為: x y d 0 10 -9 1 10 -6 2 10 -1 3 10 6 4 9 -3 5 9 8 6 8 5 7 7 6在在d0的情況下的情況下，取右下方像，取右下方像素素,d的增量的增量:d=d+2(x-y)+5在在d=0=0，則，則y=yy=yi i-1-1，選擇右下方點，選擇右下方點(p(p2 2) ) x xi+1i+1= =x xi i+1+1, y, yi+1i+1=y=yi i-1,-1, d di+2i+2 =2(x =2(xi i+2)+2)2 2+(y+(yi i-1)-1)2 2+(y+(yi i-

36、2)-2)2 2-2r-2r2 2= =2x2xi i2 2+8x+8xi i+8+y+8+yi i2 2+y+yi i2 2-2y-2yi i+1-4y+1-4yi i+4-2r+4-2r2 2= =d d i+1i+1 + + 4(x4(xi i- y- yi i)+10)+10如果如果d d i+1i+10=0，則，則y=yi-1，選擇右下方點，選擇右下方點(p2) xi+1=xi+1, yi+1=yi-1 di+2 =d i+1 + 4(xi- yi)+10如果如果d i+10，則，則y=yi，選擇正右方點，選擇正右方點(p1) xi+1=xi+1, yi+1=yi d i+2 =d

37、i+1+ 4x i+62022-1-62022-1-6BresenhamBresenham生成圓弧的程序如下：生成圓弧的程序如下：根據算法，可得根據算法，可得BresenhamBresenham生成圓弧的程序如下：生成圓弧的程序如下：void void Bresenham_CircleBresenham_Circle ( (intint R,intR,int color) color) intint x,y,dx,y,d; ; x=0;y=R; x=0;y=R; d=3-2 d=3-2* *R;R; while(xwhile(xy)y) Circle_PointsCircle_Points (

38、 (x,y,colorx,y,color);); if(dif(d0)1)之間的直線所需的步驟。解答：假設線段的兩個端點（x1, y1）和（x2，y2），且y1y2int x,y = y1;float xf = x1, m = ( x2x1) /( y2 y1) ；while( y1|m|1）之間的直線所需的步驟。）之間的直線所需的步驟。解答：解答：假設線段的兩個端點為（x1，y1）和（x2，y2），且y1y2int x = x1, y = y1;float xf, m = （y2y1）/（x2x1）, b = y1 mx1;setPixel( x, y ); /*畫一個像素點*/while(

39、 y X2-X1=48X2-X1=4若取若取x x為一個像素單為一個像素單位，則由位，則由y yi i1 1 = =y yi i xx則可能出現像素點不連則可能出現像素點不連續的情況續的情況1212xxyy若取若取y y為一個像素單位為一個像素單位，則由，則由x xi i1 1 = =x xi i yy則像素點連續則像素點連續1212yyxx 2022-1-62022-1-6今天作業今天作業”o P89 3.2 ,3.42022-1-62022-1-63.23.2 請指出用請指出用BresenhamBresenham算法掃描轉換從像素點（算法掃描轉換從像素點（1 1，1 1）到（）到（8 8，

40、5 5）的線）的線段時的像素位置。段時的像素位置。 dx=x2-x1=8-1=7dy=y2-y1=5-1=4d1=2*dy-dx=8-7=1td1=2(dy-dx)=2(4-7)= -6td2=2*dy=2*4=8d1=2dy-dxd=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d0,x=x+1,y=ydi+1=d+2dytd2=2*dy2022-1-62022-1-6下周上機下周上機o 時間時間:10月月27日日o 地點地點:15#407機房機房o 內容內容:2022-1-62022-1-63.4 區域填充區域填充o區域填充即給出一個區域的定義，要求對此區

41、域范圍內的所有像區域填充即給出一個區域的定義，要求對此區域范圍內的所有像素賦予指定的顏色代碼。只要算法設計合理，運用著色的方法就素賦予指定的顏色代碼。只要算法設計合理，運用著色的方法就可以使光柵圖形的畫面色彩逼真，更能形象而具有真實感地利用可以使光柵圖形的畫面色彩逼真，更能形象而具有真實感地利用二維光柵技術顯示三維圖形。二維光柵技術顯示三維圖形。o多邊形可以是構成平面圖形的幾何元素，也可以是構成三維物體多邊形可以是構成平面圖形的幾何元素，也可以是構成三維物體表面的投影。如果物體的表面是曲面，也可由適當的多邊形去逼表面的投影。如果物體的表面是曲面，也可由適當的多邊形去逼近。因此，區域填充中最常用

42、的是多邊形填色。近。因此，區域填充中最常用的是多邊形填色。o對于區域填充來說，它要解決兩個問題：對于區域填充來說，它要解決兩個問題： 確定需要填充哪些象素，確定需要填充哪些象素， 確定用什么顏色或圖案。確定用什么顏色或圖案。區域填充就是將區區域填充就是將區域內的像素置成新域內的像素置成新的顏色值或圖案的顏色值或圖案處于一個處于一個封閉輪廓封閉輪廓線內的所線內的所有像素點有像素點即構成一即構成一個區域個區域2022-1-62022-1-63.4 區域填充區域填充2022-1-62022-1-63.4.1 區域的表示和類型區域的表示和類型o在計算機圖形學中，區域有兩種重要的表示方法：頂點表示和點在

43、計算機圖形學中，區域有兩種重要的表示方法：頂點表示和點陣表示。陣表示。o頂點表示頂點表示(如圖如圖315所示所示)也稱幾何表示，是用區域的頂點序列也稱幾何表示，是用區域的頂點序列來表示。例如，多邊形區域由閉合折線定義。這種表示直觀、幾來表示。例如，多邊形區域由閉合折線定義。這種表示直觀、幾何意義強、占內存少，易于進行幾何變換，但由于沒有明確指出何意義強、占內存少，易于進行幾何變換，但由于沒有明確指出哪些像素在多邊形內，故不能直接用于面著色，需要通過某種掃哪些像素在多邊形內，故不能直接用于面著色，需要通過某種掃描轉換將頂點表示轉變為點陣表示。描轉換將頂點表示轉變為點陣表示。 o點陣表示點陣表示(

44、如圖如圖316所示所示)也稱像素表示，是用位于多邊形內的也稱像素表示，是用位于多邊形內的像素集合來刻畫多邊形。這種表示便于幀緩沖器表示圖形，是面像素集合來刻畫多邊形。這種表示便于幀緩沖器表示圖形，是面著色所需的圖形表示形式。著色所需的圖形表示形式。2022-1-62022-1-63.4.1 區域的表示和類型區域的表示和類型 點陣表示分兩種情況，一種稱為內點表示，如圖點陣表示分兩種情況，一種稱為內點表示，如圖317所示，另一種稱為邊界表示，如圖所示，另一種稱為邊界表示，如圖3-18所示。所示。 內點表示：內點表示：區域內的所有像素著同一顏色，而區域外的區域內的所有像素著同一顏色，而區域外的所有像

45、素具有另一種顏色；所有像素具有另一種顏色； 邊界表示：邊界表示：區域邊界上的所有像素點具有特定的顏色區域邊界上的所有像素點具有特定的顏色（可以是填充色），在區域內的所有像素均不能具有這一（可以是填充色），在區域內的所有像素均不能具有這一特定色，而且邊界外的像素不能具有與邊界相同的顏色。特定色，而且邊界外的像素不能具有與邊界相同的顏色。2022-1-62022-1-6o區域填充算法要求區域是連通的。區域填充算法要求區域是連通的。因為只有在連通區域中，才可能將種子點因為只有在連通區域中，才可能將種子點的顏色擴展到區域內的其它點。的顏色擴展到區域內的其它點。o但是由像素構成的但是由像素構成的“區域區域”有一定的特殊性，因此被區分為兩種連通性區域：有一定的特殊性，因此被區分為兩種連通性區域： 四四連通區域和八連通區域。連通區域和八連通區域。 四連通區域四連通區域指的是從區域上一點出發，可通過四指的是從區域上一點出發，可通過四個方向，即上、下、左、右移動的組合，在不越出區域的前提下，到達個方向，即上、下、左、右移動的組合，在不越出區域的前提下，到達區域內的任意像素。區域內的任意像素。八連通區域八連通區域指的是從區域內每一像素出發，