【正文】 計算機圖形學 福建師范大學 計算機圖形學 翁彬 計算機圖形學 福建師范大學 第 2章 光柵圖形學 計算機圖形學 福建師范大學 ? 什么是光柵圖形學？ ? ? 光柵顯示器 － 圖形光柵化、 ? 光柵化圖形的處理 ? 計算機圖形學 福建師范大學 ?光柵圖形學的研究內(nèi)容 掃描轉(zhuǎn)換 算法 掃描轉(zhuǎn)換 算法 掃描轉(zhuǎn)換 與 區(qū)域填充 計算機圖形學 福建師范大學 直線段的掃描轉(zhuǎn)換算法 ?直線的掃描轉(zhuǎn)換： 確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。 ?三個常用算法： 數(shù)值微分法（ DDA） 中點畫線法 Bresenham算法。 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 基本思想 ? 已知過端點 的直線段 L： ? 直線斜率為 ? 從 的左端點 開始，向 右端點步進。步長=1(個象素 )，計算相應(yīng)的 y坐標 ；取象素點 (x, round(y))作為當前點的坐標。 ? 這種方法直觀，但效率太低，因為每一步需要一次浮點乘法、一次加法和一次舍入運算。 ) , ( ), , ( 1 1 1 0 0 0 y x P y x P 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 –作為最底層的光柵圖形算法，在通常的 CAD/圖形系統(tǒng)中，會被大量應(yīng)用，因此，哪怕節(jié)約一個加法或減法，也是很了不起的改進。 –由此出發(fā)點，導(dǎo)致增量算法的思想。 –增量算法： 在一個迭代算法中，如果每一步的 x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 計算 ? 當 時 。 ? 即：當 x每遞增 1， y遞增 k(即直線斜率 )； ? 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 例： 畫直線段 ? k ? = ? x y int(y+) y+ ? 0 0 0 0 ? 注： 網(wǎng)格點表示象素 0 1 2 3 4 5 3 2 1 Line: P0(0, 0) P1(5, 2) 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 例： 畫直線段 ? x int(y+) y+ ? 0 0 0 ? 1 0 + ? 2 1 + ? 3 1 + ? 4 2 + ? 5 2 + ? 注： 網(wǎng)格點表示象素 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? void DDALine(int x0,int y0,int x1,int y1,int color) ? ? ? int x； ? float dx, dy, y, k。 ? dx= x1x0, dy=y1y0。 ? k=dy/dx, y=y0。 ? for (x=x0。 x?x1, x++) ? ? drawpixel (x, int(y+), color)。 ? y=y+k。 ? ? ? ? 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 注意上述分析的算法僅適用于 ?k? ≤ 1的情形。在這種情況下， x每增加 1, y最多增加 1。 ? 問題： ? 當 ?k? ?1時，會如何？ (答案見下頁 ) ? ?k? 1 示意圖 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ? 當 ?k? ?1時，必須把 x， y地位互換，y每增加 1， x相應(yīng)增加 1/k。 計算機圖形學 福建師范大學 數(shù)值微分 (DDA)法 ?缺點： ? 在此算法中， y、 k必須是 float，且每一步都必須對 y進行舍入取整，不利于硬件實現(xiàn)。 計算機圖形學 福建師范大學 DDA算法小結(jié) ? 直線的顯式方程（兩點式） ? 象素是整數(shù)的（ x每次增加 1，取象素點 (x, round(y)) ） ? 最簡單算法 ? 效率低 ? 改進為增量算法（當 x每遞增 1， y遞增 k ） 計算機圖形學 福建師范大學 ?采用增量思想的 DDA算法，每計算一個象素，只需計算一個加法，是否最優(yōu)？ ?如非最優(yōu)，如何改進？ ?目標：進一步將一個加法改為一個整數(shù)加法。 ?新思路－ DDA算法采用兩點式，可否采用其他的直線表示方式？ 計算機圖形學 福建師范大學 中點畫線法 ?基本思想 ?當前象素點為 (xp, yp) 。下一個象素點為 P1 或 P2 。 ?設(shè) M=(xp+1, yp+)，為 p1與 p2 ?之中點， Q為理想直線與 x=xp+1 ?垂線的交點。將 Q與 M的 y坐標進 ?行比較。 –當 M在 Q的下方 P2離直線更近更近 取 P2 。 –M在 Q的上方 P1離直線更近更近 取 P1 –M與 Q重合， P P2任取一點。 計算機圖形學 福建師范大學 中點畫線法 問題：如何判斷 M與 Q點的關(guān)系？ 計算機圖形學 福建師范大學 中點畫線法 ? 假設(shè)直線方程為： F(x,y)=ax+by+c=0 ? 其中 a=y0y1, b=x1x0, c=x0y1x1y0 ? 由常識知： ? ∴ 欲判斷 M點是在 Q點上方還是在 Q點下方 ，只需把 M代入 F(x,y),并檢查它的符號 。 ? ?? ?? ?????????點在直線下方點在直線上方點在直線上面0,0,0,yxFyxFyxF計算機圖形學 福建師范大學 中點畫線法 ?構(gòu)造判別式 :d=F(M)=F(xp+1,yp+) ? =a(xp+1)+b(yp+)+c ? 其中 a=y0y1, b=x1x0, c=x0y1x1y0 ?當 d0， M在 L(Q點 )下方，取右上方 P2為下一個象素； ?當 d0， M在 L(Q點 )上方，取右方 P1為下一個象素； ?當 d=0，選 P1或 P2均可，約定取 P1為下一個象素； 計算機圖形學 福建師范大學 中點畫線法 ? 但這樣做，每一個象素的計算量是 4個加法 ， 兩個乘法 。 ? d=a(xp+1)+b(yp+)+c 計算機圖形學 福建師范大學 中點畫線法 ? 如果也采用增量算法呢？ 計算機圖形學 福建師范大學 中點畫線法 ? d是 xp, yp的線性函數(shù)，因此可采用增量計算，提高運算效率。 ? d=a(xp+1)+b(yp+)+c 計算機圖形學 福建師范大學 中點畫線法 ?若當前象素處于 d?0情況，則取正右方象素 P1 (xp+1, yp ), 要判下一個象素位置，應(yīng)計算 ? d1=F(xp+2, yp+) ? =a(xp+2)+b(yp+)+c=d+a； ? 增量為 a ? d=a(xp+1)+b(yp+)+c 計算機圖形學 福建師范大學 中點畫線法 ?若 d0時，則取右上方象素 P2 (xp+1, yp+1)。要判斷再下一象素，則要計算 ? d2= F(xp+2, yp+) ? =a(xp+2)+b(yp+)+c=d+a+b ； ? 增量為 a＋ b ? d=a(xp+1)+b(yp+)+c 計算機圖形學 福建師范大學 中點畫線法 ? 至此，至少新算法可以和 DDA算法一樣好。 ? 能否再做改進？ 計算機圖形學 福建師范大學 中點畫線法 ? 能否實現(xiàn)整數(shù)運算？ 計算機圖形學 福建師范大學 中點畫線法 ? 畫線從 (x0, y0)開始， d的初值 ? d0=F(x0+1, y0+) ? = a(x0 +1)+b(y0 +)+c ? = F(x0, y0)+a+ = a+ 。 ? 由于只用 d 的符號作判斷，為了只包含整數(shù)運算 , ? 可以用 2d代替 d來擺脫小數(shù)，提高效率。 ? 令 d0=2a+b, d1=2a, ? d2=2a+2b,我們有如下算法 。 計算機圖形學 福建師范大學 中點畫線法 void Midpoint Line (int x0,int y0,int x1, int y1,int color) ? { int a, b, d1, d2, d, x, y。 a=y0y1, b=x1x0, d=2*a+b。 d1=2*a, d2=2* (a+b)。 x=x0, y=y0。 drawpixel(x, y, color)。 while (xx1) { if (d0) {x++, y++, d+=d2。 } else {x++, d+=d1。} drawpixel (x, y, color)。 } /* while */ } /* mid PointLine */ 計算機圖形學 福建師范大學 中點畫線法 ? 例： 用中點畫線法 ? ? i xi yi d ? 1 0 0 1 ? 2 1 0 3 ? 3 2 1 3 ? 4 3 1 1 ? 5 4 2 5 計算機圖形學 福建師范大學 中點畫線法小結(jié) ? 中點與交點位置來判斷象素選取 ? 引入直接的隱式方程 F(x,y)=ax+by+c=0 ? 但計算量大，故又改進為增量算法（此處，增量分兩種情況） ? 為進一步提高效率，修改為全是整數(shù)計算的算法（ 2d代替 d ，同時增量也做相應(yīng)調(diào)整） 計算機圖形學 福建師范大學 中點畫線法 ?思考題： P55 ? 22 用中點畫線法掃描轉(zhuǎn)換從點（ 1,0）到（ 4,7）經(jīng)過的直線段，并給出每一步的判別值。 計算機圖形學 福建師范大學 – DDA算法采用點斜式，中點法采用隱式表示。 –中點法可以有整數(shù)算法。 –其他表示可以推出整數(shù)算法嗎？ 計算機圖形學 福建師范大學 Bresenham算法 ?基本思想 過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列象素中與此交點最近的象素。 計算機圖形學 福建師范大學 Bresenham算法 ?設(shè)直線方程為： ，其中k=dy/dx。 因為直線的起始點在象素中心，所以誤差項 d的初值 d0＝ 0。 ?X下標每增加 1， d的值相應(yīng)遞增直線的斜率值 k，即 d＝ d＋k。 –當 d≥ ，選擇當前象素的右上方象素（