包括英文原文和中文翻譯，其中中文翻譯11000字；英文 含詳細作者及出處信息

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

Dominik Henrich
實時計算機系統(tǒng)和機器人技術(shù)學(xué)會
德國卡爾斯魯厄大學(xué)，凱撒街12號，卡爾斯魯厄D-76128



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

1 簡介
　　　計算機圖形區(qū)域填充的問題主要發(fā)生在交互式系統(tǒng)。例如，繪圖應(yīng)用軟件的用戶用鼠標(biāo)點擊圖畫的區(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ū)域的工作原理是類似的。
　　　由于是運用像素來定義區(qū)域，大部分的填充算法都有一個種子點作為輸入。種子點是區(qū)域內(nèi)部的一個像素。所謂的種子填充算法就是從種子點出發(fā)并通過某個算法擴展到相鄰近的像素。只有區(qū)域內(nèi)部的像素才能夠變成填充色。由于這些像素從種子出發(fā)能達到而又不穿過邊界，因此，它們是 “連通”到種子的。
　　　考慮到內(nèi)存的使用，填充算法可以細分為兩個小組。在一個小組，附加的“工作面”除幀緩存器之外，都被用來填充。填充后，它被復(fù)制到幀緩存器。在中間可能會用到繪圖模板（Ackland 和Weste 1981年, Dunlavey1983年, Tang和 Lien 1988年)。另一組使用了一個數(shù)據(jù)結(jié)構(gòu)，大多數(shù)情況下，它是一個填充區(qū)域被劃分時存放一些內(nèi)在像素的堆棧。在之后的步驟中，這些像素中每一個都被用作新的種子點來填充一個分隔的區(qū)域（Newman和Sproull 1973年, Liebermann1978年,Smith 1979年,Shani 1980年,Pavlidis 1982年）。通常情況，這兩組的方法都需要除幀緩存器外的工作內(nèi)存。內(nèi)存的使用數(shù)量根據(jù)區(qū)域的大小來決定（隨區(qū)域復(fù)雜度而增長），且不是恒定不變的。