光柵圖形生成算法ppt課件(已修改)
2025-05-18 04:02 本頁面
【正文】 Ch3 光柵圖形生成算法 ? 光柵顯示器顯示的圖形是用一系列緊靠該圖形路徑的像素表示的。 ? 確定哪些像素能構(gòu)成所需圖形的過程稱為 圖形的光柵化 (也稱 光柵圖形生成算法 )，或稱為圖形的掃描轉(zhuǎn)換 。 本章討論內(nèi)容 ? 直線生成算法 ? 圓和圓弧的程序設(shè)計 ? 區(qū)域填充算法 ? 字符生成 ? 反走樣技術(shù) 直線生成算法 ? 直線是最基本的圖元，曲線由一系列直線段逼近，復(fù)雜圖形可看作是由無數(shù)直線段組成的。直線生成質(zhì)量影響計算機圖形設(shè)計的質(zhì)量。因此， 光柵化直線生成算法 必須服從四條 原則：直而光滑、端點準(zhǔn)確、亮度均勻、速度快。 直線生成算法 ? 逐點比較法 繪圖儀常用的一種方法。在每次畫圖過程中 ,繪圖筆每畫一筆，就與規(guī)定的圖形進行比較， 然后決定下一步的走向，用步步逼近的方法畫出規(guī)定的圖形。 X Y O ?假設(shè)以坐標(biāo)原點作為直線起點，各象限中畫筆走向如圖所示。 ? 逐點比較法 一般公式 : 要畫的線段為 OA， 畫筆的當(dāng)前的位置為 M。 以 OM， OA的斜率的大小來計算偏差。d=tg?tg?=ym/xmya/xa=(ym*xaya*xm)/xm*xa； （ 1）偏差計算（以第一象限為例） 當(dāng) d0時，表示筆在 OA線段的下方，根據(jù)約定此時應(yīng)走 +y一步；當(dāng)d=0時，表示筆在 OA線段的上方，應(yīng)該走 +x一步。 只判斷 d的正負 , 不管大小 ,第一象限 xm,xa均為正。 第一象限偏差的判斷公式 : Fm=ym*xaya*xm X Y O A(xA,yA) M(xM,yM) α β ? 逐點比較法 遞推公式 :上述公式要計算兩次乘法 , 設(shè)法用前一點的偏差來推算走步的方向以及走步后的偏差 . （ 1）偏差計算 筆的當(dāng)前位置為 Mi(xi,yi),此時 Fi=yixayaxi. ?如果 Fi0,應(yīng)走 +y一步到 Mi+1,即 :xi+1=xi,yi+1=yi+1。 Mi+1處的偏差 Fi+1=yi+1xayaxi+1=yixa+xayaxi=Fi+xa。 ?如果 Fi=0,應(yīng)走 +x一步到 Mi+1,即 :xi+1=xi+1,yi+1=yi。 Mi+1處的偏差 Fi+1=yi+1xayaxi+1=yixayaxi ya= Fi ya。 如果 Fi=0 則走 +x一步 ,此時 Fi+1=Fiya。 如果 Fi0 則走 +y一步 ,此時 Fi+1=Fi+xa。 ? 逐點比較法 設(shè)步距為 ?t, 直線在 x,y方向的增量分別為 ?x 和 ? ,繪圖筆從直線的起點畫到終點 ,在 x方向應(yīng)走 | ?x/ ?t|步 ,在 y方向應(yīng)走 | ?y/ ?t|步 .取 n= | ?x/ ?t|+ | ?y/ ?t|作為終點判斷的控制數(shù) ,并將此數(shù)存入計數(shù)器內(nèi) . 在 x或 y方向上每走一步計數(shù)器減 1,當(dāng)計數(shù)器減到零時 ,作圖停止 . （ 2）終點判斷 直線生成算法 ? Bresenham直線生成算法 基本原理：沿某一計長方向上，每次變化一個單位步長，另一方向上的變化量通過計算獲得。這種方法在計算判別式時，計算量很小，生成的直線光滑，因而應(yīng)用廣泛。 假設(shè)直線的斜率在 0~1之間， k=△ y/ △ x， x的變化率比 y的變化率大，約定每次 x方向變化一個像素單位，相應(yīng) y方向的變化量為 0或 1個像素單位。 Bresenham直線生成算法 ? 已知直線起點 (x1,y1)， 終點(x2,y2)； ? 直線上第 i個像素為 P(xi,yi)，它是已經(jīng)選定的離直線最近的當(dāng)前像素?，F(xiàn)在要決定下一個像素是 S(xi+1,yi),還是T(xi+1,yi+1)? ? 若 st, 則 S靠近直線 , 應(yīng)該選擇 S。 若 s=t,則選擇 T。 P(xi,yi) S(xi+1,yi) T(xi+1,yi+1) s t Q(x,y) ? 計算判別式 : 理論直線上點 Q坐標(biāo)為 y= k(xi+1)+b。求 s和 t: s=yyi=k(xi+1)+byi。 t=(yi+1)y=(yi+1)k(xi+1)b s t P(xi,yi) S(xi+1,yi) T(xi+1,yi+1) ? 計算判別式 : 理論直線上點 Q坐標(biāo)為 y= k(xi+1)+b。求 s和 t: s=yyi=k(xi+1)+byi。 t=(yi+1)y=(yi+1)k(xi+1)b st=2k(xi+1)2yi+2b1 由于 k=△ y／ △ x, △ x=x2x1,△ y=y2y1,代入上式 ， 得到 △ x (st)=2△ yxi2△ xyi+(2△ y△ x+2b△ x) (31) 記 di=△ x(st),△ x＞ 0,di與 (st)同號 。di值符號為選擇下一個像素的判別因子。為得到 di的遞推形式 ,以 i+1代入式 (31)的 i， 得 di+1=2△ yxi+12△ xyi+1+(2△ y△ x+2b△ x) (32) ? 計算判別式 : 將 (32)減去 (31),且 xi+1=xi+1， 得
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1