計算機(jī)圖形學(xué)基本光柵圖形算法

《計算機(jī)圖形學(xué)基本光柵圖形算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、本章內(nèi)容13.1用Java語言繪圖23.2直線的掃描轉(zhuǎn)換33.3圓的掃描轉(zhuǎn)換43.4多邊形的掃描轉(zhuǎn)換53.5區(qū)域填充63.6字符的生成73.7光柵圖形的反走樣算法3.2直線的掃描轉(zhuǎn)換⊙圖形圖像是由屏幕上不同亮度不同顏色的光點（像素）組成。在光柵顯示器的熒光屏上生成一個對象，實質(zhì)上是往幀緩存寄存器的相應(yīng)單元中填入數(shù)據(jù)。所以⊙對直線進(jìn)行光柵化的時候，只能在顯示器所給定的有限個像素組成的點陣中確定最佳逼近于該直線的一組像素，用這些像素表示該直線。所以⊙生成直線的主要工作是：快速找出距離直線最近的網(wǎng)格點

2、，用這些網(wǎng)格點對應(yīng)的像素表示該直線。3像素逼近直線示意圖圖像元素可尋址點43.2.1基本3增.量2.算1法基(DD本A-增dig量it算al法differentialanalyzer)1、基本思想：設(shè)直線y?mx?b滿足0?m?1，由于直線的斜率小于等于1，所以，該直線的掃描轉(zhuǎn)換可從最左端開始，x每次遞增一個單位，對每個xi，相應(yīng)的有y?mx?b，則iiy?mx?b?m(x?1)?b?y?mi?1i?1ii所以，x每增加一個單位，y只需加上一個m，這樣就去掉了乘法運算，提高了算法效率。在該算法中

3、，直線上的所有點的x和y值可由前一點的值加一個基本增量得到，所以該算法稱為基本增量算法。53.2.1基本增量算法上述討論只適合

4、m

5、?1的情況，當(dāng)

6、m

7、?時1，注：只需將和x的角y色互換，即每次y增加一個單位，每次x增加1。/m基本增量算法也叫數(shù)字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用數(shù)值方法求解微分方程的一種設(shè)備，即根據(jù)11x1和y的一階導(dǎo)數(shù)，在x和y方向上漸進(jìn)地以小步長移動，由此產(chǎn)生連續(xù)的像素坐標(biāo)(x,y)。ii62、直線的表示：設(shè)直線的

8、起點坐標(biāo)為(xs，ys)，終點坐標(biāo)為(xe,ye)，令Δx＝xe-xs，Δy＝y(tǒng)e-ys，則直線參數(shù)方程為x?x??xts0?t?1y?y??yts第i步時?xi?xs??x?ti(3.1)?y?y??y?t?isiv目標(biāo)：能快速地求出能很好地表示直線的像素73、提高速度的方法：乘法用加法實現(xiàn)，每一個點坐標(biāo)都可以由前一個坐標(biāo)變化一個增量得到。設(shè)(xi,yi)是第i步得的直線上的點，則直線上第個i+1點是(xi+1,yi+1)，其中?x?x??x(t??t)?x??x?ti?1sii(3.2)??

9、y?y??y(t??t)?y??y?ti?1sii當(dāng)Δx>Δy>0，即直線斜率小于1，應(yīng)使x方向每次增加1，y方向最多增加1，此時取Δt=1/Δx；同理,當(dāng)Δy>Δx>0,直線斜率大于1，取Δt=1/Δy，所以令n?max{

10、?x

11、,

12、?y

13、}，將參數(shù)區(qū)間[0，1]分為n等份，即t每次的增量為?t?1/n。8下圖中，用公式（3.2）求得的直線PsPe上的點用空心圓表示，但顯示時要用像素來表示，即采用四舍五入的辦法得到最靠近空心圓點的像素，用這些像素（下圖中的實心圓點）來表示直線。PePs圖中實心

14、圓點表示用DDA方法生成的直線94、直線的DDA算法程序voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);dx=(float)(x2-x1)/k;dy=(float)(y2-y1)/k;//變化的增量x=(float)(x1);y=(float)(y1);圖中黑點表示用DDAfor(inti=0;i

15、+){法生成的直線g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f));x=x+dx;y=y+dy;}}//endDDA完成四舍五入10設(shè)給定直線的起點坐標(biāo)為(0，0)，實例終點坐標(biāo)為(9，6)，則上述DDA算法畫出的直線如下圖所示。DDA算法缺點：需要進(jìn)行浮點數(shù)運算，產(chǎn)生一個像素要做兩次加法和兩次取整運算，運行效率低且取整運算不利于硬件實現(xiàn)。DDA方法所畫直線圖113.2.2Bresenham算法設(shè)直線的起點坐標(biāo)為(xs

16、,ys)，斜率為m。下面就0?m?1的情況來說算法背景明該算法。取xi為像素所在點的橫坐標(biāo)（整數(shù)），令(x,y)?(x,y)，11ss直線上相鄰兩點的坐標(biāo)滿足關(guān)系yi?1?yi?m(3.3)一般來說，m不一定是整數(shù)，所以yi也不一定是整數(shù)，因此要用靠近該點最近的網(wǎng)格點(x,int(y?0.5))來近似。由ii于取整計算量較大，為了提高效率，Bresenham算法用下面的方法來避免使用取整運算。12算法思想：Dy?1設(shè)圖3.4中已得到第i個顯示的點i,r(x,y)，B點是直線與第i?1列Aii,r