嵌入式圖形加速器中邊標(biāo)志算法的改進(jìn)與硬件實(shí)現(xiàn).pdf

1、多邊形填充算法是計(jì)算機(jī)圖形學(xué)中的基本算法之一，也是圖形加速器中光柵化階段的主要算法之一。近些年來，隨著嵌入式系統(tǒng)的廣泛應(yīng)用以及計(jì)算機(jī)圖形學(xué)的發(fā)展，面對著嵌入式系統(tǒng)中高質(zhì)量、動態(tài)實(shí)時顯示以及高分辨率的要求，傳統(tǒng)的使用軟件編程語言實(shí)現(xiàn)相關(guān)算法，然后主要依賴微處理器來對顯示數(shù)據(jù)進(jìn)行處理的顯示方式顯然已經(jīng)難以滿足此時的要求。因此在嵌入式系統(tǒng)中使用硬件來實(shí)現(xiàn)圖形顯示中經(jīng)常用到而且占用微處理器等資源比較多的算法，從而減輕微處理器的負(fù)擔(dān)，達(dá)到圖形加速

2、顯示的目的，進(jìn)而滿足高要求顯示的需求，不失為一種可行的顯示處理方案。
　　邊標(biāo)志算法是多邊形填充算法中經(jīng)常使用的填充算法之一。傳統(tǒng)的多邊形邊標(biāo)志算法在處理帶有極值點(diǎn)、狹長條以及具有水平邊界（含有奇數(shù)個像素點(diǎn)）的多邊形時便會出現(xiàn)異常填充的現(xiàn)象。因此本文在深入研究傳統(tǒng)的邊標(biāo)志算法及大量的改進(jìn)后的邊標(biāo)志算法的基礎(chǔ)之上，提出了一種新的改進(jìn)的邊標(biāo)志算法。該算法充分利用了邊標(biāo)志算法在光柵化多邊形的邊界時需要對每一條邊界的每一個像素點(diǎn)都要訪問一

3、次的特點(diǎn)，為多邊形內(nèi)部以及多邊形邊界上的像素點(diǎn)設(shè)置一個計(jì)數(shù)型邊標(biāo)記變量flag，在對多邊形的邊界進(jìn)行光柵化的過程中，針對邊界上的像素點(diǎn)每訪問一次對其flag值便進(jìn)行加1。這樣就很方便簡捷的將極值點(diǎn)和狹長條上的點(diǎn)與普通的邊界點(diǎn)區(qū)別開來。在對多邊形進(jìn)行填充的過程中，根據(jù)當(dāng)前像素點(diǎn)的flag值與1的大小關(guān)系情況判斷掃描線以后的像素點(diǎn)是否位于多邊形的內(nèi)部，以便對像素點(diǎn)進(jìn)行填充。
　　改進(jìn)后的算法不僅保持了傳統(tǒng)的邊標(biāo)記算法的數(shù)據(jù)結(jié)構(gòu)簡單、思

4、想簡單和適合硬件實(shí)現(xiàn)的優(yōu)點(diǎn)，而且在處理極值點(diǎn)、狹長條問題以及水平邊界的過程中又僅僅使用對邊界像素點(diǎn)的標(biāo)記值進(jìn)行加1的操作，一次性的完成了極值點(diǎn)、狹長條上的點(diǎn)與普通點(diǎn)的區(qū)別，從而消除了填充異常的現(xiàn)象，方便了算法的實(shí)現(xiàn)。對本文提出的改進(jìn)的邊標(biāo)志算法首先是在PC機(jī)上使用VC++6.0對其填充結(jié)果的正確性進(jìn)行了驗(yàn)證，然后是在友晶科技公司的DE2-70系列教育開發(fā)板上使用Verilog HDL進(jìn)行了實(shí)現(xiàn)，最后使用友晶科技公司的TRDB-LTM顯示