算法演示系统设计与实现

隋雪洁　杨伟

摘 要：计算机图形学的主要内容是研究图像的生成和算法处理，该课程最大的难点在于算法理解。对应《计算机图形学》课程教材，设计开发了一套算法演示系统，通过人机交互和算法的动态演示，实现可视化教学，增强了学生的理解力。

关键词：算法演示；可视化教学；计算机图形学

DOIDOI：10.11907/rjdk.151497

中图分类号：TP319 文献标识码：A 文章编号：1672-7800（2015）007-0142-03

基金项目基金项目：

简介简介：隋雪洁（1991-），女，山东威海人，山东科技大学信息科学与工程学院硕士研究生，研究方向为CAD与图形图像处理；杨伟（1987-），男，山东潍坊人，天津航天中为数据系统科技有限公司设计师 ，研究方向为电力电子技术。

0 引言

《计算机图形学》是图形图像处理领域的一门基础课程，也是计算机科学中最活跃的学科分支之一，近几年发展迅速，在CAD设计、广告设计、娱乐影视、计算机动画、虚拟现实等许多领域都有应用，高校几乎都开设了这一课程。

计算机图形学知识是纯理论知识，教材对于算法的阐述也只是思想和静态代码，学生难以想象出算法的执行效果，极易感到枯燥乏味，失去学习积极性。本文根据《计算机图形学》教材，采用面向对象技术，着力于14种图形学算法的原理阐述与设计实现，将算法图形可视化，以提高《计算机图形学》课程的教学效果。

1 开发环境简介

本系统选用VS2010作为开发设计平台。VS2010是目前最流行的Windows平台应用程序开发环境，MFC是一个C++类库，它封装了许多Windows API函数，当在项目中新建一个MFC工程时，开发环境会自动产生许多文件，开发者可以专心研究程序的逻辑。

2 演示系统设计

2.1 系统综述

传统的算法开发几乎都采用Opengl库。Opengl是一个功能强大、调用方便的底层图形库，它将简单的图形生成算法封装好，虽然直接调用生成的演示效果与底层VC++编写无异，但是不利于算法掌握。本教学演示系统采用C++编写开发，学生可以展开代码与图形对照，对算法的理解更加深刻，以提高编程能力。

采用彻底的面向对象技术，将每种算法放在一个类中，在对应类中定义算法所需的参数和函数，不仅使已有算法有良好的组织结构，还利于新算法的加入，其优点如下：①可扩展性；②内容丰富，涵盖知识面广；③操作界面简洁，有良好的可交互性；④真正实现可视化教学，在运行界面动态展示算法效果。

2.2 功能设计

本算法演示系统与教材对应，开发了14种算法，主要包括：直线的生成算法与直线的反走样算法；椭圆的生成与圆的生成算法；二维与三维图形的变换算法，包括旋转、平移、切错、缩放；多边形的3种不同填充算法；Bezier曲线与B样条曲线生成算法；双三次Bezier曲面与双三次B样条曲面生成算法；立方体纹理映射。

2.3 流程设计

教学演示系统旨在实现算法的可视化。作为辅助学习系统，必须有简洁的用户界面，并实现人机交互。采用菜单项和弹出对话框方式，用户既可以选择不同的算法进行演示，也可在对话框中输入不同的参数，通过对参数的修改，观察屏幕图形的变化，加深对算法的理解，图1为系统设计流程。

图1 系统流程

2.4 算法设计

以多边形填充3种不同算法为例，阐述算法设计思想。

边缘填充算法涉及到2种颜色：背景色和填充色。找到多边形每一条边与扫描线的交点，以交点为边界分为左右两部分，填充只需将交点右侧像素点的颜色取反即可（右侧延伸到多边形的外接矩形）。当多边形所有边循环一遍后，填充即完成。

有效边填充算法：首先找到多边形纵坐标的最小值与最大值，以此确定扫描线范围，扫描线从多边形最低点向上移动，找到每一条扫描线与多边形各边的交点，算出交点横坐标，并以横坐标递增的次序排序，从而确定填充区间，填充该区间内的像素点即可。此外，为了增加可观性，每一条填充完毕时设定休眠时间。

种子填充算法：首先用鼠标在填充图形内部任意区域选取种子结点，然后搜索上下左右像素点，由内向外进行指定点的填充，直到遇到边界位置。本算法采用进栈出栈思想，可有效提高填充效率。

三种算法流程如图2所示。

图2 多边形填充流程

3 演示系统实现

3.1 系统类

本系统数据存储在CStudyDoc类文档中，结果显示在CStudyView类中，下面对几大重要类作简要说明：

CStudyFrame是程序主框架；

CStudyApp表示开发程序的主线程；

CStudyDoc是文档类，主要负责维护和管理程序数据；

CStudyView表示文档数据，也是用户操作的主要界面。

3.2 运行界面

本系统界面分为3部分：菜单项、工具条和绘图区域。菜单项有快捷方式和下拉子菜单，在资源视图Menu下的IDR_MAINFRAME中进行设计；工具条在Toolbar下的IDR_MAINFRAME中，工具条的ID与子菜单的ID相对应；在资源视图中添加Dialog即可产生对话框视图，同时生成一个对话框类，可以在内部进行控件的编辑与操作，界面如图3所示。

图3 系统运行

3.3 总体实现

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；分别为调色板、多边形定义、有效边表结点定义、桶结点的初始节点和当前结点定义。

消息响应函数在StudyView.h中定义，在StudyView.cpp具体实现，组织结构清晰，多边形填充涉及到的成员函数主要包括：

获取屏幕最大宽度void MaxX（）；

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

多边形填充函数void Fill（）；

构造桶结点函数void MakeBucket（）；

建立边表函数void Et（）；

将新边插入边表函数void Add（Edge *）；

对已产生的边表排序void Order（）；

将结点压入堆栈void Push（CPoint p）；

将结点从栈中弹出Stack *Pop（）。

3.3.2 调色板

填充颜色的选择是直接调用系统调色板，运行界面已有定义的颜色模板菜单，在类向导StudyView中找到它的ID，双击即可自动生成消息响应函数OnFillcolor（），在该函数中添加以下代码：

OnFillcolor（）；

CColorDialog ccd（FillColor）；

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

FillColor=ccd.GetColor（）

3.3.3 双缓冲技术

传统的绘图方式是单缓冲，图形首先绘制在内存缓冲区，然后由GDI自动将它拷贝到显存，刷新产生屏幕闪烁，视觉效果很差。本系统采用双缓冲技术，在内存中添加一个后备缓冲区，绘图实质上在后备缓冲区进行，把后备缓冲区已绘制好的图形拷到前面缓冲区，再由GDI将它拷贝到显存，这样就避免了Windows GDI因为不断刷新而形成的屏幕闪烁问题。实现过程为：

首先添加响应函数OnEraseBkgnd（CDC* pDC）屏蔽背景刷新，然后在Ondraw中进行如下操作：

定义一个位图对象：

CBitmap？bitmap，MemBitmap；

CDC Mycdc；

bitmap.LoadBitmap（IDB_BITMAP1）；

BITMAP bmp；

bitmap.GetBitmap（&bmp）；

建立与前端缓冲区兼容的后备缓冲区：

Mycdc.CreateCompatibleDC（NULL）；

建立位图：

MemBitmap.CreateCompatibleBitmap（pDC，260，260）；

将位图选入到内存设备描述表，将图形画到指定的位图：

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

Mycdc.CreateCompatibleDC（pDC）；

Mycdc.SelectObject（&bitmap）

4 演示系统测试

对上述多边形填充算法进行测试，可以清晰观察到不同算法的动态实现过程，在填充过程中做了截图，效果如图4、图5、图6所示。

从图4可以看出，在多边形内部选取了种子结点，按照搜索4个临界点的方式填充，在上方边缘处碰到边界色，放弃填充该像素，再继续搜索；从图5可以明显看出，该算法是按照扫描线一条一条填充的，视图左上方为原点处，横纵坐标分别向右、向下延伸，因此看到的效果是自上而下进行；如图6所示，首先将第一条边的右侧背景色全部置为填充色，然后将第二条边右侧置为填充色，当覆盖到第一条边右侧时，又将填充色置为背景色，以此方式完成整个多边形的填充。

图4 种子填充算法测试 图5 有效边表填充测试

图6 边缘填充测试

5 结语

本教学演示系统操作方便、资源广泛、内容丰富，使《计算机图形学》教材中的算法得以具体实现，将枯燥抽象的算法变成动态形象的动画，能够充分调动学生的学习积极性，提高自主学习能力，提高教师授课效率，对可视化教学具有重要意义。

参考文献：

[1] 孙家广，胡事民.计算机图形学基础教程[M].北京：清华大学出版社，2009.

[2] 刘华勇，张大明，李璐.计算机图形学算法演示系统设计[J].知识经济，2011（17）：96-119.

[3] 张玉新，张月清，卜治国，等.计算机图形学算法可视化教学研究与实现[J].河北农业大学学报，2009（5）：237-239

[4] 吴艳，程鲁玉.基于FlashMX的计算机图形直线生成算法演示系统的设计与实现[J].长春师范学院学报：自然科学版，2013：33-35.

[5] 赵辉煌，魏书堤，陈坚祯，等.基于VC的多线程计算机图形学教学演示系统设计与实现[J].信息系统工程，2014（6）：159-160.

[6] 孔令德.计算机图形学实践教学资源库的设计与建设[J].计算机教育，2013（13）：87-97.

[7] 江玉珍.计算机图形学算法可视化教学演示系统的构建[J].现代计算机，2011（3）：44-46.

[8] 唐荣锡.计算机图形学教程[M].北京：科学出版社，2000.

[9] 杨长强，郑永果，彭延军.计算机图形学教学系统的设计与实现[J].教育信息化，2006（7）：43-44.

[10] 唐泽圣.计算机图形学基础[M].北京：清华大学出版社，2000.

（责任编辑：杜能钢）