《視覺計(jì)算機(jī)》：國際計(jì)算機(jī)圖形期刊
(1992年7月13日遞交; 1992年12月7日校正; 1993 4月16日發(fā)表)

高效利用空間的光柵圖形區(qū)域填充

Dominik Henrich
實(shí)時(shí)計(jì)算機(jī)系統(tǒng)和機(jī)器人技術(shù)學(xué)會(huì)
德國卡爾斯魯厄大學(xué)，凱撒街12號(hào)，卡爾斯魯厄D-76128
郵箱: dhenrich@ira.uka.de

摘要
本文提出了在光柵圖形學(xué)中被定義邊界的區(qū)域填充算法。此算法僅要求一個(gè)固定大小的工作內(nèi)存。這種方法是基于所謂的使用內(nèi)部連通區(qū)域內(nèi)點(diǎn)的“種子算法”。本文中除了附加啟發(fā)式加速算法，基本算法也被描述和驗(yàn)證。對(duì)于不同類別的區(qū)域，算法的時(shí)間復(fù)雜度將通過實(shí)驗(yàn)結(jié)果進(jìn)行比較。
關(guān)鍵字:種子填充,圖形處理器,幀緩沖操作,算法顯示,光柵圖形學(xué)

1 簡介
計(jì)算機(jī)圖形區(qū)域填充的問題主要發(fā)生在交互式系統(tǒng)。例如，繪圖應(yīng)用軟件的用戶用鼠標(biāo)點(diǎn)擊圖畫的區(qū)域時(shí)，應(yīng)用軟件立即被要求填充這個(gè)區(qū)域。由于這個(gè)領(lǐng)域?qū)λ俣鹊母咭?，越來越多的帶有特殊圖形處理的解決方案已被列入考慮范圍。由于協(xié)處理器的芯片區(qū)域是有限的，算法不用或只用協(xié)處理器提供的局部工作內(nèi)存有特殊要求。這里，我們描述并且驗(yàn)證以解決這種有限性的基本算法和附加啟發(fā)式試探索法。
填充的區(qū)域可以用不同的方式來描述。例如，多邊形的幾條邊可以分隔出這個(gè)區(qū)域的邊界部分(Little和Heuft 1979年, Brassel和Fegeas 1979年)。另一種情況是用一組連續(xù)的鄰接象素來描述區(qū)域。如果定義區(qū)域的像素是著同一顏色，稱之為內(nèi)點(diǎn)表示。否則，邊界像素著同一顏色時(shí)，這個(gè)區(qū)域采用的是邊界表示。這兩種情況的其它像素點(diǎn)的著色都是隨意的。本文我們集中介紹邊界表示區(qū)域，內(nèi)點(diǎn)表示區(qū)域的工作原理是類似的。