网站首页  词典首页

请输入您要查询的论文：

　

标题 算法演示系统设计与实现
范文 隋雪洁　杨伟



摘 要：计算机图形学的主要内容是研究图像的生成和算法处理，该课程最大的难点在于算法理解。对应《计算机图形学》课程教材，设计开发了一套算法演示系统，通过人机交互和算法的动态演示，实现可视化教学，增强了学生的理解力。
关键词：算法演示；可视化教学；计算机图形学
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.
（责任编辑：杜能钢）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/3/15 14:15:16