1、 余 敦 輝湖北大學 數計學院計算機圖形學1 余 敦 輝計算機圖形學1第五章 基本圖形生成算法光柵掃描圖形系統的結構光柵掃描特點： * 數據量大 快的要求 * 顯示的離散化 準的要求 * 獨立的圖形顯示處理器 快速，實時硬件處理的掃描轉換CPU系統總線顯示處理器系統存儲器顯示處理器存儲器幀緩存視頻控制器I/O設備監視器2第五章 基本圖形生成算法光柵掃描圖形系統的結構光柵掃描特第五章 基本圖形生成算法圖形顯示處理器 (加速引擎)任務：進行掃描轉換(Scan Conversion)掃描轉換：將應用程序給出的圖形定義數字化為一組像素強度值，并放到幀緩存器掃描轉換的工作內容：基本圖形的生成字符的生成填

2、充、裁剪線型的處理彩色處理某些變換和管理3第五章 基本圖形生成算法圖形顯示處理器 (加速引擎)任務第五章 基本圖形生成算法坐標系統為描述對象、構造場景或完成圖形變換，需要不同的坐標系！建模坐標系定義對象2. 世界坐標系定義對象與外界環境的關系3. 設備坐標系 定義圖形顯示的位置、大小4. 規范化坐標 為保證互換性（與設備無關）而定義的輔助坐標4第五章 基本圖形生成算法坐標系統為描述對象、構造場景或完第五章 基本圖形生成算法坐標系統建模坐標Modeling CoordinateLocal CoordinateMaster Coordinate世界坐標World Coordinate繪圖儀其它輸出

3、設備設備坐標Device CoordinateScreen Coordinate111規范化坐標NormalizedCoordinate5第五章 基本圖形生成算法坐標系統建模坐標Modelin第五章 基本圖形生成算法5.1 直線的掃描轉換光柵掃描顯示下畫直線存在的問題：(1) 顯示速度問題： 例：分辨率：1024768， 24Bit 彩色， 幀存容量：10247683 2,359,296 Byte 刷新率 85Hz: 85 2,359,296 200,540,160 (Byte / S) 存儲器讀出時間：5nS(2) 顯示質量問題：階梯狀線的粗細不一線的亮度差異6第五章 基本圖形生成算法5.1

4、 直線的掃描轉換光柵掃描顯第五章 基本圖形生成算法5.1 直線的掃描轉換直線的繪制要求：1.直線要直2.直線的端點要準確，即無定向性和斷裂情況3.直線的亮度、色澤要均勻4.畫線的速度要快5.要求直線具有不同的色澤、亮度、線型等解決的問題：給定直線兩端點P0(x0,y0)和P1(x1,y1)，畫出該直線。7第五章 基本圖形生成算法5.1 直線的掃描轉換直線的繪第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.1 數值微分法(DDA法)直線的微分方程：DDA算法原理： =1/max(|x|,|y|) 8第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的

5、掃描轉換5.1.1 數值微分法(DDA法)max(|x|,|y|)=|x|，即|k|1的情況：max(|x|,|y|)=|y|，此時|k|1：9第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.1 數值微分法(DDA法)注意：round(x)=(int)(x+0.5)10第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.1 數值微分法(DDA法)Void DDAline(int x0,int y0,int x1,int y1) int dx,dy,eps1,k; float x,

6、y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; x=x0; y=y0; If (abs(dx)abs(dy) eps1=abs(dx); else eps1=abs(dy); xIncre=(float)dy/(float)eps1; yIncre=(float)dy/(float)eps1; for (k=0;k=eps1;k+) putpixel(int)(x+0.5),(int)(y+0.5); x+=xIncre; y+=yIncre; 11第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1.1 數值微

7、分法(DDA法)特點：增量算法直觀、易實現缺點：浮點運算、取整廢時，且不利于硬件實現。不利于用硬件實現 。12第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1.2 中點畫線法算法5.1.2 中點畫線法算法原理：假定直線斜率K1，且已確定點亮象素點P（Xp ,Yp ）M為中點，Q為交點現需確定下一個點亮的象素。顯然可得出如下結論：若M在Q的下方，選Pu，否則選Pd13第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1.2 中點畫線法算法算法實現： 假設直線的起點、終點分別為：（X

8、0,Y0),(X1,Y1) 該直線方程可表示為： F(x,y)=a*x+b*y+c （1） 其中： a=Y0-Y1, b=X1-X0, c=X0*Y1-X1*Y0 當： F(Xt,Yt) = 0 (Xt,Yt) 在直線上 F(Xt,Yt) 0 (Xt,Yt) 在直線上方14第五章 基本圖形生成算法5.1 直線的掃描轉換 5.1第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.2 中點畫線法算法15第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.2 中點畫線法算法 因此：將中點M坐標代入（1）式，并判斷其符號即可確定象素點的選取。構

9、造如下判別式： d = F(M) =F(Xp+1,Yp+0.5) =a(Xp+1)+b(Yp+0.5)+c 由上式可看出，d是x,y線性函數，可推導d的增量公式16第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.2 中點畫線法算法當d 0 時， 取象素Pu，此時再下一個象素的判別式為：d= F(Xp+2,Yp+1.5) = a(Xp+2)+b(Yp+1.5)+c = a(Xp+1)+b(Yp+0.5)+c +a +b = d + a + b;誤差項的遞推d= 0時，取象素Pd，此時再下一個象素的判別式為：d= F(Xp+2,Yp+0.

10、5) = a(Xp+2)+b(Yp+0.5)+c = a(Xp+1)+b(Yp+0.5)+c +a = d + a;誤差項的遞推d0：18第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.2 中點畫線法算法d的初始值可按下式計算： d0 = F(X0+1,Y0+0.5) = a(X0+1)+b(Y0+0.5)+c = F(X0,Y0)+a+0.5b = a+0.5b 由于只用d 的符號作判斷，為了只包含整數運算, 可取2d代替 d，這樣可得如下中點算法程序：19第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算

11、法5.1 直線的掃描轉換5.1.2 中點畫線法算法 MidpointLine(X0,Y0,X1,Y1,Color) int X0,Y0,X1,Y1,Color; int a,b,d1,d2,d,x,y; a=Y0-Y1; b=X1-X0; d=a+a+b; d1=a+a; d2=a+b+a+b; x=X0; y=Y0; drawpixle(x,y,Color); while(xX1) if(d0) x+; y+; d+=d2; 20第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.2 中點畫線法算法 else x+; d += d1;

12、drawpixle(x,y,Color); /*while*/ /*MidPointLine*/ 習題： 按照中點劃線算法，確定直線（0，0）（5，3）的點亮象素。列出計算過程，并列出所選象素坐標。 21第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.3 Bresenham畫線算法5.1.3 改進的Bresenham算法基本原理：(假定直線段的0k1)22第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.3 Bresenham畫線算法假定直線斜率,0k1 時 d=d-1 ;當d

13、0.5，則(x,y)更新為(x+1,y+1)，同時將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結束。24第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.3 Bresenham畫線算法改進1：令e=d-0.5e初= -0.5，每走一步有e=e+k。if (e0) then e=e-125第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.3 Bresenham畫線算法算法步驟為：1.輸入直線的兩端點P0(x0,y0)和P1(x1,

14、y1)。2.計算初始值x、y、e=-0.5、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+k，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結束。26第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.3 Bresenham畫線算法改進2：用2ex來替換ee初= -x，每走一步有e=e+2y。if (e0) then e=e-2x27第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.第五章 基本圖形生成算法5.

15、1 直線的掃描轉換5.1.3 Bresenham畫線算法算法步驟：1. 輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2. 計算初始值x、y、e=-x、x=x0、y=y0。3. 繪制點(x,y)。4. e更新為e+2y，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2x；否則(x,y)更新為(x+1,y)。5. 當直線沒有畫完時，重復步驟3和4。否則結束。28第五章 基本圖形生成算法5.1 直線的掃描轉換5.1.程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,d

16、x,dy; float k,e; int e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; e = -dx; for( i=0; i 0) e = e - 1; e = e - 2*dx; if(e =0) y+; 29程序如下： BresenhamLine(x0,y0, Bresenham 畫線例直線端點為(20,10)和（30,18), 用 Bresenham 法畫線解： Dx 10， Dy 8， k = Dy / Dx = 0.8， 2 Dy 16， 2Dx 20 e0 Dx 10 畫初始點(20, 10), 并根據判

17、別式確定沿線段路徑的后續像素位置如下表：29212223242526202827101817161513141211193030 Bresenham 畫線例29212223242526第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.1 圓的對稱性利用八分圓的對稱性特點，可以簡化圓的掃描轉換算法。如果圓的圓心在原點，則可以由其中某個八分圓的圓周上的某點（x，y）計算出其他七個八分圓圓周上對應的點的坐標。由此可構造相應算法，由圖中陰影的圓周復制生成整個圓周。31第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.1第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.1 圓的對稱性算法如下：in

18、t Circle_Points(x,y,value)int x,y,value; drawpixel(x,y,value); drawpixel(x,-y,value); drawpixel(-x,y,value); drawpixel(-x,-y,value); drawpixel(y, x, value); drawpixel(-y, x, value); drawpixel(y, -x, value); drawpixel(-y, -x, value);32第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.1第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2 角度DDA畫圓算法1、

19、角度DDA法若已知圓的方程： x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 =x n - (y n - y 0 )d y n+1 =y n + (x n - x 0 )d33第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2 角度DDA畫圓算法角增量(弧度)的選取：d /(n-1)n越大，點越多，速度越慢。所以在不同的精度下，對于不同的半徑給定不同的d：使 max(|x|， |y|) 1因： x = - ( y

20、n y0) d y = ( xn x0) d即 max(| ( yn y0) d |， | ( xn x0) d |) 1又因為 | yn y0 |， | xn x0 | 最大是R所以：R| d | 1 | d | 1/R絕對值表示畫圓弧有順時針和逆時針之別，為精度計，取 | d | 1/(R+1)34第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2 角度DDA畫圓算法算法：Arcdda（xc，yc，r，a1，a2，color）int xc，yc，r，color；double a1，a2； int i,steps,x,y； doubl

21、e da,radin; da = 1/(r1）； radin a2 - a1; steps = radin/da; x = r*cos(a1); y = r * Sin(a1); for(i = 0;i steps;i+) drawpixel( x+xc , y+ yc , color ); x = x y*da ; y = y+ x*da ; 35第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.2第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法利用圓的對稱性，只須討論1/8圓(第一象限中的第二個八分圓)。解決問題：36第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.

22、3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法基本原理：假設P（Xp+1，Yp）為當前點亮象素，那么，下一個點亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。37第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法 2)推導過程： 構造一函數： F（X，Y）=X2 + Y2 - R2 F（X，Y）= 0 （X，Y）在圓上； F（X，Y） 0 （X，Y）在圓外。 M為P1、P2間的中點，M=(Xp+1,Yp-0.5) 有如下結論： F（M）= 0 取P238第五章 基本圖形生成算法5.

23、2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法 構造判別式 d = F(M)= F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d=0, 則P2 為下一個象素，那么再下一個象素的判別式為： d = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + 2(xp - yp) + 5 即d 的增量為 2 (xp - yp) +5.40第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2

24、.3 中點畫圓法算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當xy時，重復步驟3和4。否則結束。41第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法MidpointCircle(r, color) int r, color; int x,y; float d; x=0;

25、 y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+； else d+ = 2*(x-y) + 5; x+;y-; 42第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法改進1：用d-0.25代替d算法步驟：1.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)

26、+5，再將(x,y)更新為(x+1,y-1)。5.當xy時，重復步驟3和4。否則結束。令ed0.25 e1R則 d 0 e 0.25而e為整數，則e 0.25等價于e 0。再將e仍用d來表示43第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法改進2：因判別式d的增量是x，y的線性函數。 每當x遞增1，d遞增 x 2； 每當y遞增1，d遞減 y 2； 由于初始象素為（0，r），所以x 的初值為3， y 的初值為2r2。再注意到乘2運算可以改用加法實現，至此我們可寫出不含乘法，僅用整數實現的中點畫圓算法。44第五章 基本圖形生

27、成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 中點畫圓法MidpointCircle(r, color) int r, color; int x,y，deltax，deltay，d; x=0; y=r; d=1-r; deltax=3; deltay=2-r-r; drawpixel(x,y,color); while(xy) if(d0) d+ = deltax; deltax+=2; x+； else d+ = (deltax+deltay); deltax+=2;deltay+=2; x+; y-; 45第五章 基本圖形生成算法5.2 圓的掃

28、描轉換5.2.3例題：畫第一象限中，半徑 R10， 圓心在原點的圓弧解：起點為(x0, y0) (0, 10) e0 1R 9； (x1, y1)(1, 10) e1 e0 2x0 +3 6； (x2, y2)(2, 10) e2 e1 2x1 +3 1； (x3, y3)(3, 10) e3 e2 2x2 +3 6； (x4, y4)(4, 9) e4 e3 2(x3 y3 ) + 5 3；(x5, y5)(5, 9) e5 e4 2x4 + 3 8； (x6, y6)(6, 8) e6 e5 2(x5 y5 ) + 5 5； (x7, y7)(7, 7)912345608719876453

29、21010若 ei ei1 ei + 2xi + 3ei=0, ei1 ei + 2(xi yi ) + 546例題：畫第一象限中，半徑 R10， 圓心在原點的圓弧解：起第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 Bresenham畫圓法5.2.3. Bresenham畫圓算法 為討論方便，僅考慮圓心在原點，半徑為R的第一象限上的一段圓弧。且取（0，R）為起點，按順時針方向繪制該1/4圓弧。47第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 Bresenham畫圓法原理 ： 如圖1-3所示，從當前點亮象素出發，按順時針方

30、向生成圓時，最佳逼近該圓的下一個象素只可能為H、D、V三象素之一。H、D、V中距圓周邊界距離最小者，即為所求的象素點。48第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 Bresenham畫圓法算法： H、D、V三點到圓心的距離平方與圓的半徑平方差，即為H、D、V到圓弧距離的一種度量： H = (x+1)2 + y2 - R2; D = (x+1)2 + (y-1)2 - R2; V = x2 + (y-1)2 - R2;49第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3

31、 Bresenham畫圓法為了根據這些度量值可確定最佳象素點，首先，將H、D、V與理想圓弧的關系進行分類。存在以下五種情況： 1）H、D、V全在圓內； 2）H在圓外，D、V在圓內； 3）D在圓上，H在圓外，V在圓內； 4）H、D在圓外，V在圓內； 5）H、D、V全在圓外。與Bresenham畫線算法一樣，按照上述不同類型，找出誤差度量的遞推公式，然后判別它的正、負性即可確定最佳逼近的象素點。50第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 Bresenham畫圓法當D 0 , 只可能為1或2種情況。為了確定是H還是D，可用如下判別

32、式： HD = | H | - | D | HD 0 則應選H，否則選D。51第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3第五章 基本圖形生成算法5.2 圓的掃描轉換5.2.3 Bresenham畫圓法對于第2種情況： HD = H + D = (x+1)2 + y2 - R2 + (x+1)2 + (y-1)2 - R2 =2 D + 2y - 1 對于第1種情況： y是x的單調遞減函數H為下一點亮象素。 另，此時H 0 和 D 0 H + D = 2 D + 2y - 1 =0) drawpixel(x,y,color); if(delta 0) d1 = 2* (delta +

33、 y) -1; if(d1 0) d2 = 2*(delta-x)-1; if(d2 0；對于橢圓內的點，F(x,y) x分量y分量 0，取Pd(xi+1,yi-1)66第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.1 橢圓的中點Bresenham算法誤差項的遞推情況一：d10：67第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.1 橢圓的中點Bresenham算法誤差項的遞推情況二： d10：68第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.1 橢圓的中點Bresenham算法上半部判別式的初始值： 初始點（0，b）候選點（1，b-1）（1，b）中 點 （1，b-0.5）69第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.1 橢圓的中點Bresenham算法再來推導橢圓弧下半部分的繪制公式判別式 誤差項的遞推 判別式的初值70第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.第五章 基本圖形生成算法5.3 橢圓的掃描轉換5.3.