




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、第七章,光柵圖形的掃描轉(zhuǎn)換與區(qū)域填色,多邊形的兩種表示方法,多邊形的表示方法,頂點表示用多邊形的頂點來表示,點陣表示用多邊形內(nèi)的象素來表示,兩種表示方法的優(yōu)缺點,頂點表示:,直觀,幾何意義強,占內(nèi)存少,用得 普遍,但不能直接用于面著色。,點陣表示:,便于用幀緩沖器表示圖形,便于面著色。,什么是多邊形的掃描轉(zhuǎn)換,頂點表示,點陣表示,多邊形的掃描轉(zhuǎn)換,逐點判斷算法,算法思想:逐個像素判別,檢測其是否在多邊形內(nèi)部,從而給出位于多邊形內(nèi)部的像素集合。,逐點判斷算法的具體實現(xiàn),假設(shè)P=P0P1P2PnP0為一個給定多邊形,P0,P1,P2Pn為其頂點表示。 假設(shè)inside(P,x,y)是驗證點(x,y
2、)是否在多邊形P內(nèi)的布爾函數(shù)。,Inside函數(shù)的實現(xiàn)原理,計算從(x,y)到(+,y)的射線與多邊形的交點個數(shù)。 若交點個數(shù)是奇數(shù)的話,就表明該點在多邊形內(nèi)部,否則該點在多邊形外部。,逐點判斷算法的具體實現(xiàn),假設(shè)framebuffer(x,y)是與(x,y)對應的幀緩沖器中的元素,用以存放對應像素的顏色值。設(shè)polygon_color為多邊形內(nèi)的顏色值,background_color為背景顏色。,逐點判斷算法的偽代碼程序,for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P
3、,x+0.5,y+0.5) then setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_color),逐點判斷算法的優(yōu)缺點,優(yōu)點:簡單,易于理解。 缺點:忽略了像素與像素之間的聯(lián)系,如果整個平面有幾千萬個像素,也要一一進行判別,要做大量的計算工作,效率太低。,掃描線算法,掃描線算法利用了相鄰像素之間的連貫性,避免了反復求交的運算。 掃描線算法綜合利用了區(qū)域的連貫性,掃描線的連貫性和邊的連貫性。,區(qū)域的連貫性,假設(shè)多邊形P的頂點Pi(xi,yi),i=0,1,2n 各個頂點Pi的縱坐標
4、按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)。 如果知道了某點q所在區(qū)域在多邊形內(nèi)(或外),就能知道整個長方形區(qū)域內(nèi)的梯形排列情況。 此性質(zhì)稱為區(qū)域的連貫性。,掃描線的連貫性,假設(shè)e為一整數(shù)滿足 若掃描線y=e與多邊形P的邊Pi-1Pi相交,則記其交點的橫坐標xei。 現(xiàn)在假
5、設(shè)xei1,xei2,xeil為掃描線與P的邊界各交點的橫坐標的遞增序列,稱為交點序列。,交點序列的性質(zhì),l是偶數(shù)。 在該掃描線上只有區(qū)段(xeik,xei,k+1),(k=1,3,5l-1)位于多邊形P內(nèi),其余均在多邊形P外,兩種區(qū)段沿掃描線相間排列。 此性質(zhì)稱為掃描線的連貫性。,交點序列,若d=e-1,則位于掃描線y=d上的交點序列為xdj1,xdj2,xdjk。 若多邊形P的邊Pr-1Pr與掃描線y=e和y=d都相交,則xer和xdr滿足:,怎樣得到y(tǒng)=e上的交點序列,通過遞推式可以算出與y=e和y=d都相交的點 若再求出與掃描線y=d不相交但與下一掃描線y=e相交的所有邊PqPq+1上
6、的交點xeq 然后把這些點按底層的順序排列,就能得到了y=e上的交點序列,邊的連貫性,當取某一整數(shù)k,0=k=n-1,使 1)兩序列元素數(shù)個數(shù)相等 2)點(xeir,e)與(xdjr,d)位于多邊形同一條邊上,即ir=jr,得到 由上式就可遞推出xeir。,奇點的處理,當掃描線與多邊形P的邊界的交點是P的頂點時,該交點稱為奇點。 由于連貫性,每一條掃描線與多邊形P的邊界交點個數(shù)都是偶數(shù)。但是過奇點的掃描線可能出現(xiàn)奇數(shù)。,出現(xiàn)奇點的兩種情況,出現(xiàn)奇點的兩種情況的討論,極值點就是附近的點都比其小或都比其大,滿足數(shù)學表達式為(yi-1-yi)(yi+1-yi)0 不是極值點的頂點稱為非極值點。,P所
7、有的頂點,極值點,非極值點,對于奇點的兩種情況的處理,交點個數(shù)加一,交點個數(shù)不變,掃描線算法的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),邊的分類表ET,邊的活化鏈表AEL,Ymax:邊的上端點的y坐標,x:在ET中表示邊的下端點 的x坐標,在AEL中則表示 邊與掃描線交點的x坐標,x:邊的斜率的倒數(shù),next:指向下一條邊的指針,邊的分類表ET,邊的分類表ET是按邊下端點的縱坐標y對非水平邊進行分類的鏈表數(shù)組。,2,10,2,16,1,2,3,4,5,6,e7,e5,e7,e5,e4,e4,e1,e1,e2,e2,e3,e3,邊的活化表AEL,邊的活化表AEL由與當前掃描線相交的所有多邊形的邊組成,它記錄了多邊形邊
8、沿掃描線的交點序列,并根據(jù)遞推式:,AEL,e1,e2,e3,e4,AEL在y=8的掃描線上的狀態(tài),不斷刷新交點序列。,掃描線算法的描述,步驟1:(y初始化)建立ET表,并且取掃描線縱坐標y的初始值為ET中非空元素的最小序列。 步驟2:(AEL初始化)將邊的活化鏈表AEL設(shè)置為空。 步驟3:按從下到上的順序?qū)v坐標值為y的掃描線(當前掃描線)執(zhí)行子算法,直到ET和AEL都變?yōu)榭諡橹埂?子算法步驟,1)如果邊分類表ET中第y類元素為非空,則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表AEL中,AEL中各邊按x的值(當x的值相等時,按x值)遞增方式排序。,子算法步驟,2)若相對于當前掃描線,邊
9、的活化鏈表AEL非空,則將AEL中邊兩兩依次配對 (位置位于1,2的配對;位置位于3,4的配對),依次配對的邊的內(nèi)部點(像素)按多邊形的顏色屬性進行著色。,子算法步驟,3)將邊的活化鏈表AEL中ymaxy的邊刪去 4)將邊的活化鏈表AEL剩下的每一條邊的x域累加x,即x:=x+x 5)將當前掃描線的縱坐標值y累加1,即y:=y+1,掃描線算法的優(yōu)缺點,優(yōu)點:效率高。 缺點:程序復雜,需要排序。,邊緣填充算法,由于掃描線算法需要對多邊形的邊進行排序,如果采用求余的方法,就不用對邊進行排序了。,什么是求余?,數(shù)學上:A為一個給定的正數(shù),數(shù)M的余是指A-M的差。記為 ,易得 光柵圖形上:若某區(qū)域已著
10、上值為M的某種顏色,對M作偶數(shù)次求余運算后,此區(qū)域顏色不變,作奇數(shù)次求余運算后,區(qū)域顏色變?yōu)?。,求余運算的函數(shù)表示,Complement(framebuffer,x,y)為實施求余運算的函數(shù),其作用為 framebuffer(x,y):=A-framebuffer(x,y),邊緣填充算法的描述,假設(shè)x1,x2,xm為掃描線與多邊形P的交點的數(shù)列(不要求是遞增序列)。 步驟1:在y=e上所有像素都上值為 的顏色: for x:=screen_xmin to screen_xmax do setpixel(framebuffer,x,e,M),邊緣填充算法的描述,步驟2:對位于掃描線y=e上的所
11、有x坐標大于xi(I=1,2,m)的像素求余。稱為向右求余: for i:=1 to m do for x:=xi to screen_xmax do Complement(framebuffer,x,y) 這樣,多邊形內(nèi)被著色M,多邊形外被著色 。,邊緣填充算法的圖示,邊緣填充算法的邊界求余,邊緣填充算法的優(yōu)缺點,優(yōu)點:數(shù)據(jù)結(jié)構(gòu)和程序都比較簡單。 缺點:需對幀緩沖器中大批元素反復賦值,速度并不比掃描線算法快。,邊界標志算法,邊界標志算法采用先畫邊界后填色的方法,對幀緩沖器中每個元素賦值不超過2次。,邊界標志算法的算法思想,算法思想:先把多邊形邊界用另一種顏色標識出來,由于邊界已經(jīng)標識出來了,
12、邊界之間的各個區(qū)段要么填上多邊形內(nèi)部的顏色,要么填上背景色。,步驟1:以值為boundary_color的特殊顏色勾畫多邊形P的邊界。見書上的程序。 步驟2:逐條掃描線對多邊形著色。因為已經(jīng)標志為特殊顏色的邊界是兩兩配對的。一對邊界點中間可能是多邊形區(qū)域內(nèi)的點,也可能是多邊形區(qū)域外的點。,邊界標志算法的描述,如何判斷邊對中間的點是否在多邊形內(nèi)部,采用一個布爾變量interior_point,如果當前像素位于多邊形內(nèi),則為true,應著polygon_color,否則為false,應著background_color。,interior_point如何變化,此布爾變量起始在多邊形外,初始值為fa
13、lse,每碰到一個邊界像素,就取反。,邊界標志算法的優(yōu)缺點,優(yōu)點:避免了對幀緩沖器中大量元素的多次賦值,速度與掃描線算法相當。 缺點:需逐條掃描線對幀緩沖器中的元素進行搜索和比較。,區(qū)域填充,區(qū)域填充是指先將區(qū)域內(nèi)一點賦予給定顏色,然后將這種顏色擴展到整個區(qū)域的過程。 最先的那點也叫做種子點。,區(qū)域的表示法,內(nèi)點表示法:把所給區(qū)域內(nèi)所有象素一一列舉出來。 邊界表示法:把所給區(qū)域邊界上的象素一一列舉出來。,區(qū)域的連通性,在區(qū)域填充算法中要求區(qū)域具有一定的連通性。,4連通性,4連通:區(qū)域任意兩點,從一點出發(fā)通過上、下、左、右方向,只經(jīng)過區(qū)域內(nèi)的點可到達另一點。,8連通性,8連通:區(qū)域任意兩點,從一
14、點出發(fā)通過水平、垂直和對角線方向,只經(jīng)過區(qū)域內(nèi)的點可到達另一點。,具體表現(xiàn)形式,內(nèi)點表示的4連通區(qū)域 邊界表示的4連通區(qū)域 內(nèi)點表示的8連通區(qū)域 邊界表示的8連通區(qū)域,兩種連通性的邊界不同,同一個區(qū)域可以看成是4連通區(qū)域,也可以看成是8連通區(qū)域,但是兩者的邊界是不同的。 4連通區(qū)域的邊界是8連通區(qū)域; 8連通區(qū)域的邊界是4連通區(qū)域。,遞歸算法,算法思想:先選取一個種子象素(x,y),然后設(shè)此象素(x,y)為new_color,然后逐步按照連通性進行遞歸調(diào)用將整個區(qū)域G都設(shè)置為new_color。,遞歸算法的算法步驟,先測試象素(x,y)的顏色是否等于old_color,若不是則說明該象素在區(qū)域
15、G外,不能取為種子,停止填充; 否則置該象素顏色為new_color,再對上、下、左、右四個象素遞歸調(diào)用本身函數(shù)。,算法程序(內(nèi)點表示的4連通),Procedure flood-fill-4(x,y,old_color,new_color:integer) Begin if getpixel(framebuffer,x,y)=old_color then begin setpixel(framebuffer,x,y,new_color) flood-fill-4(x,y+1,old_color,new_color) flood-fill-4(x,y-1,old_color,new_color)
16、 flood-fill-4(x-1,y,old_color,new_color) flood-fill-4(x+1,y,old_color,new_color) end end,遞歸算法的特點,遞歸這種方法必須包含兩個部分:自身調(diào)用和停止條件。,其他形式的區(qū)域表示如何變動,若是邊界表示的4連通區(qū)域的程序只要改動判斷條件就行了。 if getpixel(framebuffer,x,y)boundary_color and getpixel(framebuffer,x,y)new_color,遞歸算法的優(yōu)缺點和作業(yè),優(yōu)點:程序簡單明了。 缺點:數(shù)據(jù)和函數(shù)反復進出系統(tǒng)堆棧,費時費內(nèi)存。 作業(yè):內(nèi)點表
17、示的8連通區(qū)域、邊界表示的8連通區(qū)域的遞歸算法的程序。,掃描線算法,區(qū)域填充的掃描線算法適用于邊界表示的4連通區(qū)域。,掃描線算法的算法思想,首先填充種子點所在的當前掃描線上位于給定區(qū)域內(nèi)的一區(qū)段。 然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段,并依次把這些區(qū)段的右端點入棧。 然后不斷取出棧頂?shù)姆N子重復繼續(xù)上一過程,直到棧空。,算法的實現(xiàn)(1),1)初始化:將種子點壓入初始化后的棧。 2)出棧:如果棧為空,算法結(jié)束;否則取棧頂元素為當前種子點。 3)區(qū)段填充:從當前種子點開始沿水平掃描線向左右兩個方向逐個像素進行填色,直至抵達邊界為止。 4)定范圍:以XLEFT和XRIGHT分別表示
18、第三步中填充的區(qū)段兩個端點的橫坐標。,算法的實現(xiàn)(2),5)進棧:分別在于當前掃描線相鄰的上下兩條掃描線上,確定位于區(qū)間【XLEFT,XRIGHT】內(nèi)的給定區(qū)域的區(qū)段。如果這些區(qū)段內(nèi)的像素顏色值為內(nèi)部點或邊界點的顏色的話,則轉(zhuǎn)到第二步,否則從XLEFT開始向右逐點判斷,直到碰到邊界點停下,此時把邊界點左端的點(區(qū)段右端點)入棧。向右繼續(xù)逐點判斷是否還存在空白區(qū)段,如果有,把這些區(qū)段的右端點依次入棧。,實例,算法的優(yōu)點和缺點,優(yōu)點:只需把掃描線右端種子入棧,而無須把全部象素入棧,進出棧次數(shù)大為減少,內(nèi)存節(jié)省很多,速度提高很快。 缺點:對于已經(jīng)填充的直線可能會多次地重復檢查是否已經(jīng)填充。,多邊形掃
19、描轉(zhuǎn)換與區(qū)域填充的互相轉(zhuǎn)化,若把多邊形內(nèi)一點作為種子點,并用以前學過的直線生成算法將多邊形的邊界表示為8連通區(qū)域的話,多邊形的掃描轉(zhuǎn)換問題可以轉(zhuǎn)換為區(qū)域填充問題。 反過來,若已知多邊形的頂點表示,則區(qū)域填充問題可以轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換問題。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同(1),基本思想不同: 多邊形的掃描轉(zhuǎn)換:將多邊形的頂點表示轉(zhuǎn)換為點陣表示,利用多邊形各種形式的連貫性。 區(qū)域填充:只改變區(qū)域內(nèi)的顏色,不改變區(qū)域表示方法,利用區(qū)域的連通性。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同(2),對邊界的要求不同: 多邊形的掃描轉(zhuǎn)換:要求每一條掃描線與多邊形邊界的交點個數(shù)是偶數(shù)。 區(qū)域填充:要求4連通區(qū)域邊界為封閉8連通區(qū)域,要求8連通區(qū)域邊界為封閉4連通區(qū)域。,多邊形的掃描轉(zhuǎn)換和區(qū)域填充的不同(3),出發(fā)點(初始點)不同: 多邊形的掃描轉(zhuǎn)換:要求多邊形頂點要依次給出。 區(qū)域填充:要求指定區(qū)域內(nèi)一點為種子點,但對任意多邊形來說,要確定某點為多邊形內(nèi)部一點要做大量的計算。,光柵圖形的走樣現(xiàn)象,邊界階梯形:采用離散量表示連續(xù)量而引起的,細節(jié)失真,狹小圖形遺失,運動圖形的閃光現(xiàn)象:出現(xiàn)在緩慢移動的物體中,線段反走樣算法的要點,線段有一定的寬度,應把線段看作狹長的矩形。 線段有一定的面積,當
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 股東出資與員工持股計劃協(xié)議書
- 購物卡充值與消費返利合作協(xié)議
- 婦幼保健知識與護理建議
- 肝病的飲食禁忌和康復護理
- 2024-2025學年天津市南開區(qū)七年級(下)期末數(shù)學試卷
- 中原鉆井培訓實驗基地
- 2025-2030中國不銹鋼棒材行業(yè)運營風險及發(fā)展現(xiàn)狀趨勢洞察報告
- 采購比武方案
- 割箱機報價方案
- 項目部職能規(guī)劃方案
- 2023-2024學年滬科版(2019)高中信息技術(shù)必修二第三單元項目五《規(guī)劃并連接數(shù)字家庭系統(tǒng)的網(wǎng)絡-組建小型信息系統(tǒng)網(wǎng)絡(一)》說課稿
- 石油行業(yè)設(shè)備管理規(guī)范
- 汕頭市防汛防旱防風防凍應急預案
- 2023年高考遼寧卷化學真題(解析版)
- (修訂版)糧油質(zhì)量檢驗員理論考試復習題庫-上(單選題)
- 2023-2024學年廣東省深圳市福田區(qū)七年級(下)期末數(shù)學答案
- 2024版商戶入駐合同
- 和公司直播合作協(xié)議書范本
- 兒科護理學高職全套教學課件
- 光伏發(fā)電工程建設(shè)標準工藝手冊(2023版)
- 北師大版八年級數(shù)學下冊常考題專練專題18平行四邊形中的周長和面積問題(原卷版+解析)
評論
0/150
提交評論