張小永

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

1 引言

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

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

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

2 算法原理

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

2.1 點(diǎn)P到圓心O的距離小l

2.2 點(diǎn)P到圓弧邊界距離d

因此可得：

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

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

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

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

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

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

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

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

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

3 算法FPGA實(shí)現(xiàn)

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

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

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

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

第四級(jí)流水線將計(jì)算得到的圓弧各點(diǎn)坐標(biāo)和顏色值寫(xiě)入圖像存儲(chǔ)空間。

4 算法仿真與測(cè)試驗(yàn)證

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

5 結(jié)論

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

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

圖4：MATLAB 仿真效果圖

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