有效的混合圓弧掃描轉換算法

張勝男， 牛連強， 陳 欣

（1. 沈陽工業大學信息科學與工程學院，遼寧 沈陽 110870；2. 沈陽工業大學理學院，遼寧 沈陽 110870）

圖形基元的生成算法對整個圖形系統的效率和質量具有重要影響。因此，從20世紀70年代起，這些基元的光柵轉換算法的研究就已開始[1]，至今仍受到關注[2-4]。目前，直線的光柵轉換算法已得到了充分的研究，并發展了2步算法、多步算法、行程算法以及多級行程算法等[2,5-7]，利用很少的幾次基本運算即可繪制多個像素。但由于圓弧等曲線的非線性性，其進行光柵轉換算法的設計遠比處理直線復雜，進展也非常緩慢。

作為經典圓弧繪制算法，Bresenham算法[8]和中點法[9]分別采用兩點的距離平方差和中點誤差作為決策參數，確定每次每步時的坐標位置，算法簡單，容易實現。文獻[10]提出了基于中點法的快速算法，該算法先將中點法的迭代關系除以系數 2，再利用奇、偶次迭代來分別處理關系式中的常數1/2，從而消除了系數2所帶來的位移運算。本文作者于文獻[11]提出了一種直接利用殘差實現的另一種有別于前述兩種算法的基本圓弧生成算法。由于這些算法的共同點是每步選擇一個像素，故被稱為基于像素（pixel-based）的算法。

為了提高圓弧的生成速度，目前的研究工作主要集中在以下兩個方面：

1）盡量減少每次步進消耗的運算次數；

2）盡量減少輸出(I/O)的次數。

很難從理論上說明，每次步進至少需要多少次運算，但由于單步選擇像素法的運算量已經難以減小，改進的目標將是多步法。由于現今的硬件設備輸出多點像素時的位模式設置時間與輸出一個像素的位模式設置時間接近，因此，減少I/O輸出次數可以有效地提高繪制效率，這是行程算法的出發點。不過，當圓的半徑確定時，行程法所減少的運算量也是確定的。

文獻[12-13]首先提出了一個每次步進可繪制兩個像素的2步驟算法，該算法利用對連續兩點中點的位置關系的預先估計進行判定，以舍棄中間點的數學運算。文獻[4]采取重新定義決策參數的方法實現了一種2點步進算法，使每點的運算量達到3.8左右。

文獻[14]提出了一個基于水平行程的圓弧的光柵轉換算法（記為HCL算法）。HCL算法的主要思想是將 45° ～90°之間的圓弧視為由水平行程組成，因為同一個行程上的像素的y坐標是相同的，故可以根據y-0.5 ～y+0.5的y坐標變化范圍確定行程長度的迭代關系，進而求出行程長度并一次性輸出這些像素。根據文獻[13]的測試，這種算法的圓弧光柵轉換效率比傳統的單點算法高 1.36倍（對 1≤radius≤128）。

經過比較，我們認為目前最快的圓弧繪制算法是由Yao and Rokne提出的一種混合算法[15-16]。該算法是在HCL算法的基礎上結合2點步進實現的。具體地說，Yao-Rokne算法對45° ～90°之間的圓弧的性質做了更細致的分析，并以“y=2x”為界將其劃分為2部分。第1部分采用類似HCL算法的迭代公式計算出水平行程的長度，再一次性輸出這些行程，但每次循環的增量為 2。由于第2部分的水平行程長度為1或2，該算法采用中點法迭代并輸出每個像素。很明顯，YR算法具有行程算法的特征，且水平行程的計算速度快，因此，整體圓弧繪制速度有了明顯提高。本文作者在文獻[17]中提出了一種利用基本迭代關系構造的簡單行程算法。

Bresenham算法和中點法一直被認為是經典的算法，其中的重要原因之一是簡單性，包括思想簡單、格式推導簡單和僅使用的簡單運算。不過，雖然改進后的HCL算法和YR算法不同程度地提高了繪制效率，但這些結果的推導和理解困難，且引入了開方、乘法等復雜的運算。

本文提出了一種利用中點法技術重新構造迭代關系而得到的2點步進與行程計算、模式分析相結合的混合算法。新算法對水平行程長度大于2的部分和水平行程長度小于2的部分單獨處理，但每次迭代幾乎都能產生2個（或3個）像素。新算法僅通過推廣中點法實現，理論推導容易，且消除了YR算法中的乘法，僅使用簡單運算實現，其效率高于現有的其它算法。

在以下的討論中，假定圓弧的圓心在坐標原點，圓弧半徑r為整數。由于圓的對稱性，僅研究 45° ～90°的圓弧繪制，其他 7個 1/8圓弧可由對稱性得到。約定在目標像素與圓弧真實值的誤差為0.5時，取下方像素。

1 相關的工作分析

1.1 WR算法

Wu和Rokne在文獻[9]中提出了一個雙步圓生成算法（記為WR算法），如圖1所示。設當前點為(x,y)，該算法判斷圓弧是在(x+2,y)與(x+2,y-1)之間的中點（記為中點 2）之上還是之下，或是在(x+2,y-1)與(x+2,y-2)之間的中點（記為中點3）之上還是之下。

1）若是在中點 2之上，則畫兩點(x+1,y)和(x+2,y)；

2）若是在中點 3之下，則畫另外兩點(x+1,y-1)和(x+2,y-2)，并轉到第2個1/16圓弧生成部分；

3）如果圓弧在兩個中點之間，則不加區分地畫 3 點(x+1,y)、(x+1,y-1)和(x+2,y-1)。

圖1 圓弧經過的位置

上述方法可以有效地減少計算量。不過，在繪制3點時，(x+1,y) 和(x+1,y-1)中的一個像素到圓弧的距離必然要大于0.5個像素單位（除非圓弧恰好通過兩像素中點的特殊情況），甚至這個誤差有可能大到接近一個像素單位1，這與生成曲線的最佳逼近（小于等于0.5個像素單位）的原則不符。

1.2 HCL算法

Hsu、Chow和Liu提出的HCL算法基于這樣的觀察：光柵轉換圓弧可以被視為由y坐標相同的水平線段（稱為行程）所組成。當i≥1時，第i段水平行程的y坐標為yi=r-i+0.5。若假設此行程的最大x坐標為Si，則有

(x+1)2=x2+2x+1。

對于水平行程長度較大的情況，HCL算法可以在一定程度上提高繪制效率。

1.3 YR算法

Yao和Rokne在HCL算法的基礎上對圓弧的特性進行了更仔細的研究，并建立了如下結論：

定理1設D(x,y)為如圖2所示圓弧上滿足y=2x的點，該點將圖中位于45° ～90°的圓弧分為C1和C2兩段，則有

如果水平位移 Li完全包含于 C1，則該水平位移的長度 li≥ 2 ；

如果水平位移Li完全包含于C2，則該水平位移的長度 li≤ 2 。

圖2 由點D將八分圓弧劃分成兩個部分

證明參見文獻[15]。

利用上述性質，YR算法只對C1部分計算水平行程，其迭代關系與 HCL算法基本相同，而對C2部分仍采用傳統的中點法。對C1部分采用的迭代形式如下

如果采用4作為增量，則x可以每次循環步進2點，使得計算量得到減少。

注意到上述迭代中沒有累計誤差，在轉入C2部分后，YR算法需要按如下公式給出初始的誤差

這里引入了2次乘法，增加了算法的復雜性。

2 水平行程的特性

在YR算法中，為了直接計算行程的長度，圓弧被小心地劃分為兩部分。但是，定理1中滿足條件“y=2x”的點D很難簡單精確地確定。此外，直接對迭代并計算出 Si的代價也很高，且不能得到C2部分起始點的誤差。

事實上，如果直接采用誤差來控制每次迭代，則并不需要精確地區分C1和C2。為此，本節建立一個用于描述相鄰水平行程之間關系的結果。

定理2在光柵圓弧中，除了第1個水平行程外，若 45° ～90°圓弧的第 i段水平行程長度為li(i≥1)，則第i+1段的水平行程長度li+1≤li+1。

證 明記第 i段水平行程的起點(,yi)處圓弧與上0.5分度線的距離為 δ ()，圓弧在點(,yi)與(,yi+1)之間 y 方向變化量為 Δ ()，參見圖3。則有

圖3 相鄰的兩個行程的長度比較

證畢。

定理2對復雜模式分析非常有效，如果已知當前行程長度，且下一個行程長度大于當前行程長度，則無須判斷可直接得到該長度。

推 論在定理2的假設下，若第i段水平行程長度為則對所有 j >i，有 lj≤li+1。

3 混合行程算法

根據定理2，不需要關心C1、C2部分的劃分點D的準確位置，代之以檢測第1條長度為1的水平行程。這是因為如果在繪制過程中遇到一條長度為1的水平行程L，則其后的水平行程的長度只能是1或2，而在L之前的行程長度都大于或等于2。因此，可以對L之前和之后的光柵圓弧分別采用不同的處理方法。顯然，只要能夠以較快的方式得到行程長度，就可以消除YR算法中的2x運算。

3.1 最簡單的行程算法

傳統的中點法依據中點與真實曲線的相對位置關系確定被選擇的像素，若用D表示決策參數，則有如下結論：

1）初始決策參數滿足D0=1-r；

2）假設當前被選擇的點是P(xP,yP)，決策參數為DP，則下一步可能的選擇為E和SE，分別對應著水平步進和對角步進，如圖4所示。

圖4 中點法的步進點選擇

如果DP<0，則選擇E，且有

DP+1=DP+ΔE=DP+2xP+3；

如果DP≥0，則選擇SE，且有

DP+1=DP+ΔSE=DP+2(xP-yP)+5。

上述算法可以被容易地改寫成行程算法：

在需要分別處理C1和C2部分時，可將最后的步驟修改為：

if(行程長度>1) goto REPEAT;

這種改寫不需要任何準備工作。如果采用差分，可以進一步減少運算量。

盡管算法1和算法2非常簡單，但他們的效率都不低于HCL算法以及文獻[14]提出的算法1的效率，且不需要任何復雜的運算。以下我們繼續討論建立在上述算法之上的多點步進算法。

3.2 2點步進的水平行程處理

觀察圖 5，仍假設當前被選擇的點是 P(xP,yP)，并記

ΔE=2xP+3，

ΔE代表了水平步進2點時的中點（參考點）處應該累加的誤差。

1）向前步進2點

如果 DP+ΔE≤0，那么，下一次選擇的點為P+2，更新決策參數為

DP+2=DP+2xP+3+2(xP+1)+3=DP+4xP+2，

ΔE=ΔE+4。

圖5 水平方向的2點步進

2）向前步進少于2點

如果 DP+ΔE≥0，那么，下一次選擇的點應為SE1或SE2。于是，繼續判定：

若 DP<0，則水平步進 1點，再對角步進 1點，即選擇P+1和SE2，有

3）行程長度確定

算法中的一項重要工作是判別行程長度，并在遇到長度為1的行程時結束算法。不過，直接對長度進行判別需要附加的運算，因此，本文采取了如下方法：每次的行程計算時，將第1次對條件“DP+ΔE≤0”的判定從循環中獨立。如果該條件為true，再判定條件“DP>0”成立，若此條件成立，則算法結束。這樣，僅在已知行程長度不超過2時判斷其行程長度是否為1。

3.3 沿對角方向2點步進

由中點法的步進規則可知，每次沿對角方向步進消耗的運算量是比較大的。有效地提高 C2部分的繪制效率對整個算法的效率影響很大。

觀察圖6，對于當前被選擇的點P(xP,yP)，記

則ΔSE是沿對角方向步進兩點時的中點（參考點）處應累加的誤差。

于是，初始時的決策參數為DP=DP-1-ΔSE – 4。

1）沿水平和對角各步進1點

如果DP<0，應選擇點P1和P3，有

2）沿對角、水平和對角方向各步進1點如果DP≥0，應首先沿對角方向步進到點P2，并判別：

如果 DP+ΔSE<0，繼續選擇 P3和 P5點，更新決策參數為

DP5=DP+2(ΔSE+xP5)+5，

ΔSE=ΔSE+10。

如果DP+ΔSE≥0，應選擇點P4，有

DP4=DP+2ΔSE+4，

ΔSE=ΔSE+8。

為了避免“DP+ΔE”和“DP+ΔSE”中的加法運算，可以將ΔE和ΔSE取負，并將對D的更新中的ΔE和ΔSE項的符號取反。

圖6 對角方向的2點步進

3.4 算法描述

算法3幾乎每次循環都可以步進2點或3點。在C2部分的連續繪制y坐標相同的2點可以采用畫線命令一次輸出。

4 進一步的改進措施

通常，對圓弧的光柵轉換算法的改進在繪制半徑較大的圓時更有意義，而對半徑較小的圓，基本生成方法是優先的選擇。此外，我們認為對算法的改進主要有兩個方向：

1）將2點步進改為n點步進；

2）進一步詳細分解模式，根據不同模式采取不同的處理方法。

4.1 行程模式的差異

光柵圓弧上不同部分的行程模式差異很大，表1統計了100≤r≤1000時不同行程長度所占有的比例和平均像素數，由此可說明改善哪些部分的繪制算法對整體生成算法的效率影響較大。

根據表1可將1/8圓弧粗略劃分為像素個數接近的3個部分，即水平行程長度為5以上的部分、水平行程長度為2 ～4的部分以及行程長度為1 ～2的部分，而行程為2 ～3的部分接近行程長度為3 ～4的部分的2倍。

表1 圓弧不同區段的像素個數統計(100≤r≤1000)

4.2 4點步進加速

很明顯，如果對整體1/8圓弧每次步進前移4點，算法在水平行程結束時需要較多的判斷，行程長度為2 ～4部分的效率會很低，實際測試也說明了這一點。因此，我們考慮僅在算法2之前增加4點步進作為一種加速措施。如果行程長度小于4，則立即轉入算法3。

我們實際測試了4點步進算法，其效率提高的幅度并不明顯。

4.3 單獨處理特殊的模式

根據像素模式的不同分別采用不同的繪制策略是提高繪制速度的另一種途徑。例如，由表1可知，行程長度為2 ～3的部分占有較大的比重，提高這部分圓弧的繪制繪制速度對整體算法的效率將會產生一定的影響。

由定理2，在第1次繪制一個長度為2的水平行程后，和直到遇到第一個行程長度為1的行程為止，中間的行程長度只能是2或3。因此，可以按下述方法繪制此區間的圓弧：

利用上述部分算法替換掉算法3中的如下語句就得到了一個完整的加速算法

在特別強調效率時，還可以用同樣的方法繪制行程長度為3 ～4的部分。

5 算法分析

雖然可以在理論上對算法所采用的各種運算量進行分析，但需要進行較多的估計和假設。例如，對于圖7，容易說明其中的幾種長度h1,h2,w1,w2，并由這些長度確定各種步進的點數，進而將它們與運算次數相乘后求和即可得出各種運算的總次數。但是，對行程長度為2起始至分點D之間的長度h3和w3很難準確計算。同時，在采用單步法時，可以比較準確地計算出x方向和y方向步進發生的時刻，但在采取2點步進時，就需要做過多粗略的估計[14]，其結果并不準確。

考慮到實際運行程序所得到的時間受多種因素影響，且不同的算法采用的運算也有差異。因此，我們通過實際跟蹤每次運算來得到各種運算的精確次數，并遵循下述原則：

1）統計的運算包括加法、位移、符號判定和邏輯運算，分別記為Na,Ns,Nt和Nc。

2）不包括對x和y的坐標變化的計算。

3）乘2的冪運算被視為位移運算。

4）由于在圓的半徑較小時，一般改進后的算法并沒有什么優勢，故測試只對 32≤r≤1024的圓弧進行（平均值）。

圖7 不同區域的長度

實際測試算法3的結果及YR算法（原文的理論分析結果和實際測試結果）和單點算法的理論分析結果見表2。

表2 不同運算的執行次數比較(33≤r≤1024)

表2對YR算法的測試未包括進入C2部分之前的初始化工作（2次乘法和其他運算）。很明顯，算法 3比單點算法及 YR算法消耗更少的運算量。測試也說明，由于假設較多，文獻[14]的理論分析結果的誤差是較大的。

為了對各種算法有更全面的比較，我們視所有基本運算為1個時間單位，一次乘法為12個時間單位，實際測試并得出了幾種算法實際消耗的平均運算次數（見表3）以及每點平均消耗的基本運算次數（見表4）。圖8顯示了YR算法、本文算法3與中點法的運算量之比。

因為繪制像素的時間與實際硬件有關，本文對I/O次數不進行比較（行程法的I/O次數基本相同）。此外，考慮到HCL算法包含開方、乘法等復雜運算，效率明顯低于YR算法，故僅提供了與YR算法3以及經典中點法之間的比較。

表3和表4表明，本文提出的4種算法都具有比目前已存在算法更高的效率。其中，算法2僅由中點法做簡單改造，其效率略優于YR算法，但該算法極為簡單。算法3代碼長度與YR算法接近，但其消耗的運算量約為YR算法的80%。步進1點平均消耗的基本運算約為3次，僅比單點直線生成算法的每次步進多消耗1次運算。算法 4和算法 5的代碼較長，消耗的運算量約為YR算法的75%。如果將算法4和算法5的加速技術與算法3融合，每點平均運算量可達到2.5左右，其缺點是代碼過長。與HSL算法和YR算法相比，本文算法2和算法3無需任何復雜推導，結構簡單，沒有任何復雜的運算，運算量和程序代碼量較小，具有明顯的優勢。

圖8 YR算法及本文算法3與中點法的運算量之比

表3 計算量比較

表4 繪制每點平均計算量比較

由于行程法可以有效地減少像素輸出的時間消耗，一個很自然的想法就是先計算出組成圓弧的所有行程的長度，再繪制這些行程，這是HSL算法和YR算法的出發點。但是，計算行程長度本身要求解一個非線性方程，求解方法設計、理解困難，只能采取迭代法來避免引入復雜運算，而這種迭代也需要逐點進行，并不會比直接對決策參數的迭代減少運算量。同時，當繪制區域變化時，其初始誤差需要特殊計算，不可避免地要引入乘法。類似地，這種方式也難以對不同的區域采取特殊的有效策略。

試驗也表明，超過2步的多步法很難得到更大的優勢。對于非線性曲線，以較低的代價直接計算出水平行程的長度是困難的，在強調繪制速度時，利用決策參數遞推并結合對復雜模式的細致分析是更好的策略。

6 結 束 語

本文利用2點步進重新構造了傳統中點算法的決策參數，提出了一種快速生成圓弧的混合行程算法。該算法幾乎每次循環都可步進2點，少量循環步進1點或3點，且水平行程可以一次性計算和輸出。利用加速措施得到的幾種新算法可以分別以平均每點 2.7 ～3.7次基本運算的計算量完成整個圓弧生成，效率明顯優于現有的其它算法。由于新算法僅采用中點算法的決策參數進行誤差控制，思想、推導簡單，需要更少的輔助手段，且有利于用更優的策略替代算法中的任何部分，進而得到更高的效率。此外，新算法沒有引入任何復雜運算，如乘法、開方等，有利于硬件實現，且算法的思想可以推廣到橢圓、拋物線等典型曲線的繪制。

[1] Bresenham J E. Algorithm for computer control of a digital Plotter [J]. IBM System Journal,1965,4(1):25-30.

[2] Boyer V,Bourdin J J. Auto-adaptive step straight-line algorithm [J]. IEEE Computer Graphics and Applications,2000,20(5): 67-69.

[3] 程 錦,陸國棟,譚建榮. 一種快速圓弧繪制算法[J].軟件學報,2002,13(12): 2275-2280.

[4] 劉勇奎,石教英. 圓的像素級生成及反走樣算法[J].計算機輔助設計與圖形學學報,2005,17(1): 34-41.

[5] Gill G W. N-step incremental straight line algorithms [J].IEEE Computer Graphics and Applications,1994,14(3): 66-72.

[6] Fung K Y,Nicholl T M,Dewdney A K. A run-length slice line drawing algorithm without division operations [J]. EUROGRAPHICS '92,1992,11(3):267-277.

[7] Boyer V,Bourdin J J. Fast lines: a span by span method [J]. Computer Graphics Forum,1999,18(3):377-384.

[8] Bresenham J E. A linear algorithm for incremental digital display of circular arcs [J]. Communications of the Association for Computing Machinery [J]. 1977,20(2): 100-106.

[9] Foley J D,Dam A V,Feiner S K,et al. Computer graphics: principles and practice [M]. Addison-Wesley Publishing Company,Reading Massachusetts,1990:89-172.

[10] Kuzmin Y P. An efficient circle-drawing algorithm [J].Computer Graphics Forum,1990,9(4): 333-336.

[11] 牛連強,馮海文,吳 澎. 利用殘差控制的快速圓弧生成與反走樣算法[J]. 計算機輔助設計與圖形學學報,2011,23(2): 232-239.

[12] Wu X,Rokne J. Double-step incremental generation of lines and circles [J]. Computer Vision Graphics,and Image Processing,1987,37(3): 331-344.

[13] Wu X,Rokne J. Double-step generation of ellipses [J].IEEE Computer Graphics and Applications,1989,9(3): 56-69.

[14] Hsu S Y,Chow L R,Liu C H. A new approach for the generation of circles [J]. Computer Graphics Forum [J]. 1993,12(2): 105-109.

[15] Yao C,Rokne J G. Hybrid scan-conversion of circles [J].IEEE Transactions on Visualization and Computer Graphics,1995,1(4): 311-318.

[16] Yao C,Rokne J G. Run-length slice algorithms for the scan-conversion of ellipses [J]. Computer &Graphics,1998,22(4): 463-477.

[17] 牛連強,薛 瑾,朱天翔. 快速繪制圓弧的行程算法[J]. 沈陽工業大學學報,2010,32(4): 411-416.