隋雪潔　楊偉

摘 要：計(jì)算機(jī)圖形學(xué)的主要內(nèi)容是研究圖像的生成和算法處理，該課程最大的難點(diǎn)在于算法理解。對(duì)應(yīng)《計(jì)算機(jī)圖形學(xué)》課程教材，設(shè)計(jì)開(kāi)發(fā)了一套算法演示系統(tǒng)，通過(guò)人機(jī)交互和算法的動(dòng)態(tài)演示，實(shí)現(xiàn)可視化教學(xué)，增強(qiáng)了學(xué)生的理解力。

關(guān)鍵詞：算法演示；可視化教學(xué)；計(jì)算機(jī)圖形學(xué)

DOIDOI：10.11907/rjdk.151497

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2015）007-0142-03

基金項(xiàng)目基金項(xiàng)目：

簡(jiǎn)介簡(jiǎn)介：隋雪潔（1991-），女，山東威海人，山東科技大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)镃AD與圖形圖像處理；楊偉（1987-），男，山東濰坊人，天津航天中為數(shù)據(jù)系統(tǒng)科技有限公司設(shè)計(jì)師 ，研究方向?yàn)殡娏﹄娮蛹夹g(shù)。

0 引言

《計(jì)算機(jī)圖形學(xué)》是圖形圖像處理領(lǐng)域的一門(mén)基礎(chǔ)課程，也是計(jì)算機(jī)科學(xué)中最活躍的學(xué)科分支之一，近幾年發(fā)展迅速，在CAD設(shè)計(jì)、廣告設(shè)計(jì)、娛樂(lè)影視、計(jì)算機(jī)動(dòng)畫(huà)、虛擬現(xiàn)實(shí)等許多領(lǐng)域都有應(yīng)用，高校幾乎都開(kāi)設(shè)了這一課程。

計(jì)算機(jī)圖形學(xué)知識(shí)是純理論知識(shí)，教材對(duì)于算法的闡述也只是思想和靜態(tài)代碼，學(xué)生難以想象出算法的執(zhí)行效果，極易感到枯燥乏味，失去學(xué)習(xí)積極性。本文根據(jù)《計(jì)算機(jī)圖形學(xué)》教材，采用面向?qū)ο蠹夹g(shù)，著力于14種圖形學(xué)算法的原理闡述與設(shè)計(jì)實(shí)現(xiàn)，將算法圖形可視化，以提高《計(jì)算機(jī)圖形學(xué)》課程的教學(xué)效果。

1 開(kāi)發(fā)環(huán)境簡(jiǎn)介

本系統(tǒng)選用VS2010作為開(kāi)發(fā)設(shè)計(jì)平臺(tái)。VS2010是目前最流行的Windows平臺(tái)應(yīng)用程序開(kāi)發(fā)環(huán)境，MFC是一個(gè)C++類庫(kù)，它封裝了許多Windows API函數(shù)，當(dāng)在項(xiàng)目中新建一個(gè)MFC工程時(shí)，開(kāi)發(fā)環(huán)境會(huì)自動(dòng)產(chǎn)生許多文件，開(kāi)發(fā)者可以專心研究程序的邏輯。

2 演示系統(tǒng)設(shè)計(jì)

2.1 系統(tǒng)綜述

傳統(tǒng)的算法開(kāi)發(fā)幾乎都采用Opengl庫(kù)。Opengl是一個(gè)功能強(qiáng)大、調(diào)用方便的底層圖形庫(kù)，它將簡(jiǎn)單的圖形生成算法封裝好，雖然直接調(diào)用生成的演示效果與底層VC++編寫(xiě)無(wú)異，但是不利于算法掌握。本教學(xué)演示系統(tǒng)采用C++編寫(xiě)開(kāi)發(fā)，學(xué)生可以展開(kāi)代碼與圖形對(duì)照，對(duì)算法的理解更加深刻，以提高編程能力。

采用徹底的面向?qū)ο蠹夹g(shù)，將每種算法放在一個(gè)類中，在對(duì)應(yīng)類中定義算法所需的參數(shù)和函數(shù)，不僅使已有算法有良好的組織結(jié)構(gòu)，還利于新算法的加入，其優(yōu)點(diǎn)如下：①可擴(kuò)展性；②內(nèi)容豐富，涵蓋知識(shí)面廣；③操作界面簡(jiǎn)潔，有良好的可交互性；④真正實(shí)現(xiàn)可視化教學(xué)，在運(yùn)行界面動(dòng)態(tài)展示算法效果。

2.2 功能設(shè)計(jì)

本算法演示系統(tǒng)與教材對(duì)應(yīng)，開(kāi)發(fā)了14種算法，主要包括：直線的生成算法與直線的反走樣算法；橢圓的生成與圓的生成算法；二維與三維圖形的變換算法，包括旋轉(zhuǎn)、平移、切錯(cuò)、縮放；多邊形的3種不同填充算法；Bezier曲線與B樣條曲線生成算法；雙三次Bezier曲面與雙三次B樣條曲面生成算法；立方體紋理映射。

2.3 流程設(shè)計(jì)

教學(xué)演示系統(tǒng)旨在實(shí)現(xiàn)算法的可視化。作為輔助學(xué)習(xí)系統(tǒng)，必須有簡(jiǎn)潔的用戶界面，并實(shí)現(xiàn)人機(jī)交互。采用菜單項(xiàng)和彈出對(duì)話框方式，用戶既可以選擇不同的算法進(jìn)行演示，也可在對(duì)話框中輸入不同的參數(shù)，通過(guò)對(duì)參數(shù)的修改，觀察屏幕圖形的變化，加深對(duì)算法的理解，圖1為系統(tǒng)設(shè)計(jì)流程。

圖1 系統(tǒng)流程

2.4 算法設(shè)計(jì)

以多邊形填充3種不同算法為例，闡述算法設(shè)計(jì)思想。

邊緣填充算法涉及到2種顏色：背景色和填充色。找到多邊形每一條邊與掃描線的交點(diǎn)，以交點(diǎn)為邊界分為左右兩部分，填充只需將交點(diǎn)右側(cè)像素點(diǎn)的顏色取反即可（右側(cè)延伸到多邊形的外接矩形）。當(dāng)多邊形所有邊循環(huán)一遍后，填充即完成。

有效邊填充算法：首先找到多邊形縱坐標(biāo)的最小值與最大值，以此確定掃描線范圍，掃描線從多邊形最低點(diǎn)向上移動(dòng)，找到每一條掃描線與多邊形各邊的交點(diǎn)，算出交點(diǎn)橫坐標(biāo)，并以橫坐標(biāo)遞增的次序排序，從而確定填充區(qū)間，填充該區(qū)間內(nèi)的像素點(diǎn)即可。此外，為了增加可觀性，每一條填充完畢時(shí)設(shè)定休眠時(shí)間。

種子填充算法：首先用鼠標(biāo)在填充圖形內(nèi)部任意區(qū)域選取種子結(jié)點(diǎn)，然后搜索上下左右像素點(diǎn)，由內(nèi)向外進(jìn)行指定點(diǎn)的填充，直到遇到邊界位置。本算法采用進(jìn)棧出棧思想，可有效提高填充效率。

三種算法流程如圖2所示。

圖2 多邊形填充流程

3 演示系統(tǒng)實(shí)現(xiàn)

3.1 系統(tǒng)類

本系統(tǒng)數(shù)據(jù)存儲(chǔ)在CStudyDoc類文檔中，結(jié)果顯示在CStudyView類中，下面對(duì)幾大重要類作簡(jiǎn)要說(shuō)明：

CStudyFrame是程序主框架；

CStudyApp表示開(kāi)發(fā)程序的主線程；

CStudyDoc是文檔類，主要負(fù)責(zé)維護(hù)和管理程序數(shù)據(jù)；

CStudyView表示文檔數(shù)據(jù)，也是用戶操作的主要界面。

3.2 運(yùn)行界面

本系統(tǒng)界面分為3部分：菜單項(xiàng)、工具條和繪圖區(qū)域。菜單項(xiàng)有快捷方式和下拉子菜單，在資源視圖Menu下的IDR_MAINFRAME中進(jìn)行設(shè)計(jì)；工具條在Toolbar下的IDR_MAINFRAME中，工具條的ID與子菜單的ID相對(duì)應(yīng)；在資源視圖中添加Dialog即可產(chǎn)生對(duì)話框視圖，同時(shí)生成一個(gè)對(duì)話框類，可以在內(nèi)部進(jìn)行控件的編輯與操作，界面如圖3所示。

圖3 系統(tǒng)運(yùn)行

3.3 總體實(shí)現(xiàn)

3.3.1 類、數(shù)據(jù)、函數(shù)（以多邊形填充為例）

頭文件中添加3個(gè)類，分別為桶結(jié)點(diǎn)類Bucket、邊表類Edge和棧結(jié)點(diǎn)類Stack，在StudyView.h文件中包含它們，因?yàn)樽鴺?biāo)系中的像素都為整數(shù)，因此定義帶參數(shù)的宏#define ROUND（a） int（a+0.5），繪圖時(shí)可對(duì)像素點(diǎn)的計(jì)算結(jié)果四舍五入。

StudyView.h的公有數(shù)據(jù)成員包括COLORREF ChooseColor；CPoint Point[7]；Edge A[Num]，*FirstA，*NowA，*T1，*T2；Bucket *FirstB，*NowB；分別為調(diào)色板、多邊形定義、有效邊表結(jié)點(diǎn)定義、桶結(jié)點(diǎn)的初始節(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)定義。

消息響應(yīng)函數(shù)在StudyView.h中定義，在StudyView.cpp具體實(shí)現(xiàn)，組織結(jié)構(gòu)清晰，多邊形填充涉及到的成員函數(shù)主要包括：

獲取屏幕最大寬度void MaxX（）；

獲取屏幕最大高度void MaxY（）；

多邊形填充函數(shù)void Fill（）；

構(gòu)造桶結(jié)點(diǎn)函數(shù)void MakeBucket（）；

建立邊表函數(shù)void Et（）；

將新邊插入邊表函數(shù)void Add（Edge *）；

對(duì)已產(chǎn)生的邊表排序void Order（）；

將結(jié)點(diǎn)壓入堆棧void Push（CPoint p）；

將結(jié)點(diǎn)從棧中彈出Stack *Pop（）。

3.3.2 調(diào)色板

填充顏色的選擇是直接調(diào)用系統(tǒng)調(diào)色板，運(yùn)行界面已有定義的顏色模板菜單，在類向?qū)tudyView中找到它的ID，雙擊即可自動(dòng)生成消息響應(yīng)函數(shù)OnFillcolor（），在該函數(shù)中添加以下代碼：

OnFillcolor（）；

CColorDialog ccd（FillColor）；

if（ccd.DoModal（）==IDOK）；

FillColor=ccd.GetColor（）

3.3.3 雙緩沖技術(shù)

傳統(tǒng)的繪圖方式是單緩沖，圖形首先繪制在內(nèi)存緩沖區(qū)，然后由GDI自動(dòng)將它拷貝到顯存，刷新產(chǎn)生屏幕閃爍，視覺(jué)效果很差。本系統(tǒng)采用雙緩沖技術(shù)，在內(nèi)存中添加一個(gè)后備緩沖區(qū)，繪圖實(shí)質(zhì)上在后備緩沖區(qū)進(jìn)行，把后備緩沖區(qū)已繪制好的圖形拷到前面緩沖區(qū)，再由GDI將它拷貝到顯存，這樣就避免了Windows GDI因?yàn)椴粩嗨⑿露纬傻钠聊婚W爍問(wèn)題。實(shí)現(xiàn)過(guò)程為：

首先添加響應(yīng)函數(shù)OnEraseBkgnd（CDC* pDC）屏蔽背景刷新，然后在Ondraw中進(jìn)行如下操作：

定義一個(gè)位圖對(duì)象：

CBitmap？bitmap，MemBitmap；

CDC Mycdc；

bitmap.LoadBitmap（IDB_BITMAP1）；

BITMAP bmp；

bitmap.GetBitmap（&bmp）；

建立與前端緩沖區(qū)兼容的后備緩沖區(qū)：

Mycdc.CreateCompatibleDC（NULL）；

建立位圖：

MemBitmap.CreateCompatibleBitmap（pDC，260，260）；

將位圖選入到內(nèi)存設(shè)備描述表，將圖形畫(huà)到指定的位圖：

CBitmap *pOldBit=MemDC.SelectObject（&MemBitmap）；

Mycdc.CreateCompatibleDC（pDC）；

Mycdc.SelectObject（&bitmap）

4 演示系統(tǒng)測(cè)試

對(duì)上述多邊形填充算法進(jìn)行測(cè)試，可以清晰觀察到不同算法的動(dòng)態(tài)實(shí)現(xiàn)過(guò)程，在填充過(guò)程中做了截圖，效果如圖4、圖5、圖6所示。

從圖4可以看出，在多邊形內(nèi)部選取了種子結(jié)點(diǎn)，按照搜索4個(gè)臨界點(diǎn)的方式填充，在上方邊緣處碰到邊界色，放棄填充該像素，再繼續(xù)搜索；從圖5可以明顯看出，該算法是按照掃描線一條一條填充的，視圖左上方為原點(diǎn)處，橫縱坐標(biāo)分別向右、向下延伸，因此看到的效果是自上而下進(jìn)行；如圖6所示，首先將第一條邊的右側(cè)背景色全部置為填充色，然后將第二條邊右側(cè)置為填充色，當(dāng)覆蓋到第一條邊右側(cè)時(shí)，又將填充色置為背景色，以此方式完成整個(gè)多邊形的填充。

圖4 種子填充算法測(cè)試 圖5 有效邊表填充測(cè)試

圖6 邊緣填充測(cè)試

5 結(jié)語(yǔ)

本教學(xué)演示系統(tǒng)操作方便、資源廣泛、內(nèi)容豐富，使《計(jì)算機(jī)圖形學(xué)》教材中的算法得以具體實(shí)現(xiàn)，將枯燥抽象的算法變成動(dòng)態(tài)形象的動(dòng)畫(huà)，能夠充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性，提高自主學(xué)習(xí)能力，提高教師授課效率，對(duì)可視化教學(xué)具有重要意義。

參考文獻(xiàn)：

[1] 孫家廣，胡事民.計(jì)算機(jī)圖形學(xué)基礎(chǔ)教程[M].北京：清華大學(xué)出版社，2009.

[2] 劉華勇，張大明，李璐.計(jì)算機(jī)圖形學(xué)算法演示系統(tǒng)設(shè)計(jì)[J].知識(shí)經(jīng)濟(jì)，2011（17）：96-119.

[3] 張玉新，張?jiān)虑澹分螄?guó)，等.計(jì)算機(jī)圖形學(xué)算法可視化教學(xué)研究與實(shí)現(xiàn)[J].河北農(nóng)業(yè)大學(xué)學(xué)報(bào)，2009（5）：237-239

[4] 吳艷，程魯玉.基于FlashMX的計(jì)算機(jī)圖形直線生成算法演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].長(zhǎng)春師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2013：33-35.

[5] 趙輝煌，魏書(shū)堤，陳堅(jiān)禎，等.基于VC的多線程計(jì)算機(jī)圖形學(xué)教學(xué)演示系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].信息系統(tǒng)工程，2014（6）：159-160.

[6] 孔令德.計(jì)算機(jī)圖形學(xué)實(shí)踐教學(xué)資源庫(kù)的設(shè)計(jì)與建設(shè)[J].計(jì)算機(jī)教育，2013（13）：87-97.

[7] 江玉珍.計(jì)算機(jī)圖形學(xué)算法可視化教學(xué)演示系統(tǒng)的構(gòu)建[J].現(xiàn)代計(jì)算機(jī)，2011（3）：44-46.

[8] 唐榮錫.計(jì)算機(jī)圖形學(xué)教程[M].北京：科學(xué)出版社，2000.

[9] 楊長(zhǎng)強(qiáng)，鄭永果，彭延軍.計(jì)算機(jī)圖形學(xué)教學(xué)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].教育信息化，2006（7）：43-44.

[10] 唐澤圣.計(jì)算機(jī)圖形學(xué)基礎(chǔ)[M].北京：清華大學(xué)出版社，2000.

（責(zé)任編輯：杜能鋼）