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