張小永
(北京青云航空儀表有限公司 北京市 101300)
圓弧是組成計(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ì)算速度。
本算法利用點(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)。
因此可得:
計(jì)算點(diǎn)P 沿半徑方向的線寬邊界顏色系數(shù)KR。按點(diǎn)P 到圓心O 的距離l 與半徑R 和線寬W 的關(guān)系確定KR,具體如下:
圖1:圓弧生成算法原理示意圖
計(jì)算點(diǎn)P 沿圓弧方向的角度邊界顏色系數(shù)Kθ。按P 到圓弧角度邊界的距離d 確定Kθ,具體如下:
(1)當(dāng) 時(shí),KR=0;
(3)當(dāng)0<d 時(shí),KR=1;
根據(jù)線寬邊界顏色系數(shù)KR和角度邊界顏色系數(shù)Kθ,計(jì)算得到第P 的反走樣系數(shù)K。
本算法的實(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 給出了對(duì)本算法原理利用Matlab 進(jìn)行仿真的效果圖,圖中所繪制的圓弧準(zhǔn)確美觀,圓弧的內(nèi)外徑邊界和兩端點(diǎn)邊界反走樣效果理想。圖5 給出了本算法在某機(jī)載顯示設(shè)備中實(shí)現(xiàn)的圓弧繪制效果。
經(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è)備顯示效果圖