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

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

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



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