算法演示系統(tǒng)設計與實現(xiàn)

隋雪潔　楊偉

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

關鍵詞：算法演示；可視化教學；計算機圖形學

DOIDOI：10.11907/rjdk.151497

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-7800（2015）007-0142-03

基金項目基金項目：

簡介簡介：隋雪潔（1991-），女，山東威海人，山東科技大學信息科學與工程學院碩士研究生，研究方向為CAD與圖形圖像處理；楊偉（1987-），男，山東濰坊人，天津航天中為數據系統(tǒng)科技有限公司設計師 ，研究方向為電力電子技術。

0 引言

《計算機圖形學》是圖形圖像處理領域的一門基礎課程，也是計算機科學中最活躍的學科分支之一，近幾年發(fā)展迅速，在CAD設計、廣告設計、娛樂影視、計算機動畫、虛擬現(xiàn)實等許多領域都有應用，高校幾乎都開設了這一課程。

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

1 開發(fā)環(huán)境簡介

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

2 演示系統(tǒng)設計

2.1 系統(tǒng)綜述

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

采用徹底的面向對象技術，將每種算法放在一個類中，在對應類中定義算法所需的參數和函數，不僅使已有算法有良好的組織結構，還利于新算法的加入，其優(yōu)點如下：①可擴展性；②內容豐富，涵蓋知識面廣；③操作界面簡潔，有良好的可交互性；④真正實現(xiàn)可視化教學，在運行界面動態(tài)展示算法效果。

2.2 功能設計

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

2.3 流程設計

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

圖1 系統(tǒng)流程

2.4 算法設計

以多邊形填充3種不同算法為例，闡述算法設計思想。

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

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

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

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

圖2 多邊形填充流程

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

3.1 系統(tǒng)類

本系統(tǒng)數據存儲在CStudyDoc類文檔中，結果顯示在CStudyView類中，下面對幾大重要類作簡要說明：

CStudyFrame是程序主框架；

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

CStudyDoc是文檔類，主要負責維護和管理程序數據；

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

3.2 運行界面

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

圖3 系統(tǒng)運行

3.3 總體實現(xiàn)

3.3.1 類、數據、函數（以多邊形填充為例）

頭文件中添加3個類，分別為桶結點類Bucket、邊表類Edge和棧結點類Stack，在StudyView.h文件中包含它們，因為坐標系中的像素都為整數，因此定義帶參數的宏#define ROUND（a） int（a+0.5），繪圖時可對像素點的計算結果四舍五入。

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

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

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

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

多邊形填充函數void Fill（）；

構造桶結點函數void MakeBucket（）；

建立邊表函數void Et（）；

將新邊插入邊表函數void Add（Edge *）；

對已產生的邊表排序void Order（）；

將結點壓入堆棧void Push（CPoint p）；

將結點從棧中彈出Stack *Pop（）。

3.3.2 調色板

填充顏色的選擇是直接調用系統(tǒng)調色板，運行界面已有定義的顏色模板菜單，在類向導StudyView中找到它的ID，雙擊即可自動生成消息響應函數OnFillcolor（），在該函數中添加以下代碼：

OnFillcolor（）；

CColorDialog ccd（FillColor）；

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

FillColor=ccd.GetColor（）

3.3.3 雙緩沖技術

傳統(tǒng)的繪圖方式是單緩沖，圖形首先繪制在內存緩沖區(qū)，然后由GDI自動將它拷貝到顯存，刷新產生屏幕閃爍，視覺效果很差。本系統(tǒng)采用雙緩沖技術，在內存中添加一個后備緩沖區(qū)，繪圖實質上在后備緩沖區(qū)進行，把后備緩沖區(qū)已繪制好的圖形拷到前面緩沖區(qū)，再由GDI將它拷貝到顯存，這樣就避免了Windows GDI因為不斷刷新而形成的屏幕閃爍問題。實現(xiàn)過程為：

首先添加響應函數OnEraseBkgnd（CDC* pDC）屏蔽背景刷新，然后在Ondraw中進行如下操作：

定義一個位圖對象：

CBitmap？bitmap，MemBitmap；

CDC Mycdc；

bitmap.LoadBitmap（IDB_BITMAP1）；

BITMAP bmp；

bitmap.GetBitmap（&bmp）；

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

Mycdc.CreateCompatibleDC（NULL）；

建立位圖：

MemBitmap.CreateCompatibleBitmap（pDC，260，260）；

將位圖選入到內存設備描述表，將圖形畫到指定的位圖：

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

Mycdc.CreateCompatibleDC（pDC）；

Mycdc.SelectObject（&bitmap）

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

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

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

圖4 種子填充算法測試 圖5 有效邊表填充測試

圖6 邊緣填充測試

5 結語

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

參考文獻：

[1] 孫家廣，胡事民.計算機圖形學基礎教程[M].北京：清華大學出版社，2009.

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

[3] 張玉新，張月清，卜治國，等.計算機圖形學算法可視化教學研究與實現(xiàn)[J].河北農業(yè)大學學報，2009（5）：237-239

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

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

[6] 孔令德.計算機圖形學實踐教學資源庫的設計與建設[J].計算機教育，2013（13）：87-97.

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

[8] 唐榮錫.計算機圖形學教程[M].北京：科學出版社，2000.

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

[10] 唐澤圣.計算機圖形學基礎[M].北京：清華大學出版社，2000.

（責任編輯：杜能鋼）