一種Windows下實時高效圖形繪制算法

摘 要:針對實時系統中對圖形繪制速度的特殊要求，提出一種應用于Windows環境下應用程序客戶區中的高效圖形繪制算法，給出實現圖形水平平移、豎直平移、自由平移、水平縮放、豎直縮放、自由縮放的關鍵技術。該算法基于無效矩形確定圖形中需要繪制的數據和坐標軸范圍，可避免大量不必要的重繪工作，實現圖形高效、快速繪制，保證操作的實時性。利用內存DC繪圖可避免圖形閃爍，增強圖形顯示效果。與Matlab中繪圖函數進行性能比較，證明了提出的圖形繪制算法是有效的。關鍵詞:圖形繪制; 無效矩形; 圖形閃爍; Matlab

中圖分類號:TN911-34; TP3111文獻標識碼:A

文章編號: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 引 言

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

Windows操作系統提供了圖形設備接口(GUI)[6-8]。在Windows操作系統中，當移動某個應用程序窗口的位置，致使窗口原來被遮蓋的部分顯露出來，或者改變窗口大小時，Windows都要向應用程序發送WMPAINT消息，以告知應用程序有一部分客戶區域已變為無效，需要重新繪制，即重繪。這部分需要重繪的區域稱為客戶區無效區域，由于一般是矩形，故又稱無效矩形。通常情況下無效矩形的大小不等于客戶區，所以重繪時沒有必要繪制整個客戶區，只需繪制客戶區中位于無效矩形中的那部分圖形即可，這樣可以顯著提高圖形繪制代碼執行速度，減少繪制工作量，實現實時操作。

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

1 算法描述

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



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 應用程序客戶區圖形繪制示意圖

實時高效繪制圖形算法的總體思想是，當對圖形實施操作時，保持客戶區坐標系和映射模式固定不變，通過改變x0，yc，Δx，R的值并重繪，實現圖形實時變化，具體分析如下:

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

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

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

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

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

當x0，yc，Δx，R中某一個值改變后，及時調用InvalidateRect函數使需要重繪的區域無效，這將驅使Windows操作系統給應用程序發送WMPAINT消息，在該消息響應處理中，利用更新的x0，yc，Δx，R重繪無效區域，達到動態、實時顯示圖形的目的。

1.1 水平方向縮放圖形

對圖形的操作常用鼠標進行，當需要水平縮放圖形時，為增加圖形縮放視覺效果，應使位于鼠標指針處的數據在縮放前后的位置保持不變。設(x，y)是鼠標指針當前位置，(x′，y′)是水平縮放后的位置，則應有:

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

式中:Δx′為已知參數。解方程組可得到x′0，然后重繪客戶區圖形，實現水平縮放。

1.2 豎直方向縮放圖形

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

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

式中:R′是已知參數。解方程組得到y′c，然后重繪客戶區圖形，實現垂直縮放。

1.3 自由縮放圖形

自由縮放是指在按下鼠標鍵后不放開并拖動鼠標，形成一個矩形區域，對該區域中的圖形進行縮放。這樣可以觀察這部分圖形細節。在該縮放模式下，鼠標拖出矩形區域與客戶區當前可見范圍在縮放前后相對應。設(l，t)，(r，b)分別為鼠標選定矩形左上角和右下角坐標，(x1，y1)，(x2，y2)則分別為客戶區左上角和右下角坐標，易知:

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)中兩個方程組，得到x′0，Δx′，y′c，R′，接著重繪客戶區圖形，實現圖形選定區域縮放。

1.4 查看圖形上某點數據

設鼠標指針處坐標是(x，y)，將x，y代入式(1)，得到該點的索引I和數值Y，在此基礎上進一步采用操作人員偏愛的方式顯示該數據。

2 關鍵技術

由以上分析可知，運行在Windows中的應用程序在接收到操作系統發送來的WMPAINT消息后要重繪客戶區，為了保證圖形顯示的實時性，重繪代碼部分的工作量應盡可能小，并避免一切不必要的重繪，即重繪時只需繪制無效矩形區域。這就需要準確計算需要重繪的與無效矩形有關的數據索引范圍、坐標軸刻度范圍，見圖2。

圖2 確定與無效矩形相關的數據范圍、坐標軸刻度

2.1 確定無效矩形包含的數據索引

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

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

iTemp=ints2-x0Δx;

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

++iTemp;

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

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

if (iIndexBeg

{//繪制該部分圖形}

2.2 確定無效矩形包含的ox軸刻度

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

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

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

++k1;

if (s2

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

if (k1≤k2)

{//繪制ox軸刻度線}

2.3 確定無效矩形包含的oy軸刻度

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

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

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

++m1;

if (s2

if (m1≤m2)

{//繪制oy軸刻度線}

2.4 消除圖形閃爍

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

3 性能評估

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

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

表1 平均響應時間對比(基于20次實現)

N平均響應時間 /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中可以看出，對于Matlab Plot函數，當數據量N大于1 000 000時，平均響應時間急劇上升，從2.42 s迅速增大到29.60 s。作為對比，本文算法平均響應時間約為0.11 s，而且響應時間與N依賴關系較弱。這與前面的分析是一致的，因為無論N有多大，本文算法只重繪處于客戶區無效矩形內的數據，因此大大減少了圖形重繪工作量，提高了響應時間。

圖3 利用MatlabPlot函數水平移動圖形

4 結 語

本文提出Windows下應用程序客戶區中圖形高效繪制的基本原理，以及實現圖形水平平移、豎直平移、自由平移、水平縮放、豎直縮放、自由縮放的關鍵技術?；跓o效矩形確定需要繪制的數據和坐標軸范圍，可避免大量不必要的重繪工作，是實現圖形高效、快速繪制的關鍵。利用內存DC作圖，可避免圖形閃爍，增強圖形效果。在性能評估方面，以水平移動圖形為例與Matlab Plot函數進行功能比較，給出仿真結果。實驗表明，本文提出的圖形重繪算法執行速度遠遠快于Matlab Plot函數，無論對圖形平移或者縮放還是其他操作，都具有操作流暢的特點，而且數據量越大(大于106)，本文算法的優點越明顯，這說明本文提出的重繪算法具有實時、高效的特點，可用于實時系統中。

參考文獻

[1]劉麗娟.用Visual C++實現工業數據監控系統研究[J].微計算機信息，2008，24(9):247-249.

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

[3]徐大誠，邵雷，李培光.基于USB 2.0的數字圖像視頻流的實時捕捉與顯示系統的設計與實現[J].計算機應用與軟件，2008，25(9):133-135.

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

[5]徐學禹，楊晰紅.基于VisualFoxPro9.0數據動態圖形顯示的研究[J].機械設計與制造，2008(7):194-195.

[6]PROSISE Jeff.MFC Windows程序設計[M].北京:清華大學出版社，2003.

[7]PETZOLD Charles.Windows程序設計[M].北京:北京大學出版社，2004.

[8]KRUGLINSKI David J.Visual C++技術內幕[M].北京:清華大學出版社，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.