對圖形學算法的改進

胡樹杰

（沈陽理工大學 信息科學與工程學院，沈陽 110168）

0 引言

計算機圖形學的基礎算法一般在工具軟件中會被無數次調用，其執行速度是至關重要的，所以它的生成算法的優劣對整個圖形系統效率的影響非常大。因此，對一些基礎算法的改進，使其進一步完善是必要的。

在計算機圖形學的領域中，圓的生成算法比較成熟，經典的單點算法有多種，其中比較熟悉的有Bresenham算法等。本論文對圓的生成算法進行了研究和探索。首先，通過對Bresenham算法畫圓算法進行分析，在像素點的選取上進行創新，通過新算法畫出的圓比Bresenham畫圓法畫出的圓更接近真實的圓；其次，新算法的基礎上，實現雙步畫圓，算法的效率的得到最大的提高；第三，對新算法與Bresenham在精度與速度上進行比較，結果顯示新算法比Bresenham有很大的優勢。

另外，在圓的生成過程中，僅需生成一個八分之一圓，那么圓的其它部分就可以通過一系列的簡單反射變換得到。

1 基本思想

通過分析Bresenham畫圓算法我們會發現，算法的主要計算量是在對判斷變量△d的計算上。本文也定義變量△d為判斷變量。

如圖1所示，假設P0（x0，y0）點為當前點，為了最佳逼近該圓，根據圓弧的走向，下一點像素的取法只能是正右方像素和右下方像素兩種選擇，即下一點在 P1（x1，y1）和 P2（x2，y2）兩個點中選取一個。P1點和P2點究竟選取哪個點作為下一步的主要取決于這兩個點到圓周的距離更小。

2 算法推導

2.1 點的選取

以P1（x1，y1）為基準坐標，則P0的坐標為P0（x1-1, y1），P2的坐標為 P2（x1，y1-1），于是判斷公式表示為：

上面這個公式可以判斷哪一點是離圓周最近的點，即應該選取的點。

圖1 算法示意圖

根據公式（2）可以進一步化簡為：

繼續化簡可得：

根據公式（4）可以判斷出究竟下一點的選取是P1還是P2。令：

為了簡化計算，可以歸納f (x, y)的遞推公式。即根據待確定的兩個點的上一個點就可以確定這兩個點中到底選取哪個點作為所需要畫的點。

即令

可得以下結論：

當f (x, y)＞0時，下一點取P2；

當f (x, y)＜0時，下一點取P1；

當f (x, y)＝0時，下一點取P1或P2。

則f (x, y)的符號，就可以判斷橫坐標x對應的點的選取。

若f (x, y)≤0取P1為下一個像素點，則再下一點為P3和P4中的一個，根據判別式可得

當則f (x1, y1)≤0時選定P1，再根據公式（6）判斷出下一點是P3或是P4。

若f (x1, y1)＞0時選定P2，為x坐標對應的點，則下一點的選取在P4(x1+1, y1-1)和P5(x1+1, y1-2)中來選取一個。

再根據公式（5）導出公式（7），即已知選定P2后，繼續在P4，P5中選取下一個像素點的公式：

當 d＞0時，下一點取P5為畫圓向下進行的像素點；

當 d＜0時，下一點取P4為畫圓向下進行的像素點；

當 d＝0時，下一點取P4或P5為畫圓向下進行的像素點。

通過以上推導，對Bresenham算法進行了改進。使計算避免了復雜的浮點數和平方等運算，計算過程只有簡單的整數乘法和加法。

2.2 雙步圓推導

目前圖形學的雙步生成算法也逐漸被人們所關注。所謂雙步法就是算法每一次循環產生兩個象素，且雙步生成算法與單點生成算法在每次循環中具有相同的計算量，所以雙步生成算法僅使用了單點生成算法一半的循環量，這意味著雙步圓的生成速度大約可以提高一半，因而算法在運算速度上比單點算法要快。

本文結合雙步算法的思想以及改變像素級選取點的方法，設計出一個基于改進的bresenham畫圓算法的雙步畫圓算法。

利用改變像素級算法中公式（5）的方法判定下一點是P1或P2的算法來進一步推導雙步畫圓的算法。

當選定P1后，下一個像素點為P3或P4點，這時用P3到圓的距離與P4到圓的距離之差與P1到圓的距離與P2到圓的距離之差做以下推導：

公式（8）中df (x1, y1)不是數學意義上的微分，而是用定義的距離之差的P1與P2的距離之差和P3與P4的距離之差的差值，即把這個差值推導成一種遞推公式，等選下一點時可以根據P3與P4的距離之差向下推導，即當f (x, y)≤0時，df (x1, y1)表示P1，P2的距離之差與P3，P4的距離之差的差值，可以推導第二代與第三代的關系，以此類推。

1）若f (x0, y0)≤0時，根據公式（8）得出：

若f (x0+1, y0)≤0，取點P1(x0+1, y0),根據公式（9）得出：

若f (x0+1, y0)＞0，取P2(x0+1, y0-1)，根據公式（9），（10）導出

同f (x1, y1)≤0，導出當f (x1, y1)＞0時，

2）若f (x0, y0)＞0時，根據公式（12）導出：

若f (x0+1, y0)≤0，取點P1(x0+1, y0)，根據公式（12），（13）導出：

若f (x0+1, y0)＞0，取P2(x0+1, y0-1)，根據公式（12），（13）導出：

通過f (x0+2, y0)的符號就可以確定第二跳最接近圓弧的點。從而根據上一步中f (x0, y0)就可以確定下兩個點的坐標，因此算法中每次循環可以確定兩個點的坐標，實現雙步畫圓。

根據以上推導，生成基于改進的bresenham的雙步畫圓算法。

程序代碼如下：

void DrawCircle(int x, int y, int r)

{ int m = 0,n = r;

int u,v;

long count = -2*r +1;

int i;

for (i=0; m＜n; i++)

{if (i＞0)

{ m += 1;

if(count＞0)

{count+=4*(m-n);

}

else

{count+=4*m+2;

}

if(count＞0)

{ n -= 1;

u=m;v=n;

m+=1;

count+=4*(m-n)-2;

if (count＞0)

{n-=1;

}

}

else

{ u=m;v=n;

m+=1;

count+=4*m+2;

if (count＞0)

{n-=1;

}

}

}

3 新算法與Bresenham算法的比較

3.1 新算法與Bresenham算法在速度比較

為了驗證新算法的效率，本文對算法的執行速度進行了量化度量，并與Bresenham算法進行比較。對于算法速度通過分別用新算法與Bresenham算法測量畫500個半徑為200的圓所需要的時間來度量。在執行之前通過設置系統時鐘函數clock()設定時鐘，結束后通過此函數獲取完成時間 。

運行結果： 用Bresenham算法畫500圓需要的時間為3.131868秒；用新算法畫500圓需要的時間為2.747253秒。結果表明，用新算法畫圓的速度比Bresenham畫圓算法速度要快。

3.2 新算法與Bresenham算法在精確度上的比較

對于算法精度比較，本文通過求畫出圓上每一個點與實際圓的點的距離的平方差的平均值來進行新算法與Bresenham算法在精度上的比較。設目標圓弧點的坐標為法得出的對應的點的坐標為即通過以下公式來測量：

比較結果： Bresenham算法得出的方差為87.18881；而新算法得出的方差為68.433566。可以看出新的畫圓算法比Bresenham畫圓算法更接近真實，精確度更高。

4 結束語

通過以上的分析，改進的圓的算法無論在速度上還是精度上都要優于傳統的Bresenham畫圓算法。但是對于一些經典算法改進的余地已很有限，今后工作的重點應在對多步（多于雙步）算法的開發上。多步算法結合圓的對稱點方法將使圓的生成算法具有更快的速度。

[1] 孫家廣, 楊長貴. 計算機圖形學(新版)[M]. 北京: 清華大學出版社, 1995.

[2] 金廷贊. 計算機圖形學[M]. 杭州: 浙江大學出版社,1988.

[3] 沈紅.一個改進的象素級圓的單點生成算法[J].沈陽工業學院學報,2003, 22(2).

[4] 沈紅. 一個圓的雙步生成算法的提出[J]. 沈陽工業大學學報, 2002, 24(6).

[5] 王曙燕.C語言程序設計(第一版)[M].科學出版社,2008:23-58.