對(duì)圖形學(xué)算法的改進(jìn)

胡樹(shù)杰

（沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110168）

0 引言

計(jì)算機(jī)圖形學(xué)的基礎(chǔ)算法一般在工具軟件中會(huì)被無(wú)數(shù)次調(diào)用，其執(zhí)行速度是至關(guān)重要的，所以它的生成算法的優(yōu)劣對(duì)整個(gè)圖形系統(tǒng)效率的影響非常大。因此，對(duì)一些基礎(chǔ)算法的改進(jìn)，使其進(jìn)一步完善是必要的。

在計(jì)算機(jī)圖形學(xué)的領(lǐng)域中，圓的生成算法比較成熟，經(jīng)典的單點(diǎn)算法有多種，其中比較熟悉的有Bresenham算法等。本論文對(duì)圓的生成算法進(jìn)行了研究和探索。首先，通過(guò)對(duì)Bresenham算法畫圓算法進(jìn)行分析，在像素點(diǎn)的選取上進(jìn)行創(chuàng)新，通過(guò)新算法畫出的圓比Bresenham畫圓法畫出的圓更接近真實(shí)的圓；其次，新算法的基礎(chǔ)上，實(shí)現(xiàn)雙步畫圓，算法的效率的得到最大的提高；第三，對(duì)新算法與Bresenham在精度與速度上進(jìn)行比較，結(jié)果顯示新算法比Bresenham有很大的優(yōu)勢(shì)。

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

1 基本思想

通過(guò)分析Bresenham畫圓算法我們會(huì)發(fā)現(xiàn)，算法的主要計(jì)算量是在對(duì)判斷變量△d的計(jì)算上。本文也定義變量△d為判斷變量。

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

2 算法推導(dǎo)

2.1 點(diǎn)的選取

以P1（x1，y1）為基準(zhǔn)坐標(biāo)，則P0的坐標(biāo)為P0（x1-1, y1），P2的坐標(biāo)為 P2（x1，y1-1），于是判斷公式表示為：

上面這個(gè)公式可以判斷哪一點(diǎn)是離圓周最近的點(diǎn)，即應(yīng)該選取的點(diǎn)。

圖1 算法示意圖

根據(jù)公式（2）可以進(jìn)一步化簡(jiǎn)為：

繼續(xù)化簡(jiǎn)可得：

根據(jù)公式（4）可以判斷出究竟下一點(diǎn)的選取是P1還是P2。令：

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

即令

可得以下結(jié)論：

當(dāng)f (x, y)＞0時(shí)，下一點(diǎn)取P2；

當(dāng)f (x, y)＜0時(shí)，下一點(diǎn)取P1；

當(dāng)f (x, y)＝0時(shí)，下一點(diǎn)取P1或P2。

則f (x, y)的符號(hào)，就可以判斷橫坐標(biāo)x對(duì)應(yīng)的點(diǎn)的選取。

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

當(dāng)則f (x1, y1)≤0時(shí)選定P1，再根據(jù)公式（6）判斷出下一點(diǎn)是P3或是P4。

若f (x1, y1)＞0時(shí)選定P2，為x坐標(biāo)對(duì)應(yīng)的點(diǎn)，則下一點(diǎn)的選取在P4(x1+1, y1-1)和P5(x1+1, y1-2)中來(lái)選取一個(gè)。

再根據(jù)公式（5）導(dǎo)出公式（7），即已知選定P2后，繼續(xù)在P4，P5中選取下一個(gè)像素點(diǎn)的公式：

當(dāng) d＞0時(shí)，下一點(diǎn)取P5為畫圓向下進(jìn)行的像素點(diǎn)；

當(dāng) d＜0時(shí)，下一點(diǎn)取P4為畫圓向下進(jìn)行的像素點(diǎn)；

當(dāng) d＝0時(shí)，下一點(diǎn)取P4或P5為畫圓向下進(jìn)行的像素點(diǎn)。

通過(guò)以上推導(dǎo)，對(duì)Bresenham算法進(jìn)行了改進(jìn)。使計(jì)算避免了復(fù)雜的浮點(diǎn)數(shù)和平方等運(yùn)算，計(jì)算過(guò)程只有簡(jiǎn)單的整數(shù)乘法和加法。

2.2 雙步圓推導(dǎo)

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

本文結(jié)合雙步算法的思想以及改變像素級(jí)選取點(diǎn)的方法，設(shè)計(jì)出一個(gè)基于改進(jìn)的bresenham畫圓算法的雙步畫圓算法。

利用改變像素級(jí)算法中公式（5）的方法判定下一點(diǎn)是P1或P2的算法來(lái)進(jìn)一步推導(dǎo)雙步畫圓的算法。

當(dāng)選定P1后，下一個(gè)像素點(diǎn)為P3或P4點(diǎn)，這時(shí)用P3到圓的距離與P4到圓的距離之差與P1到圓的距離與P2到圓的距離之差做以下推導(dǎo)：

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

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

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

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

同f (x1, y1)≤0，導(dǎo)出當(dāng)f (x1, y1)＞0時(shí)，

2）若f (x0, y0)＞0時(shí)，根據(jù)公式（12）導(dǎo)出：

若f (x0+1, y0)≤0，取點(diǎn)P1(x0+1, y0)，根據(jù)公式（12），（13）導(dǎo)出：

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

通過(guò)f (x0+2, y0)的符號(hào)就可以確定第二跳最接近圓弧的點(diǎn)。從而根據(jù)上一步中f (x0, y0)就可以確定下兩個(gè)點(diǎn)的坐標(biāo)，因此算法中每次循環(huán)可以確定兩個(gè)點(diǎn)的坐標(biāo)，實(shí)現(xiàn)雙步畫圓。

根據(jù)以上推導(dǎo)，生成基于改進(jìn)的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算法在速度比較

為了驗(yàn)證新算法的效率，本文對(duì)算法的執(zhí)行速度進(jìn)行了量化度量，并與Bresenham算法進(jìn)行比較。對(duì)于算法速度通過(guò)分別用新算法與Bresenham算法測(cè)量畫500個(gè)半徑為200的圓所需要的時(shí)間來(lái)度量。在執(zhí)行之前通過(guò)設(shè)置系統(tǒng)時(shí)鐘函數(shù)clock()設(shè)定時(shí)鐘，結(jié)束后通過(guò)此函數(shù)獲取完成時(shí)間 。

運(yùn)行結(jié)果： 用Bresenham算法畫500圓需要的時(shí)間為3.131868秒；用新算法畫500圓需要的時(shí)間為2.747253秒。結(jié)果表明，用新算法畫圓的速度比Bresenham畫圓算法速度要快。

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

對(duì)于算法精度比較，本文通過(guò)求畫出圓上每一個(gè)點(diǎn)與實(shí)際圓的點(diǎn)的距離的平方差的平均值來(lái)進(jìn)行新算法與Bresenham算法在精度上的比較。設(shè)目標(biāo)圓弧點(diǎn)的坐標(biāo)為法得出的對(duì)應(yīng)的點(diǎn)的坐標(biāo)為即通過(guò)以下公式來(lái)測(cè)量：

比較結(jié)果： Bresenham算法得出的方差為87.18881；而新算法得出的方差為68.433566?？梢钥闯鲂碌漠媹A算法比Bresenham畫圓算法更接近真實(shí)，精確度更高。

4 結(jié)束語(yǔ)

通過(guò)以上的分析，改進(jìn)的圓的算法無(wú)論在速度上還是精度上都要優(yōu)于傳統(tǒng)的Bresenham畫圓算法。但是對(duì)于一些經(jīng)典算法改進(jìn)的余地已很有限，今后工作的重點(diǎn)應(yīng)在對(duì)多步（多于雙步）算法的開(kāi)發(fā)上。多步算法結(jié)合圓的對(duì)稱點(diǎn)方法將使圓的生成算法具有更快的速度。

[1] 孫家廣, 楊長(zhǎng)貴. 計(jì)算機(jī)圖形學(xué)(新版)[M]. 北京: 清華大學(xué)出版社, 1995.

[2] 金廷贊. 計(jì)算機(jī)圖形學(xué)[M]. 杭州: 浙江大學(xué)出版社,1988.

[3] 沈紅.一個(gè)改進(jìn)的象素級(jí)圓的單點(diǎn)生成算法[J].沈陽(yáng)工業(yè)學(xué)院學(xué)報(bào),2003, 22(2).

[4] 沈紅. 一個(gè)圓的雙步生成算法的提出[J]. 沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào), 2002, 24(6).

[5] 王曙燕.C語(yǔ)言程序設(shè)計(jì)(第一版)[M].科學(xué)出版社,2008:23-58.