基于FPGA的圓弧快速生成算法及其應(yīng)用

張小永

（北京青云航空儀表有限公司 北京市 101300）

1 引言

圓弧是組成計算機(jī)圖形最基本的元素之一。在機(jī)載顯示系統(tǒng)中，常使用圓弧繪制天地球等圖形?，F(xiàn)有圓弧繪制算法大多以減少圓弧中每點坐標(biāo)計算的復(fù)雜度為研究對象，以簡單的方法獲得離實際圓弧線段最近的光柵點[1-3]。

計算機(jī)圖形學(xué)中通常采用Bresenham 算法和數(shù)字微分分析儀（digital diあerential analyzer，DDA）算法繪制圓弧。這兩種算法采用逐點遞推步進(jìn)的方式繪制圓弧，這種遞推步進(jìn)的繪制方式由于繪制的各點存在嚴(yán)格的先后關(guān)系不易實現(xiàn)并行運算，因此目前多核處理器和FPGA 的并行計算能力的大幅提高，并不能有效提高繪制速度。

本算法采用逐點計算各像素到圓心距離以確定該點是否在待繪制圓弧上的方式進(jìn)行圓弧繪制。該方式較DDA 和Bresenham 圓弧繪制方法增加了計算量，但解除了相鄰像素點的遞推關(guān)系，因為可以在FPGA 實現(xiàn)時通過設(shè)計多級流水線大大提高計算速度。

2 算法原理

本算法利用點P 到圓心O 的距離l 是否在圓弧范圍內(nèi)，判定點P 是否在半徑R、寬度W 的圓弧范圍內(nèi)，并通過點P 到圓弧角度邊界的距離d 判定點P 是否在圓弧角度邊界范圍內(nèi)。對于在圓弧線寬邊界和起止角度邊界的點，利用Wu 反走樣算法進(jìn)行反走樣處理，使繪制的圓弧更加美觀。另外，利用圓的對稱性，可以通過計算第一象限內(nèi)的四分之一圓弧像素坐標(biāo)擴(kuò)展得到整個圓弧的像素坐標(biāo)。

2.1 點P到圓心O的距離小l

2.2 點P到圓弧邊界距離d

因此可得：

2.3 圓弧線寬邊界反走樣處理

計算點P 沿半徑方向的線寬邊界顏色系數(shù)KR。按點P 到圓心O 的距離l 與半徑R 和線寬W 的關(guān)系確定KR，具體如下：

圖1：圓弧生成算法原理示意圖

2.4 圓弧角度邊界反走樣處理

計算點P 沿圓弧方向的角度邊界顏色系數(shù)Kθ。按P 到圓弧角度邊界的距離d 確定Kθ，具體如下：

（1）當(dāng) 時，KR=0；

（3）當(dāng)0＜d 時，KR=1；

2.5 計算反走樣系數(shù)

根據(jù)線寬邊界顏色系數(shù)KR和角度邊界顏色系數(shù)Kθ，計算得到第P 的反走樣系數(shù)K。

3 算法FPGA實現(xiàn)

本算法的實現(xiàn)需要依靠FPGA 強(qiáng)大的計算能力，計算預(yù)估圓弧所在區(qū)域內(nèi)各像素點到圓心的距離和到圓弧邊界弧度的距離判定該像素是否在圓弧上，從而實現(xiàn)圓弧的快速生成。如圖2 所示，本算法在FPGA 中實現(xiàn)時分為四級流水線。

圖2：圓弧生成算法FPGA 實現(xiàn)原理框圖

第一級流水線實現(xiàn)1 象限四分圓的坐標(biāo)序列生成。如圖3 所示，生成坐標(biāo)時在的區(qū)域內(nèi)水平掃描生成圓弧像素坐標(biāo)序列。在生成時利用剔除不在圓弧內(nèi)的點。利用沿掃描方向像素到圓心的距離l 單調(diào)遞增的規(guī)律，在掃描到時結(jié)束本行掃描。利用掃描線與圓弧內(nèi)徑交點隨y 坐標(biāo)減小增大，因此在進(jìn)行新的一行掃描時，起點設(shè)置為上一行掃描線與圓弧內(nèi)徑交點的x 坐標(biāo)。

第三級流水線依據(jù)l、d 和Color 計算各坐標(biāo)的顏色值，對于在圓弧線寬邊界和起止角度邊界的點，利用Wu 反走樣算法進(jìn)行反走樣處理。并依據(jù)對稱性對整個圓弧進(jìn)行擴(kuò)展。

第四級流水線將計算得到的圓弧各點坐標(biāo)和顏色值寫入圖像存儲空間。

4 算法仿真與測試驗證

圖4 給出了對本算法原理利用Matlab 進(jìn)行仿真的效果圖，圖中所繪制的圓弧準(zhǔn)確美觀，圓弧的內(nèi)外徑邊界和兩端點邊界反走樣效果理想。圖5 給出了本算法在某機(jī)載顯示設(shè)備中實現(xiàn)的圓弧繪制效果。

5 結(jié)論

經(jīng)過上述驗證，本文設(shè)計的基于FPGA 的圓弧快速生成算法，能夠依靠FPGA 強(qiáng)大的計算能力，通過計算預(yù)估圓弧所在區(qū)域內(nèi)各像素點到圓心的距離和到圓弧邊界弧度的距離判定該像素是否在圓弧上，從而實現(xiàn)圓弧的快速生成。相較計算機(jī)圖形學(xué)常用的Bresenham 圓生成算法和數(shù)字微分分析儀算法（digital diあerentialanalyzer，DDA），本方法消除了圓弧生成過程中逐點遞推計算的先后關(guān)系，能夠充分利用FPGA 并行計算的優(yōu)勢，提高圓弧繪制速度。另外通過計算像素到圓弧邊界弧度的距離來處理圓弧的兩個端點，使圓弧繪制更美觀。仿真和實驗結(jié)果表明：本圓弧生成算法繪制的圓弧視覺效果好，時間效率高，達(dá)到了工程應(yīng)用的目的。

圖3：四分圓的坐標(biāo)序列生成示意圖

圖4：MATLAB 仿真效果圖

圖5：某機(jī)載顯示設(shè)備顯示效果圖