一種Windows下實(shí)時(shí)高效圖形繪制算法

摘 要:針對(duì)實(shí)時(shí)系統(tǒng)中對(duì)圖形繪制速度的特殊要求，提出一種應(yīng)用于Windows環(huán)境下應(yīng)用程序客戶區(qū)中的高效圖形繪制算法，給出實(shí)現(xiàn)圖形水平平移、豎直平移、自由平移、水平縮放、豎直縮放、自由縮放的關(guān)鍵技術(shù)。該算法基于無(wú)效矩形確定圖形中需要繪制的數(shù)據(jù)和坐標(biāo)軸范圍，可避免大量不必要的重繪工作，實(shí)現(xiàn)圖形高效、快速繪制，保證操作的實(shí)時(shí)性。利用內(nèi)存DC繪圖可避免圖形閃爍，增強(qiáng)圖形顯示效果。與Matlab中繪圖函數(shù)進(jìn)行性能比較，證明了提出的圖形繪制算法是有效的。關(guān)鍵詞:圖形繪制; 無(wú)效矩形; 圖形閃爍; Matlab

中圖分類號(hào):TN911-34; TP3111文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)16-0043-04

Real-time and Efficient Graphics-drawing Algorithm under Windows Condition

ZHANG Zhi-min， OU Jian-ping， HUANG Fu-kan

(College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China)

Abstract: An efficient graphics-drawing algorithm applied to the client area of Windows system is proposed to meet the requirement of real-time systems. The key technologies which can realize the patterns′ horizontal displacement， vertical translation， unconstrained translation， image horizontal scaling， image vertical scaling and image unconstrained scaling are presented. The data and axis scale which need to be drawed in graphics are determined with the algorithm by utilizing the invalid rectangle to avoid lots of unnecessary redrawing and realize efficient and fast graphics-drawing. With the memory DC， graphics flicker is avoided， as a result， the vividness of graphics is enhanced. In comparison with the plot function in Matlab， simulation results show that the algorithm proposed in this paper is efficient.Keywords: graphics drawing; invalid rectangle; graphics flicker; matlab

0 引 言

隨著計(jì)算機(jī)科學(xué)技術(shù)的飛速發(fā)展，計(jì)算機(jī)已經(jīng)深入到各行各業(yè)，人類也隨著發(fā)展產(chǎn)生了大量的信息數(shù)據(jù)，這些信息數(shù)據(jù)為生產(chǎn)和研究提供了依據(jù)。在分析過(guò)程中，以圖形方式顯示數(shù)據(jù)可以達(dá)到直觀的效果，給決策人以感官上的啟發(fā)[1-3]。例如在無(wú)線電工程等領(lǐng)域，經(jīng)常需要以圖形化方式監(jiān)視無(wú)線通信信號(hào)的時(shí)域波形、頻譜波形等[4]。為便于獲取包含于數(shù)據(jù)中的更詳細(xì)的信息，要求操作人員監(jiān)視信號(hào)時(shí)能隨時(shí)察看圖形的局部細(xì)節(jié)，即要求圖形具有水平縮放、豎直縮放、自由縮放、水平平移、豎直平移、自由平移等功能，而且所有這些對(duì)圖形的操作都要求能實(shí)時(shí)進(jìn)行[5]，這就給圖形顯示程序的設(shè)計(jì)帶來(lái)一定難度。

Windows操作系統(tǒng)提供了圖形設(shè)備接口(GUI)[6-8]。在Windows操作系統(tǒng)中，當(dāng)移動(dòng)某個(gè)應(yīng)用程序窗口的位置，致使窗口原來(lái)被遮蓋的部分顯露出來(lái)，或者改變窗口大小時(shí)，Windows都要向應(yīng)用程序發(fā)送WMPAINT消息，以告知應(yīng)用程序有一部分客戶區(qū)域已變?yōu)闊o(wú)效，需要重新繪制，即重繪。這部分需要重繪的區(qū)域稱為客戶區(qū)無(wú)效區(qū)域，由于一般是矩形，故又稱無(wú)效矩形。通常情況下無(wú)效矩形的大小不等于客戶區(qū)，所以重繪時(shí)沒(méi)有必要繪制整個(gè)客戶區(qū)，只需繪制客戶區(qū)中位于無(wú)效矩形中的那部分圖形即可，這樣可以顯著提高圖形繪制代碼執(zhí)行速度，減少繪制工作量，實(shí)現(xiàn)實(shí)時(shí)操作。

本文基于對(duì)無(wú)效矩形的分析，針對(duì)水平縮放、豎直縮放、自由縮放，水平平移、豎直平移、自由平移等實(shí)時(shí)操作的要求，提出一種在Windows應(yīng)用程序窗口客戶區(qū)中高效、快速繪制圖形的算法。

1 算法描述

如圖 1所示，在客戶區(qū)坐標(biāo)系中，采用MMTEXT映射模式，即坐標(biāo)度量單位是像素，客戶區(qū)左上角o為坐標(biāo)原點(diǎn)，ox軸方向水平向右，oy軸方向豎直向下。為便于敘述，設(shè)要顯示的圖形只由1條曲線組成。曲線上共包含N個(gè)數(shù)據(jù)點(diǎn)，數(shù)據(jù)大小分別為:Y0，Y1，Y2，…，YN-1，其中最大、最小值分別為Ymax，Ymin，各數(shù)據(jù)點(diǎn)在客戶區(qū)坐標(biāo)系中的坐標(biāo)分別為:(x0，y0)，(x1，y1)，(x2，y2)，…，(xI，yI)，…，(xN-1，yN-1)。其中:I為基于0的數(shù)據(jù)索引，即0≤I≤N-1。假設(shè)曲線上各數(shù)據(jù)點(diǎn)在水平方向上均勻分布，Δx為兩個(gè)相鄰數(shù)據(jù)點(diǎn)之間的水平距離。(x，y)為曲線上任意一點(diǎn)，它對(duì)應(yīng)于數(shù)據(jù)Y，yc為圖形縱向分布中心的縱坐標(biāo)，對(duì)應(yīng)于數(shù)據(jù)Yc，根據(jù)簡(jiǎn)單的數(shù)學(xué)推導(dǎo)，可得下列方程組:



I=x-x0Δx， Δx>0

Y=Yc-y-yc2Rly，ly>0，R>0(1)



式中:R為圖形縱向分布半徑，且:

Yc=(Ymax+Ymin)/2

ly=Ymax-Ymin

圖1 應(yīng)用程序客戶區(qū)圖形繪制示意圖

實(shí)時(shí)高效繪制圖形算法的總體思想是，當(dāng)對(duì)圖形實(shí)施操作時(shí)，保持客戶區(qū)坐標(biāo)系和映射模式固定不變，通過(guò)改變x0，yc，Δx，R的值并重繪，實(shí)現(xiàn)圖形實(shí)時(shí)變化，具體分析如下:

保持yc，Δx，R不變，增大x0，圖形整體水平右移，減小x0，圖形整體水平左移。

保持x0，Δx，R不變，增大yc，圖形豎直向上整體平移，減小yc，圖形豎直向下整體平移。

自由平移圖形，可視作先對(duì)圖形做水平平移，再對(duì)圖形做豎直平移的組合。

保持x0，yc，R不變，增大Δx，圖形在水平方向上放大，減小Δx，圖形在水平方向上縮小。

保持x0，yc，Δx不變，增大R，圖形在豎直方向上放大，減小R，圖形在豎直方向上縮小。

當(dāng)x0，yc，Δx，R中某一個(gè)值改變后，及時(shí)調(diào)用InvalidateRect函數(shù)使需要重繪的區(qū)域無(wú)效，這將驅(qū)使Windows操作系統(tǒng)給應(yīng)用程序發(fā)送WMPAINT消息，在該消息響應(yīng)處理中，利用更新的x0，yc，Δx，R重繪無(wú)效區(qū)域，達(dá)到動(dòng)態(tài)、實(shí)時(shí)顯示圖形的目的。

1.1 水平方向縮放圖形

對(duì)圖形的操作常用鼠標(biāo)進(jìn)行，當(dāng)需要水平縮放圖形時(shí)，為增加圖形縮放視覺(jué)效果，應(yīng)使位于鼠標(biāo)指針處的數(shù)據(jù)在縮放前后的位置保持不變。設(shè)(x，y)是鼠標(biāo)指針當(dāng)前位置，(x′，y′)是水平縮放后的位置，則應(yīng)有:

x-x0Δx=x′-x′0Δx′x′=x， y′=y(2)

式中:Δx′為已知參數(shù)。解方程組可得到x′0，然后重繪客戶區(qū)圖形，實(shí)現(xiàn)水平縮放。

1.2 豎直方向縮放圖形

豎直縮放圖形時(shí)，為了增加縮放視覺(jué)效果，同樣要求鼠標(biāo)指針處的圖形在縮放前后的位置保持不變，設(shè)(x，y)為鼠標(biāo)指針當(dāng)前位置，(x′，y′)為豎直縮放后的位置，則有:

y-ycR=y′-y′cR′x′=x， y′=y(3)

式中:R′是已知參數(shù)。解方程組得到y(tǒng)′c，然后重繪客戶區(qū)圖形，實(shí)現(xiàn)垂直縮放。

1.3 自由縮放圖形

自由縮放是指在按下鼠標(biāo)鍵后不放開(kāi)并拖動(dòng)鼠標(biāo)，形成一個(gè)矩形區(qū)域，對(duì)該區(qū)域中的圖形進(jìn)行縮放。這樣可以觀察這部分圖形細(xì)節(jié)。在該縮放模式下，鼠標(biāo)拖出矩形區(qū)域與客戶區(qū)當(dāng)前可見(jiàn)范圍在縮放前后相對(duì)應(yīng)。設(shè)(l，t)，(r，b)分別為鼠標(biāo)選定矩形左上角和右下角坐標(biāo)，(x1，y1)，(x2，y2)則分別為客戶區(qū)左上角和右下角坐標(biāo)，易知:

l-x0Δx=x1-x′0Δx′

r-x0Δx=x2-x′0Δx′，t-ycR=y1-y′cR′

b-ycR=y2-y′cR′(4)

解式(4)中兩個(gè)方程組，得到x′0，Δx′，y′c，R′，接著重繪客戶區(qū)圖形，實(shí)現(xiàn)圖形選定區(qū)域縮放。

1.4 查看圖形上某點(diǎn)數(shù)據(jù)

設(shè)鼠標(biāo)指針處坐標(biāo)是(x，y)，將x，y代入式(1)，得到該點(diǎn)的索引I和數(shù)值Y，在此基礎(chǔ)上進(jìn)一步采用操作人員偏愛(ài)的方式顯示該數(shù)據(jù)。

2 關(guān)鍵技術(shù)

由以上分析可知，運(yùn)行在Windows中的應(yīng)用程序在接收到操作系統(tǒng)發(fā)送來(lái)的WMPAINT消息后要重繪客戶區(qū)，為了保證圖形顯示的實(shí)時(shí)性，重繪代碼部分的工作量應(yīng)盡可能小，并避免一切不必要的重繪，即重繪時(shí)只需繪制無(wú)效矩形區(qū)域。這就需要準(zhǔn)確計(jì)算需要重繪的與無(wú)效矩形有關(guān)的數(shù)據(jù)索引范圍、坐標(biāo)軸刻度范圍，見(jiàn)圖2。

圖2 確定與無(wú)效矩形相關(guān)的數(shù)據(jù)范圍、坐標(biāo)軸刻度

2.1 確定無(wú)效矩形包含的數(shù)據(jù)索引

設(shè)s1，s2分別是無(wú)效矩形左、右兩邊界的橫坐標(biāo)，處于無(wú)效矩形中待顯示數(shù)據(jù)的索引范圍為iIndexBeg≤I≤iIndexEnd，則計(jì)算iIndexBeg和iIndexEnd的步驟示例如下:

iIndexBeg=minmax0，ints1-x0Δx，N-1;

iTemp=ints2-x0Δx;

if(s2>x0且s2不是整數(shù))

++iTemp;

iIndexEnd=max(min(N-1，iTemp)，0);

在上面的偽代碼中，int是C++語(yǔ)言中的強(qiáng)制數(shù)據(jù)類型轉(zhuǎn)換，例如int(3.2)=3，int(-3.2)=-3，min，max是兩個(gè)宏，用以返回計(jì)算兩個(gè)數(shù)中的最小、最大值。一旦確定數(shù)據(jù)索引范圍后，即可繪制圖形:

if (iIndexBeg

{//繪制該部分圖形}

2.2 確定無(wú)效矩形包含的ox軸刻度

假定x0處的刻度線索引為0，對(duì)于小于x0的數(shù)據(jù)，規(guī)定其刻度索引為負(fù)，對(duì)于大于x0的數(shù)據(jù)，刻度索引則為正。假定ox軸上各刻度線均勻分布且固定。設(shè)兩相鄰刻度線間水平像素?cái)?shù)為Δpx，無(wú)效矩形包含的刻度索引范圍為[k1， k2]，則確定k1，k2的偽代碼示例如下:

k1=ints1-x0Δpx;k2=ints2-x0Δpx;

if (s1>x0且s1不是整數(shù))

++k1;

if (s2

一旦確定刻度線索引范圍后，即可繪制ox軸刻度線，見(jiàn)圖2。

if (k1≤k2)

{//繪制ox軸刻度線}

2.3 確定無(wú)效矩形包含的oy軸刻度

規(guī)定oy軸刻度線索引是個(gè)整數(shù)，且yc處刻度線索引為0，小于yc的刻度線索引為負(fù)，大于yc的刻度線索引為正。刻度線在y軸上均勻分布且位置固定，設(shè)兩相鄰刻度線間豎直距離為Δpy，s1，s2分別表示無(wú)效矩形上、下兩邊界的縱坐標(biāo)。無(wú)效矩形包含的刻度索引范圍為[m1， m2]，則確定m1，m2的偽代碼示例如下:

m1=ints1-ycΔpy;m2=ints2-ycΔpy;

if (s1>yc且s1不是整數(shù))

++m1;

if (s2

if (m1≤m2)

{//繪制oy軸刻度線}

2.4 消除圖形閃爍

以上已對(duì)繪制無(wú)效矩形的算法以及關(guān)鍵技術(shù)做了介紹。此外在實(shí)時(shí)操作圖形過(guò)程中，為了避免圖形閃爍，增加圖形動(dòng)感，還需先在內(nèi)存DC(Device Context，設(shè)備上下文)上作圖，然后使用Windows API函數(shù)BitBlt一次性拷貝到客戶區(qū)中。

3 性能評(píng)估

為了對(duì)本文提出的高效實(shí)時(shí)圖形重繪算法進(jìn)行性能評(píng)估，利用Visual C++ 6.0集成開(kāi)發(fā)工具開(kāi)發(fā)一個(gè)實(shí)時(shí)圖形顯示程序，軟件項(xiàng)目類型取MDI，在視圖類的WMPAINT，WMLBUTTONDOWN，WMLBUTTONUP，WMMOUSEMOVE[9] 等消息處理函數(shù)中實(shí)現(xiàn)本文算法。圖形數(shù)據(jù)采用軟件仿真產(chǎn)生。運(yùn)行應(yīng)用程序，并以測(cè)試圖形水平平移功能為例進(jìn)行功能檢驗(yàn)。作為對(duì)比，將同批數(shù)據(jù)使用Matlab Plot函數(shù)進(jìn)行顯示[10]，然后做水平平移功能測(cè)試。

表 1中給出水平移動(dòng)包含不同數(shù)據(jù)量的圖形時(shí)，使用Matlab Plot函數(shù)(見(jiàn)圖 3)與使用本文算法(見(jiàn)圖1)得到的平均響應(yīng)時(shí)間。實(shí)驗(yàn)時(shí)對(duì)不同大小的N，每種方法都進(jìn)行20次，然后取其平均值作為最終測(cè)試結(jié)果。本文介紹算法的運(yùn)行硬件環(huán)境為Pentium 4 2.67 GHz CPU，2 GB內(nèi)存，操作系統(tǒng)為Windows XP Professional。

表1 平均響應(yīng)時(shí)間對(duì)比(基于20次實(shí)現(xiàn))

N平均響應(yīng)時(shí)間 /s

Matlab本文算法

1 0000.370.10

10 0000.710.10

100 0001.170.10

1 000 0002.420.11

10 000 00029.600.13

從表1中可以看出，對(duì)于Matlab Plot函數(shù)，當(dāng)數(shù)據(jù)量N大于1 000 000時(shí)，平均響應(yīng)時(shí)間急劇上升，從2.42 s迅速增大到29.60 s。作為對(duì)比，本文算法平均響應(yīng)時(shí)間約為0.11 s，而且響應(yīng)時(shí)間與N依賴關(guān)系較弱。這與前面的分析是一致的，因?yàn)闊o(wú)論N有多大，本文算法只重繪處于客戶區(qū)無(wú)效矩形內(nèi)的數(shù)據(jù)，因此大大減少了圖形重繪工作量，提高了響應(yīng)時(shí)間。

圖3 利用MatlabPlot函數(shù)水平移動(dòng)圖形

4 結(jié) 語(yǔ)

本文提出Windows下應(yīng)用程序客戶區(qū)中圖形高效繪制的基本原理，以及實(shí)現(xiàn)圖形水平平移、豎直平移、自由平移、水平縮放、豎直縮放、自由縮放的關(guān)鍵技術(shù)。基于無(wú)效矩形確定需要繪制的數(shù)據(jù)和坐標(biāo)軸范圍，可避免大量不必要的重繪工作，是實(shí)現(xiàn)圖形高效、快速繪制的關(guān)鍵。利用內(nèi)存DC作圖，可避免圖形閃爍，增強(qiáng)圖形效果。在性能評(píng)估方面，以水平移動(dòng)圖形為例與Matlab Plot函數(shù)進(jìn)行功能比較，給出仿真結(jié)果。實(shí)驗(yàn)表明，本文提出的圖形重繪算法執(zhí)行速度遠(yuǎn)遠(yuǎn)快于Matlab Plot函數(shù)，無(wú)論對(duì)圖形平移或者縮放還是其他操作，都具有操作流暢的特點(diǎn)，而且數(shù)據(jù)量越大(大于106)，本文算法的優(yōu)點(diǎn)越明顯，這說(shuō)明本文提出的重繪算法具有實(shí)時(shí)、高效的特點(diǎn)，可用于實(shí)時(shí)系統(tǒng)中。

參考文獻(xiàn)

[1]劉麗娟.用Visual C++實(shí)現(xiàn)工業(yè)數(shù)據(jù)監(jiān)控系統(tǒng)研究[J].微計(jì)算機(jī)信息，2008，24(9):247-249.

[2]趙素林.利用多線程實(shí)現(xiàn)串口數(shù)據(jù)的實(shí)時(shí)圖形化顯示[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(6):124-126.

[3]徐大誠(chéng)，邵雷，李培光.基于USB 2.0的數(shù)字圖像視頻流的實(shí)時(shí)捕捉與顯示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2008，25(9):133-135.

[4]鄧福偉，劉振興，周恒.多通道數(shù)據(jù)采集系統(tǒng)的設(shè)計(jì)[J].微計(jì)算機(jī)信息，2008，24(1):148-150.

[5]徐學(xué)禹，楊晰紅.基于VisualFoxPro9.0數(shù)據(jù)動(dòng)態(tài)圖形顯示的研究[J].機(jī)械設(shè)計(jì)與制造，2008(7):194-195.

[6]PROSISE Jeff.MFC Windows程序設(shè)計(jì)[M].北京:清華大學(xué)出版社，2003.

[7]PETZOLD Charles.Windows程序設(shè)計(jì)[M].北京:北京大學(xué)出版社，2004.

[8]KRUGLINSKI David J.Visual C++技術(shù)內(nèi)幕[M].北京:清華大學(xué)出版社，2003.

[9]Microsoft Corporation. The October 2001 MSDN Library[DB/OL]. [2010-05-25]. http://www.en.wikipedia.org/wiki/MSDN-Library.

[10]MathWorks. Matlab the language of technical computing[DB/OL]. [2008-06-30]. http://www.ebookee.net.