1、Chapter 3 Basic Raster Graphics Algorithms for Drawing 2D Primitives基本二維圖元的生成算法Scan-conversion掃描轉(zhuǎn)換）: 確定圖形對應(yīng)的象素集合及其顏色，用于顯示一個圖形的過程，也稱為圖形的光柵化。本章內(nèi)容(outline)n直線的掃描轉(zhuǎn)換n(SCAN CONVERTING LINES)n圓與橢圓的掃描轉(zhuǎn)換n(SCAN CONVERTING CIRCLE AND ELLIPSE)n區(qū)域填充(FILLING REGION)n字符生成(GENERATING CHARACTERS)n反走樣(ANTIALIASING)n二

2、維裁剪(2D CLIPPING)圖形掃描轉(zhuǎn)換(scan-conversion)Scan-conversion: 確定圖形對應(yīng)的象素集合及其顏色，用于顯示一個圖形的過程，稱為圖形的掃描轉(zhuǎn)換或光柵化。圖形掃描轉(zhuǎn)換分為兩步：1、確定有關(guān)組成圖形的象素；2、用圖形的顏色或其他屬性對象素進行寫操作。 第2步通常是通過調(diào)用設(shè)備驅(qū)動程序完成的，不屬于計算機圖形學的研究范圍。計算機圖形學研究前者，即如何確定最佳逼近于圖形的象素集。問題 給定直線段的兩個端點P0(x0,y0)和P1(x1,y1)， 把其在光柵掃描顯示器上顯示出來.描畫 理想的直線段:沒有線寬,由無數(shù)個點構(gòu)成 光柵掃描顯示器上:有限個不重疊象素組

3、成SCAN CONVERTING LINES(直線的掃描轉(zhuǎn)換)p0p1最佳表示最佳表示:用最靠近理想直線的一些網(wǎng)格點象用最靠近理想直線的一些網(wǎng)格點象素來代表直線即確定最佳的最近點和最大素來代表直線即確定最佳的最近點和最大似點的集合）。似點的集合）。直線的表示直線的表示(the representation of lines)數(shù)值微分法1）(DDA-Digital Differential Analyzer) 記：,0101xxyym是 線 段 的 斜 率， 則 線 段 方 程 為：Bmxy)011001(xxyxyxB中其。 1:1iixx令X的變化大于y的變化方法：10 m假設(shè)最簡單方法：利

4、用直線方程直接計算象素集。但方法最簡單方法：利用直線方程直接計算象素集。但方法用到了浮點數(shù)的乘法，加法和取整運算，影響效率。用到了浮點數(shù)的乘法，加法和取整運算，影響效率。數(shù)值微分法(2)mBmxiBmxyii11:則Bxmi)1(myi令yir= round(yi)其中，round（）表示對yi進行四舍五入。則所求點坐標為(xi+1, round(yi+1)其中, xi+1 = xi +1, yi+1 = yi +m;數(shù)值微分法(3)數(shù)值微分法(4)n待解決問題n 假設(shè)|m|1,則x向每變化1個單位,y向有可能超出1個步長。p1p0解決方法：此時應(yīng)令yi 為自變量。數(shù)值微分法(5),max(y

5、xt在算法中若能保證在一個方向上增量為1，在另一個方向的增量 1，就能保證產(chǎn)生最大似點集，從而克服前述問題。最大步長(步距)t步進方向: 的方向數(shù)值微分法(6)void Line ( /* Assumes -1ml,x0 x1 */ int x0, int y0, /* Left endpoint */ int x1, int y1, /* Right endpoint */ int value) /* Color value to place in lines pixels */ int x; /* x runs from x0 to x1 in unit increments*/ doub

6、le dy = y1 y0: double dx = x1 - x0; double m = dy / dx; double y = y0; for (x = x0; x = x1; x+) PutPixel (x, Round (y), value); /* Set pixel to value */ y += m; /* Step y by slope m */ /* Line */ The incremental line scan-conversion algorithm.n算法優(yōu)點：簡單、自然，消除了最簡單方法中的算法優(yōu)點：簡單、自然，消除了最簡單方法中的浮點數(shù)的乘法。浮點數(shù)的乘法。

7、n算法缺點：用到了浮點加法運算和取整運算，計算法缺點：用到了浮點加法運算和取整運算，計算效率低。算效率低。n自變量的選擇可根據(jù)斜率確定，以得到最佳的直自變量的選擇可根據(jù)斜率確定，以得到最佳的直線效果：線效果：為自變量。時，以當為自變量；時，以當xmym11數(shù)值微分法(7)中點畫線法 (Midpoint Line Algorithm) （1）n問題引出問題引出n 為解決為解決DDA算法中需要浮點數(shù)進算法中需要浮點數(shù)進行加運算，且輸出時需取整的不利條行加運算，且輸出時需取整的不利條件，可以用中點畫線法。件，可以用中點畫線法。n 假設(shè)直線的斜率假設(shè)直線的斜率m0,1，兩個，兩個端點分別是端點分別是x

8、0,y0）,（x1,y1）。）。P(xp,yp)P1(xp+1,yp)中點判別方法示意圖QP2(xp+1,yp+1)MMidpoint Line Algorithm(2)思想思想當 前 一 點 已 確 定當 前 一 點 已 確 定 , , 用用P(xp,yp)P(xp,yp)來代表時，下一來代表時，下一點僅可能在點僅可能在P1P1和和P2P2中選中選用用M M表示表示P1,P2P1,P2的中點，的中點，M(xp+1,yp+0.5)M(xp+1,yp+0.5)。Q Q是理想直線上是理想直線上x=xp+1x=xp+1處的點處的點. .比較比較M M和和Q Q的位置關(guān)系的位置關(guān)系, ,可以確定下一點

9、的走向可以確定下一點的走向. .比較比較M和和Q:若若M位于位于Q的下方的下方,即即yM yQ ,則應(yīng)取則應(yīng)取p1點點;準繩：準繩： 當兩侯選點的中當兩侯選點的中點落在直線下方時，點落在直線下方時，選較高點，否則選選較高點，否則選較低點。較低點。Midpoint Line Algorithm (3)P(xp,yp)P1(xp+1,yp)中點判別方法示意圖QP2(xp+1,yp+1)MMidpoint Line Algorithm (4)n定義直線函數(shù)：cbyaxyxf),(位于直線上方位于直線上位于直線下方),(0),(0),(0),(yxyxyxyxfn特點：由于Q點的 f(xQ, yQ)=

10、0，若能計算出中點M的f(xM, yM)的正負，則可判定出Q點和M點的位置關(guān)系。其中：ay0y1，bx1x0，cx0y1x1y0Midpoint Line Algorithm (5)nDefine decision function(構(gòu)造判別函數(shù))：cbyaxyxf),()21, 1()(ppyxfMfdnDefine decision variable(引入判別參數(shù)):其中：ay0y1，bx1x0，cx0y1x1y0Midpoint Line Algorithm (6)n算法描述： 斜率m0,1時n問題：如何快速計算判別參數(shù)的值？采用增量計算方法優(yōu)化判別參數(shù)的計算)1, 1(0), 1(02

11、1ppppyxPdyxPd為：時，下一點應(yīng)取當；為：時，下一點應(yīng)取當P(xp,yp)P1(xp+1,yp)QP2(xp+1,yp+1)M的增量計算公式為例，推導以d10 mdddii1即找到遞推關(guān)系式：),(iiyx)5 . 0, 1(iiiyxfd)5 . 0, 2(), 1(),( :0) 1 (111iiiiiiiiyxfdyxyxd當如黃色線所示情形Midpoint Line Algorithm (7)cybxayxfdiiiii)5 . 0()2()5 . 0, 2(1acybxaii)5 . 0() 1(adiadddif0Midpoint Line Algorithm (8)cy

12、bxayxfdiiiii)5 . 1()2()5 . 1, 2(1bacybxaii)5 . 0() 1(badibadddif0),(iiyx)5 . 1, 2() 1, 1(),( :0)2(111iiiiiiiiyxfdyxyxd當如藍色線所示情形Midpoint Line Algorithm (9)cybxayxfdstart)5 . 00() 10()5 . 00, 10(bacbyax5 . 000q第一個決策變量 dstart 為q第1個中點在 (x0+ 1, y0+0.5), badstart5 . 0由于x0，y0點在直線上，ax0by0c0，那么算法的遞推公式是：0.5b

13、a d,00 startyyxx初值：,110,10baddyyxxdaddyyxxd，若，若Midpoint Line Algorithm (10)遞推公式：d的初值中存在小數(shù)。由于判別時只考慮d的符號，且d的增量都是整數(shù)，為消除浮點數(shù)計算，可在d的計算公式兩側(cè)同乘2。并仍用d表示2d。),(iiyx算法公式是：b 2a d,00 startyyxx初值：,22110,210baddyyxxdaddyyxxd，若，若Midpoint Line Algorithm (11)問題：以上分析過程只考慮了直線斜率m0,1的情況。遞推公式：),(iiyx1為，直線上離散點的步長設(shè)直線斜率為k10k1k

14、01k1kMidpoint Line Algorithm (12)；，時，侯選點分別為：當；，時，侯選點分別為：當；，時，侯選點分別為：當；，時，侯選點分別為：當) 1, 1() 1,(1) 1, 1() 1,(1) 1, 1(), 1(01) 1, 1(), 1(10yxyxkyxyxkyxyxkyxyxk 此時，可利用兩候選點的中點與直線的位置關(guān)系，選出更接近直線的候選點)2,2(),(),(21212211yyxxyxyx的中點坐標為與Midpoint Line Algorithm (13)點/線位置關(guān)系的判別計算1) 1, 5 . 0(1) 1, 5 . 0(01)5 . 0, 1(1

15、0)5 . 0, 1(kyxfdkyxfdkyxfdkyxfdiiiiiiiiiiii判別公式為：采用增量計算方法優(yōu)化判別公式的計算10k1k01k1kMidpoint Line Algorithm (14)例：用中點畫線法光柵化一條連接兩點(0,0)和(5,2)的直 線段，寫出計算過程。)01() 10(220 xxyybadExample(1)15) 2(200yx，初值： 斜率 m=(20)/(5-0)=0.4,22110,210baddyyxxdaddyyxxd，若，若5x0-x1b -2,y1-y0axydOut pixel初始124450123450011221-33-151(0,

16、0)(1,0)(2,1)(3,1)(4,2)(5,2)遞推如下：Example(2)45632100 1 2 33 4 5 6 7The midpoint line from point (0, 0) to point (5, 2).Example(3)P(xi,yir)P1(xi+1,yir)Bresenham 判別方法示意圖QP2(xi+1,yir+1)Bresenham Line Algorithm(1)MP(xi,yi)(xi+1,yi+1)構(gòu)造判別參數(shù): i+1= yi+1 - yir 0.5Bresenham Line Algorithm(2)判別參數(shù)：i+1= yi+1 - yi

17、r 0.5 當i+10 時， 選擇P2(xi+1,yir+1)點 當i+1 0時， 選擇P1(xi+1,yir)點采用增量計算方法優(yōu)化判別參數(shù)的計算第i+2次的i+2 yi+2 yi+1r 0.5 Bresenham Line Algorithm(3)第i+1次的i+1= yi+1 - yir 0.5第i+2次的i+2 yi+2 yi+1r 0.5 (a)若在 i+1次時，i+1 0， 則選擇P1(xi+1,yir)點i+2 =yi+2 yi+1r 0.5= yi+1 + m yir 0.5= i+1 + mBresenham Line Algorithm(3)第i+2次的i+2 yi+2 yi+1r 0.5 (b) 若在 i+1次時，i+1 0，則選擇P2(xi+1,yir+1)點i+2 = yi+1 + m （yir+1) 0.5= i+1 + m 1由此可得如下遞推公式初值： x = x0 , y = y0 = y1 y0