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

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

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

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

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