計(jì)算機(jī)圖形學(xué)第七章(已修改)
2025-05-28 15:31 本頁面
【正文】 第七章 光柵圖形的掃描轉(zhuǎn)換與區(qū)域填色 多邊形的兩種表示方法 兩種表示方法的優(yōu)缺點(diǎn) 什么是多邊形的掃描轉(zhuǎn)換 逐點(diǎn)判斷算法 算法思想：逐個像素判別 ， 檢測其是否在多邊形內(nèi)部 ， 從而給出位于多邊形內(nèi)部的像素集合 。 逐點(diǎn)判斷算法的具體實(shí)現(xiàn) 假設(shè) P=P0P1P2… PnP0為一個給定多邊形，P0,P1,P2… Pn為其頂點(diǎn)表示。 假設(shè) inside(P,x,y)是驗(yàn)證點(diǎn) (x,y)是否在多邊形 P內(nèi)的布爾函數(shù)。 Inside函數(shù)的實(shí)現(xiàn)原理 計(jì)算從 (x,y)到 (+∞,y)的射線與多邊形的交點(diǎn)個數(shù)。 若交點(diǎn)個數(shù)是奇數(shù)的話，就表明該點(diǎn)在多邊形內(nèi)部，否則該點(diǎn)在多邊形外部。 逐點(diǎn)判斷算法的具體實(shí)現(xiàn) 假設(shè) framebuffer(x,y)是與 (x,y)對應(yīng)的幀緩沖器中的元素，用以存放對應(yīng)像素的顏色值。設(shè) polygon_color為多邊形內(nèi)的顏色值， background_color為背景顏色。 逐點(diǎn)判斷算法的偽代碼程序 for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P,x+,y+) then setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_color) 逐點(diǎn)判斷算法的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：簡單，易于理解。 缺點(diǎn)：忽略了像素與像素之間的聯(lián)系，如果整個平面有幾千萬個像素，也要一一進(jìn)行判別，要做大量的計(jì)算工作，效率太低。 掃描線算法 掃描線算法利用了相鄰像素之間的連貫性，避免了反復(fù)求交的運(yùn)算。 掃描線算法綜合利用了區(qū)域的連貫性，掃描線的連貫性和邊的連貫性。 區(qū)域的連貫性 假設(shè)多邊形 P的頂點(diǎn) Pi(xi,yi),i=0,1,2… n 各個頂點(diǎn) Pi的縱坐標(biāo)按 yi遞減排序： yi0, yi1, yi2… yin 其中 yi,k= yi,k+1 區(qū)域的分割 現(xiàn)在作兩條掃描線 y=yi,k和 y=yi,k+1， 這兩條掃描線之間的區(qū)域被多邊形分割成若干個梯形。 梯形上下兩底分別為兩條掃描線，腰在多邊形 P的邊上或在顯示屏幕的邊界上。 分割后區(qū)域的分類 這些梯形分為兩類：在多邊形 P內(nèi)部和在多邊形 P外部。 兩類梯形交替地排列在長方形區(qū)域內(nèi)。 如果知道了某點(diǎn) q所在區(qū)域在多邊形內(nèi)(或外 )，就能知道整個長方形區(qū)域內(nèi)的梯形排列情況。 此性質(zhì)稱為區(qū)域的連貫性。 掃描線的連貫性 假設(shè) e為一整數(shù)滿足 若掃描線 y=e與多邊形 P的邊 Pi1Pi相交，則記其交點(diǎn)的橫坐標(biāo) xei。 現(xiàn)在假設(shè) xei1,xei2,… ,xeil為掃描線與 P的邊界各交點(diǎn)的橫坐標(biāo)的遞增序列，稱為交點(diǎn)序列。 0iin yey ??交點(diǎn)序列的性質(zhì) l是偶數(shù)。 在該掃描線上只有區(qū)段 (xeik,xei,k+1)，(k=1,3,5… l1)位于多邊形 P內(nèi)，其余均在多邊形 P外，兩種區(qū)段沿掃描線相間排列。 此性質(zhì)稱為掃描線的連貫性。 交點(diǎn)序列 若 d=e1， 則位于掃
高考資料相關(guān)推薦
鄂ICP備17016276號-1