廣工數(shù)媒計(jì)算機(jī)圖形學(xué)之5基本圖形生成算法-多邊形掃描轉(zhuǎn)換及區(qū)域填充

計(jì)算機(jī)圖形學(xué)基礎(chǔ)：基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充計(jì)算機(jī)圖形學(xué)一個(gè)重要問(wèn)題是在一個(gè)區(qū)域的內(nèi)部填上不同的圖案、灰度或色彩。計(jì)算機(jī)圖形學(xué)領(lǐng)域所說(shuō)的區(qū)域分為兩類(lèi)：一類(lèi)是以頂點(diǎn)和邊界界定的多邊形；一類(lèi)是以像素點(diǎn)陣（即多邊形內(nèi)部的像素的集合）表示的區(qū)域。通常用確定穿越多邊形區(qū)域的掃描線的覆蓋區(qū)域的方法來(lái)填充多邊形。用從給定的位置開(kāi)始涂描直到指定的邊界條件為止的方法來(lái)填充以像素點(diǎn)陣表示的區(qū)域。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充區(qū)域的表示法以多邊形定義的區(qū)域用多邊形的頂點(diǎn)序列來(lái)定義邊界。這種方法直觀,幾何意義強(qiáng),占用內(nèi)存小。但是由于沒(méi)有明確位于多邊形內(nèi)部的像素集合,所以不能直接用于面著色。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充區(qū)域的表示法點(diǎn)陣表示用位于多邊形內(nèi)部的像素的集合來(lái)刻畫(huà)多邊形。這種表示法失去了多邊形重要的幾何信息（如頂點(diǎn)、幾何邊界等）,但便于用幀緩存表示圖形,是面著色所需要的圖形表示形式。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系大多數(shù)的圖形系統(tǒng)采用頂點(diǎn)序列表示多邊形。為解決這種表示法“沒(méi)有明確位于多邊形內(nèi)部的像素集合,所以不能直接用于面著色”的問(wèn)題,需要有從多邊形頂點(diǎn)表示到點(diǎn)陣表示的轉(zhuǎn)換。這種轉(zhuǎn)換稱(chēng)為多邊形掃描轉(zhuǎn)換。多邊形掃描轉(zhuǎn)換即多邊形的填充,需要從多邊形的頂點(diǎn)信息出發(fā),求出位于多邊形內(nèi)部的各個(gè)像素點(diǎn),并將其顏色寫(xiě)入幀緩存的相應(yīng)單元中。二維多邊形的掃描轉(zhuǎn)換是三維立體面著色的基礎(chǔ)。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系多邊形掃描轉(zhuǎn)換——x-掃描線算法x-掃描線算法填充多邊形基本思路:掃描線與x軸平行。按照掃描順序，計(jì)算每一條掃描線與多邊形的相交區(qū)間，用指定顏色顯示區(qū)間內(nèi)的像素。區(qū)間的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。x-掃描線算法可以填充凸、凹多邊形，也可填充中間有空的多邊形。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充多邊形掃描轉(zhuǎn)換——x-掃描線算法算法的實(shí)現(xiàn)步驟:一、確定多邊形所有頂點(diǎn)的ymax和ymin，得到掃描的范圍和最大掃描線數(shù)；二、求交:掃描線與多邊形各邊求交點(diǎn)，并確定交點(diǎn)的有效性；三、排序:將所有有效交點(diǎn)按x坐標(biāo)的大小排序；廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充多邊形掃描轉(zhuǎn)換——x-掃描線算法算法的實(shí)現(xiàn)步驟:四、交點(diǎn)配對(duì):奇數(shù)序號(hào)和偶數(shù)序號(hào)的交點(diǎn)配對(duì)；五、區(qū)間填色:將位于一對(duì)交點(diǎn)之間的像素置換成指定顏色。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充多邊形掃描轉(zhuǎn)換——x-掃描線算法x-掃描線算法涉及的問(wèn)題:一、掃描線與多邊形邊界交點(diǎn)的有效性判別；掃描線y=5與AB邊有無(wú)效交點(diǎn)k，在做求交運(yùn)算之前，判斷該掃描線的y坐標(biāo)不在點(diǎn)A和點(diǎn)B的y坐標(biāo)之間，不做求交運(yùn)算。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充多邊形掃描轉(zhuǎn)換——x-掃描線算法x-掃描線算法涉及的問(wèn)題：二、掃描線與多邊形頂點(diǎn)相交時(shí)交點(diǎn)的取舍問(wèn)題；情況1、共享頂點(diǎn)的兩條邊分別落在掃描線兩側(cè)時(shí)，交點(diǎn)記為1個(gè)。情況2.共享頂點(diǎn)的兩條邊位于掃描線同側(cè)，交點(diǎn)記為0個(gè)或2個(gè)?！癤-掃描線算法填充.SWF”演示x-掃描線算法實(shí)現(xiàn)的過(guò)程。廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系填充算法——邊緣填充算法邊緣填充算法的基本思想是逐邊向右求補(bǔ)。可以按任意順序處理多邊形的每一條邊。在處理每一條邊時(shí),首先求出該邊與掃描線的交點(diǎn),然后將每一條掃描線上交點(diǎn)右方的所有像素點(diǎn)取補(bǔ)（若這些點(diǎn)為背景色,則置換為填充色；若這些點(diǎn)為填充色,則置換為背景色）。多邊形的所有邊處理完畢后,填充完成。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系填充算法——邊緣填充算法“邊緣填充算法的過(guò)程.SWF”演示了邊緣填充算法的實(shí)現(xiàn)過(guò)程。該算法的優(yōu)點(diǎn)是簡(jiǎn)單,缺點(diǎn)是對(duì)于復(fù)雜圖形,每一像素可能要訪問(wèn)多次,效率降低。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系填充算法——邊標(biāo)志填充算法邊標(biāo)志算法是邊緣填充算法的優(yōu)化實(shí)現(xiàn)。邊標(biāo)志算法的實(shí)現(xiàn)步驟:一、邊標(biāo)記。首先對(duì)多邊形的每一條邊進(jìn)行直線的掃描轉(zhuǎn)換，然后給掃描轉(zhuǎn)換后得到的像素添加邊標(biāo)記。二、點(diǎn)標(biāo)記。對(duì)每一個(gè)像素使用一個(gè)布爾值inside指示當(dāng)前狀態(tài)，inside初值為false。每條掃描線依從左到右的順序掃描遇到被標(biāo)記過(guò)的點(diǎn)后，inside值取反，直至遇到下一個(gè)被標(biāo)記點(diǎn)為止。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系填充算法——邊標(biāo)志填充算法邊標(biāo)志算法的實(shí)現(xiàn)步驟:三、填充。至下而上完成掃描后，將所有inside值為true的像素點(diǎn)集的顏色置換為填充色，完成多邊形填充?！斑厴?biāo)志.SWF”演示了邊標(biāo)志算法實(shí)現(xiàn)的過(guò)程。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系區(qū)域填充區(qū)域填充針對(duì)以像素點(diǎn)陣（即多邊形內(nèi)部的像素的集合）表示的區(qū)域的填充。區(qū)域填充的思路為:從區(qū)域內(nèi)的一個(gè)點(diǎn)（種子點(diǎn)）開(kāi)始，由內(nèi)向外將填充色擴(kuò)展到整個(gè)區(qū)域。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充4-鄰接點(diǎn)廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系8-鄰接點(diǎn)區(qū)域填充與區(qū)域填充相關(guān)的概念:邊界表示——把位于邊界的像素一一列舉出來(lái)，即區(qū)域邊界上的像素用同一種顏色著色。4-連通區(qū)域和8-連通區(qū)域——確定了區(qū)域內(nèi)點(diǎn)的鄰接方式。以4-鄰接點(diǎn)定義的區(qū)域稱(chēng)為4-連通區(qū)域；以8-鄰接點(diǎn)定義的區(qū)域稱(chēng)為8-連通區(qū)域。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系區(qū)域填充與區(qū)域填充相關(guān)的概念:?！獥Ｊ且环N數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端(稱(chēng)為棧頂(top))對(duì)數(shù)據(jù)項(xiàng)進(jìn)行插入和刪除的操作。對(duì)棧內(nèi)數(shù)據(jù)的操作遵循后進(jìn)先出(Last-In/First-Out)的原則。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系區(qū)域填充——邊界填充算法算法步驟:用戶(hù)確定邊界顏色；確定填充色和填充模式（4-連通或8-連通邊界填充算法）；指定內(nèi)部點(diǎn)（種子點(diǎn)），按規(guī)則搜索當(dāng)前點(diǎn)的4-鄰接點(diǎn)或8-鄰接點(diǎn)，若這些點(diǎn)非邊界色，也非指定填充色，則置換該點(diǎn)的顏色為填充色，直至完成多邊形內(nèi)部填充。邊界填充算法不要求區(qū)域內(nèi)、外顏色不同，即原多邊形內(nèi)部可以為背景色。計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣東工業(yè)大學(xué)機(jī)電學(xué)院圖學(xué)與數(shù)字媒體工程系區(qū)域填充——邊界填充算法棧結(jié)構(gòu)實(shí)現(xiàn)4-連通邊界填充算法步驟:種子像素入棧；棧頂象素出棧；將出棧象素置成填充色；檢查出棧象素的4-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。檢查棧是否為空，若非空，則執(zhí)行步驟（2），若為空，則結(jié)束。4-連通邊界填充.SWF計(jì)算機(jī)圖形學(xué)基礎(chǔ):基本圖形生成算法——多邊形掃描轉(zhuǎn)換及區(qū)域填充廣