基于FPGA的圓弧快速生成算法及其應用

張小永

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

1 引言

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

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

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

2 算法原理

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

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

2.2 點P到圓弧邊界距離d

因此可得：

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

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

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

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

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

（1）當 時，KR=0；

（3）當0＜d 時，KR=1；

2.5 計算反走樣系數

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

3 算法FPGA實現

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

圖2：圓弧生成算法FPGA 實現原理框圖

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

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

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

4 算法仿真與測試驗證

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

5 結論

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

圖3：四分圓的坐標序列生成示意圖

圖4：MATLAB 仿真效果圖

圖5：某機載顯示設備顯示效果圖