标题 | 算法演示系统设计与实现 |
范文 | 隋雪洁 杨伟![]() ![]() ![]() 摘 要:计算机图形学的主要内容是研究图像的生成和算法处理,该课程最大的难点在于算法理解。对应《计算机图形学》课程教材,设计开发了一套算法演示系统,通过人机交互和算法的动态演示,实现可视化教学,增强了学生的理解力。 关键词:算法演示;可视化教学;计算机图形学 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下载服务。