光栅图形学教学演示系统的设计与实现

1、光栅图形学教学演示系统的设计与实现学 院专 业班 级学 号姓 名指导教师负责教师摘 要计算机图形学是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。由于计算机图形学技术本身的长足进步及其应用的日益广泛，计算机图形学已成为计算机科学技术与其他应用学科之间的一个桥梁，也已成为许多本科生专业的必修课之一。本文实现了一个光栅图形学教学演示系统，该系统在windows xp平台下实现，采用visual c+ 6.0作为编程工具。本文对光栅图形学教学演示系统进行了详细分析，确定了相应的结构和主要功能，以及实际开发中所采取的技术。教学演示系统能够形象的展示各种算法的工作过程，如直线扫描转

2、换算法、圆弧的扫描转换算法、多边形的扫描转换、区域填充、直线和多边形的裁减算法以及曲线、曲面的生成算法等。该系统操作简洁，能够在模拟的光栅区域上按照算法的原理将图形的光栅化过程展示出来，便于老师在教学中更形象的展示各种算法的工作过程，也便于学生在学习过程中能够更好的理解基本图形生成算法。同时，本文也介绍了系统开发设计的全过程，对算法原理做了详细的阐述，也对系统的功能进行了测试。本系统实现了大部分的基本图形生成算法，可以应用于计算机图形学的教学中，以达到提高教学质量的目的。关键词：计算机图形学；光栅；教学；基本图形生成算法design and implementation of raster g

3、raphics teaching demonstration system abstractcomputer graphics is a science which translates two-dimensional or three-dimensional computer graphics into the display grid in mathematical algorithm. as the remarkable progress and the widespread application of computer graphics, it has become a bridge

4、 between the computer science and other application disciplines, and it is one of the required courses of many undergraduate professionals.this paper implements a raster graphics teaching demonstration system, which under the windows xp platform and visual c + + 6.0. this paper analyzes the system i

5、n detail, and determines the appropriate structure and main functions, as well as the technology adopted in actual development. the teaching demonstration system can show the visual working process of various algorithms, such as the line scan conversion algorithm, the arc scan conversion algorithms,

6、 the polygon scan conversion algorithms, the area fill algorithms, the line and polygon reduction algorithm and curve, surface generation algorithm. the system operation is simple and can display the raster process in the simulate raster area in accordance with the principles of these algorithms, wh

7、ich not only can more vivid display the working process of various algorithms in teaching, but also could facilitate students to better understand the basic pattern generation algorithm in the learning process. meanwhile, this paper describes the whole process of system development and design. it do

8、es a detail expression of the algorithm principle and tests the function of the system. the system implements most of the basic pattern generation algorithms, and it could be applied in the teaching of computer graphics to improve the quality of teaching.keywords: computer graphics; raster; teaching

9、; basic pattern generation algorithm目 录1 绪 论11.1 计算机图形学的重要性11.2 计算机图形学的发展情况21.2.1 autocad概述21.2.2 计算机美术与设计31.2.3 计算机动画艺术41.2.4 科学计算可视化41.2.5 虚拟现实51.3 课题的研究意义62 需求分析72.1 光栅图形学概述72.2 任务概述72.3 任务分析72.3.1 直线扫面转换算法82.3.2 圆弧的扫描转换算法82.3.3 多边形的扫描转换与区域填充82.3.4 直线和多边形的裁减算法92.3.5 曲线与曲面的生成算法93 系统详细设计103.1 总体设计1

10、03.2 界面设计113.2.1 窗口的设计123.2.2 菜单的设计123.3 直线模块设计133.3.1 数值微分（dda）法133.3.2 中点画线法143.3.3 bresenham算法163.4 圆形模块设计183.4.1 中点画圆法183.5 区域填充模块设计193.5.1 区域填充的递归算法和扫描线算法203.6 裁剪图形模块设计223.6.1 直线段裁剪223.6.2 多边形裁剪253.7 曲线曲面模块设计263.7.1 bezier曲线263.7.2 bezier曲面283.8 小结294 系统实现和测试304.1 实验环境304.2 运行结果30参考文献34致 谢351 绪

11、 论随着网络和多媒体技术的发展和应用，计算机图形学成为当代几乎所有科学和工程技术领域用来加强信息理解和传递的技术和工具。计算机图形学的硬件和软件应用本身已发展成为一个巨大的产业，有着广泛的发展前景，必将在人们的生活中起着越来越重要的作用。因此，计算机图形学的应用是重要的研究内容。1.1 计算机图形学的重要性计算机图形学是利用计算机研究图形的表示、生成、处理，显示的一门重要的计算机学科分支。经过30多年的发展，计算机图形学已成为计算机科学中最为活跃的分支之一，并得到广泛的应用。1950年，第一台图形显示器作为美国麻省理工学院（mit）旋风一号（whirlwind）计算机的附件诞生。该显示器用一个

12、类似示波器的阴极射线管（crt）来显示一些简单的图形。在整个50年代，只有电子管计算机，用机器语言编程，主要应用于科学计算，为这些计算机配置的图形设备仅具有输出功能。计算机图形学处于准备和酝酿时期，并称之为：“被动式”图形学。1963年，伊凡苏泽兰(ivan sutherland)在麻省理工学院发表了名为画板的博士论文，它标志着计算机图形学的正式诞生。至今已有三十多年的历史。此前的计算机主要是符号处理系统，自从有了计算机图形学，计算机可以部分地表现人的右脑功能了，所以计算机图形学的建立具有重要的意义。计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面

13、造型、实体造型、真实感图形计算与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。随着网络和多媒体技术的发展和应用，体现在应用软件中的是一些更具有“现代感”的应用，例如，支持各种常用图形、raw原始图片、flash动画的快速浏览、编辑、保存、导入、导出，甚至还可以提供一些趣味涂鸦、字符素描之类的应用，以体现人的个性。图形与图像处理是计算机最早应用的领域之一，从简单的图形显示到复杂的图像分析、模式识别，使得图形与图像处理技术不断走向成熟，也涌现出了大量的软件。例如，acdsee、photoshop、coreldraw等，这些软件提供了一般显示、特殊显示、特技处理等

14、大量复杂的功能。图形处理技术得益于图形学的发展，而从目的上可以将图像处理技术分为两类，分别是图像识别技术和图像处理技术。针对图像处理技术，可以是旋转、亮度、对比度、饱和度、rgb调节、调节图像尺寸等属性方面的处理技术和添加文字、图像增强、弱化、水印、特效、镂空等处理方法。甚至为了达到更精微的处理效果，这些软件还使用了图层。随着计算机系统的硬件、软件的迅速发展，计算机已经具有强大的图形处理功能，目前计算机图形学已无所不在，从cad设计到广告设计、从影视娱乐到计算机动画，都使人们感受到计算机图形技术独特的魅力。同时，由于计算机图形学技术本身的长足进步及其应用的日益广泛，计算机图形学已成为计算机科学

15、技术与其他应用学科之间的一个桥梁，也成为许多本科生专业的必修课程之一。1.2 计算机图形学的发展情况计算机促进高科技技术不断发展，计算机图形学成为当代几乎所有科学和工程技术领域用来加强信息理解和传递的技术和工具。近年来，计算机图形学在如下几方面有了长足的进展。1.2.1 autocad概述cad 的发展也显现出智能化的趋势，就目前流行的大多数cad软件来看，主要功能是支持产品的后续阶段一一工程图的绘制和输出，产品设计功能相对薄弱，利用autocad 最常用的功能还是交互式绘图，如果要想进行产品设计，最基本的是要其中的autolisp语言编写程序，有时还要用其他高级语言协助编写，很不方便。而新一

16、代的智能cad系统可以实现从概念设计到结构设计的全过程。例如，德国西门子公司开发的sigraph design软件可以实现如下功能：从一开始就可以用计算机设计草图，不必耗时费力的输入精确的坐标点，能随心所欲的修改，一旦结构确定，给出正确的尺寸即得到满意的图纸；这个软件中具有关系数据结构，当你改变图纸的局部，相关部分自动变化，在一个视图上的修改，其他视图自动修改，甚至改变一个零件图，相关的其它零件图以及装配图的相关部分自动修改：在各个专业领域中，有一些常用件和标准件，因此，希望有一个参数化图库。而sigraph不用编程只需画一遍图就能建成自己的图库；sigraph还可以实现产品设计的动态模拟用于

17、观察设计的装置在实际运行中是否合理等等。智能cad的另一个领域是工程图纸的自动输入与智能识别，随着cad技术的迅速推广应用，各个工厂、设计院都需将成千上万张长期积累下来的设计图纸快速而准确输入计算机，作为新产品开发的技术资料。多年来，cad中普遍采用的图形输入方法是图形数字化仪交互输入和鼠标加键盘的交互输入方法。很难适应工程界大量图纸输入的迫切需要。因此，基于光电扫描仪的图纸自动输入方法已成为国内外cad工作者的努力探索的新课题。但由于工程图的智能识别涉及到计算机的硬件、计算机图形学、模式识别及人工智能等高新技术内容，使得研究工作的难点较大。工程图的自动输入与智能识别是两个密不可分的过程，用扫

18、描仪将手绘图纸输入到计算机后，形成的是点阵图象。cad中只能对矢量图形进行编辑，这就要求将点阵图象转化成矢量图形。而这些工作都让计算机自动完成，这就带来了许多的问题。如图象的智能识别；字符的提取与识别；图形拓扑结构的建立与图形的理解；实用化的后处理方法等等。国家自然科学基金会和863计划基金都在支持这方面的研究，国内外已有一些这方面的软件付诸实用，如美国的rvmaster，德国的vpmax，以及清华大学，东北大学的产品等。但效果都不很理想，还未能达到人们企盼的效果。1.2.2 计算机美术与设计1952年美国的ben laposke用模拟计算机做的波型图电子抽象画预示着电脑美术的开始(比计算机图

19、形学的正式确立还要早)。计算机美术的发展可分为三个阶段：(1)早期探索阶段(19521968年)主创人员大部分为科学家和工程师，作品以平面几何图形为主。1963年美国计算机与自动化杂志开始举办年度“计算机美术比赛”。代表作品：1960年wiuiam ferrter为波音公司制作的人体工程学实验动态模拟，模拟飞行员在飞机中各种情况；1963年kenneth know iton的打印机作品裸体。1967年日本gtg小组的回到方块。(2)中期应用阶段(1968年1983年)以1968年伦敦第一次世界计算机美术大展一“控制论珍宝”为标志，进入世界性研究与应用阶段；计算机与计算机图形技术逐步成熟，一些大

20、学开始设置相关课题，出现了一些cad应用系统和成果，三维造型系统产生并逐渐完善。代表作品：1983年美国ibm研究所richerd voss设计出分形山。(3)应用与普及阶段(1984年现在)以微机和工作站为平台的个人计算机图形系统逐渐走向成熟，大批商业性美术软件面市；以苹果公司的mac机和图形化系统软件为代表的桌面创意系统被广泛接受，cad成为美术设计领域的重要组成部分。代表作品：1990年jefrey shaw的交互图形作品“易读的城市（the legible city）”。计算机设计学包括三个方面：环境设计、视觉传达设计、产品设计。cad对艺术的介入，分三个应用层次：(1)计算机图形作为

21、系统设计手段的一种强化和替代；效果是这个层次的核心(高精度、高速度、高存储)。(2)计算机图形作为新的表现形式和新的形象资源。(3)计算机图形作为一种设计方法和观念。1.2.3 计算机动画艺术计算机动画技术的发展是和许多其它学科的发展密切相关的。计算机图形学、计算机绘画、计算机音乐、计算机辅助设计、电影技术、电视技术、计算机软件和硬件技术等众多学科的最新成果都对计算机动画技术的研究和发展起着十分重要的推动作用50年代到60年代之间，大部分的计算机绘画艺术作品都是在打印机和绘图仪上产生的。一直到60年代后期，才出现利用计算机显示点阵的特性，通过精心地设计图案来进行计算机艺术创造的活动。70年代开

22、始计算机艺术走向繁荣和成熟1973年，在东京索尼公司举办了“届国际计算机艺术展览会”80年代至今，计算机艺术的发展速度远远超出了人们的想象，在代表计算机图形研究最高水平的历届siggraph年会上，精彩的计算机艺术作品层出不穷。另外，在此期间的奥斯卡奖的获奖名单中，采用计算机特技制作电影频频上榜，大有舍我其谁的感觉。在中国，首届计算机艺术研讨会和作品展示活动于1995年在北京举行，它总结了近年来计算机艺术在中国的发展，对未来的工作起到了重要的推动作用。计算机动画的一个重要应用就是制作电影特技，可以说电影特技的发展和计算机动画的发展是相互促进的。我国的计算机动画技术起步较晚。1990年的第11届

23、亚洲运动会上，首次采用了计算机三维动画技术来制作有关的电视节目片头。从那时起，计算机动画技术在国内影视制作方面得到了讯速的发展，继而以3d studio为代表的三维动画微机软什和以photostyler、photoshop等为代表的微机二维平面设计软件的普及，对我国计算机动画技术的应用起到了推波助谰的作用。计算机动画的应用领域十分宽广，除了用来制作影视作品外，在科学研究、视觉模拟、电子游戏、工业设计、教学训练、写真仿真、过程控制、平面绘画、建筑设计等许多方面都有重要应用，如军事战术模拟。1.2.4 科学计算可视化科学计算的可视化是发达国家八十年代后期提出并发展起来的一门新兴技术，它将科学计算过

24、程中及计算结果的数据转换为几何图形及图象信息在屏幕上显示出来并进行交互处理，成为发现和理解科学计算过程中各种现象的有力工具。科学计算可视化将图形生成技术图象理解技术结合在一起，它即可理解送入计算机的图象数据，也可以从复杂的多维数据中产生图形。它涉及到下列相互独立的几个领域：计算机图形学、图象处理、计算机视觉、计算机辅助设计及交互技术等。科学计算可视按其实现的功能来分，可以分为三个档次：(1)结果数据的后处理；(2)结果数据的实时跟踪处理及显示；(3)结果数据的实时显示及交互处理。国外科学计算可视化的现状，(1)分布式虚拟风洞，这是美国国家宇航局(ames)研究中心的研究项目，包括连接到一台超能

25、计算机上的两个虚拟屏幕。(2)phthfinder，这是美国国家超级计算机应用中心(ncsa)的研究项目，是在交互分布环境下研究大气流体的软件。(3)狗心脏ct数据的动态显示，这也是ncsa的研究项目，它利用远程的并行计算资源，用体绘制技术实现ct扫描三维数据场动态显示。(4)燃烧过程动态模型的可视化，这是美国西北大学的研究项目，可以显示发生在非烧热的气体燃烧中复杂的空问瞬态图象。(5)胚胎的可视化，依利诺大学芝加哥分校研制了一个在工作站和超级计算机上实现的可视亿应用软件。科学计算可视化技术在美国的著名国家实验室及大学中已经从研究走向应用，应用范围涉及天体物理、生物学、气象学、空气动力学、数学

26、、医学图象等领域。科学计算可视化的技术水平正在从后处理向实时跟踪和交互控制发展。美国在实现科学计算可视化时，已经将超级计算机、光纤高速网、高性能工作站及虚拟环境四者结合起来，显示了这一领域技术发展的重要方向。就三维数据场的显示算法而言，当数据场分布密集而规则时(如ct扫描数据)多采用体绘制技术，这种算法效果好，但计算费时。对于数据场分布稀疏，或分布不规则的应用领域，如天体物理、气象学多采用构造中间几何图象的方法，这种方法生成图象速度快，较易作到实时交互处理。1.2.5 虚拟现实“虚拟现实”(virbual remity)一词是由美国喷气推动实验室(vpl)的创始人拉尼尔(jaron lanie

27、r)首先提出的，在克鲁格(myren kruege)70年代中早期实验里，被称为“人工现实”(artificial reality)；而在吉布森(william gibson)l984年出版的科幻小说neuremanccr里，又被称为“可控空间”(cyberspaee)。虚拟现实，也育人称之为虚拟环境(virtual environment)是美国国家航空和航天局及军事部门为模拟而开发的一门高新技术，它利用计算机图形产生器，位置跟踪器，多功能传感器和控制器等有效地模拟实际场景和情形，从而能够使观察者产生一种真实的身临其境的感觉虚拟环境由硬件和软件组成。用户界面是计算机系统中人与计算机之间相互通

28、讯的重要组成部分。八十年代以wimp为基础的图形用户界面gud极大地改善了计算机的可用性、可学性和有效性，迅速代替了命令行为代表的字符界面，成为当今计算机用户界面的主流。窗口是虚拟存在的一个屏幕，在屏幕上看到的图形是视口。windows在绘制图形时，并不是把图形直接绘制到屏幕上，而是绘制到特定的映射模式下的逻辑坐标系虚拟的窗口中，然后将这个图形映射到一个视图中，即视口中。而当前的设备（如屏幕，打印机）显示出来的就是该视图的一部分。以用户为中心的系统设计思想，增进人机交互的自然性，提高人机交互的效率和带宽是用户界面的研究方向。于是提出了多通道用户界面的思想。可以这样说人体的表面就是人机界面。虚拟

29、现实显示是关键所在，这不仅要求软件来实现，更主要的是硬件上的实现。计算机图形学中各个领域的发展各有各自的特点，但总起来说是以虚拟现实为导向和目的的。虚拟现实的发展要求必将带动计算机图形学各学科的发展。同样虚拟现实的发展也将依赖于其他学科的发展，计算机图形前景诱人。形势逼人，我国还比较落后，但通过努力还是可以缩短差距的。 1.3 课题的研究意义本题目的目的是设计并实现一个光栅图形学教学演示系统。课题实现基本图形元素如直线、圆、曲线和曲面等的绘制，对图形元素的基本操作如填充、擦除和裁剪等，来演示数值微分（dda）算法、中点画线算法和bresenham算法，中点画圆法，区域填充的递归算法，区域填充的

30、扫描线算法，cohen-sutherland法，梁友栋-barskey剪裁算法，sutherland-hodgman算法，de casteljau算法等。目前已有种类繁多的图形图像处理专用软件工具，如autocad、和photoshop等，利用这些图形图像处理软件可以实现同样的功能。即便如此，研究这些图形图像处理技术仍具有一定使用价值。利用一个设计良好的简单的小图形处理程序可以用于教学演示的目的，教学演示系统能够更形象的展示各种算法的工作原理，操作简洁，有利于分析和理解算法，而且便于在学习过程中能够更好的掌握基本图形生成的理论知识点。其次，在很多应用中需要提供自己的图形图像处理功能。例如，在一

31、个正在连接网络的任务中可能就希望显示一幅示意性的动画，此时，不能依赖一个图形软件来实现。因此，通过对独立功能的封装，可以为今后需要的图形图像的应用奠定基础。此外，借助visual c+语言能够充分挖掘硬件的潜能，得到性能优良的程序代码，同时通过编写算法实现程序加深对图形学基本内容的理解，提高用理论指导实践的能力。2 光栅图形学理论2.1 光栅图形学概述光栅图形学显示器可以看作一个像素的矩阵。在光栅显示器上显示的任何一种图形，实际上都是一些具有一种或多种颜色的像素集合。确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。对于一维图形，在不考虑线宽时，用一个像素宽的直、

32、曲线来显示图形；二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示，即区域填充。任何图形进行光栅化时，必须显示在荧屏的一个窗口里，超出窗口的图形不予显示。确定一个图形的哪些部分在窗口内必须显示；哪些在窗口外，不该显示的过程叫裁剪。裁剪通常在扫描转换之前进行，从而可以不必对那些不可见的图形进行扫描转换。对图形进行光栅化时，由于显示器的空间分辨率有限，对于非水平、垂直、45度的直线，因像素逼近误差，使所画图形产生畸变（台阶、锯齿）的现象称之为走样（aliasing）。用于减少或消除走样的技术称为反走样（antialiasing)。提高显示器的空间分辨率可以减轻走样程度，但这是以提高

33、设备成本为代价的。实际上，当显示器的像素可以用亮度显示时，通过调整图形上各像素的亮度也可以减轻走样程度。当不透光的物体阻挡了来自某些物体部分的光线，使其无法到达观察者时，这些物体部分就是隐藏部分。隐藏部分是不可见的，如果不删除隐藏的线或面，就可能发生对图的错误理解。为了使计算机图形能够真实地反映这一现象，必须把隐藏的部分从图中删除，习惯上称做消除隐藏线和隐藏面，或简称为消隐。2.2 任务概述本题目实现一个光栅图形学教学演示系统。教学演示系统能够更形象的展示各种算法的工作原理，该系统操作简洁能够在模拟的光栅区域上按照算法的原理将图形的光栅化过程展示出来，有利于分析和理解算法，能够更形象的展示各种

34、算法的工作原理，便于在学习过程中能够更好的掌握基本图形生成的算法。2.3 任务分析教学演示系统能够更形象的展示各种算法的工作原理，便于学生在学习过程中能够更好的掌握基本图形生成算法。这就要求体现以下内容：（1）掌握vc+语言和opengl编程技术。（2）设计简单的图形用户界面，以便于展现算法的实现。（3）掌握光栅图形学中相关算法的原理，这是本课题主要研究的内容。根据设计目标，分析出具体要实现绘制直线，绘制圆形，绘制矩形，裁剪图形，区域填充，画曲线，画曲面的功能，来实现直线扫描转换算法、圆弧的扫描转换算法、多边形的扫描转换与区域填充以及直线和多边形的裁减算法与生成曲线的算法等。2.3.1 直线扫

35、描转换算法在数学上，理想的直线是没有宽度的，它是由无数个点构成的集合。对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近于该直线的一组像素，并且按扫描线顺序。对这些像素进行操作，就是通常所说的用光栅显示器绘制直线或直线的扫描转换。由于一个图中可能包含成千上万条直线，所以要求绘制算法尽可能快。直线扫面转换算法有三个常用算法：数值微分（dda）法、中点画线法和bresenham算法。2.3.2 圆弧的扫描转换算法圆的特征，圆被定义为到给定中心位置的距离为定长的点集。圆心位于远点的圆有4条对称轴x=0，y=0，x=y和x=y。若已知圆弧上一点(x,y)，可以得到其关于4条对

36、称轴的其他7个点，这种性质称为八对称性。因此，只要扫描转换1/8圆弧，就可以用八对称性求出整个圆弧的像素集。圆弧的扫描转换算法的常用算法是中点画圆法。2.3.3 多边形的扫描转换与区域填充在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的定点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换。但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形，这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形学的一个基本问题是把多边形的顶点表示转换为点阵表示

37、，这种转换称为多边形的扫描转换。多边形的扫描转换算法的常用算法是扫描线算法和边界标志算法。区域填充，这里讨论的区域是指已经表示成点阵形式的填充图形，它是像素的集合。区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有像素着同一颜色；在边界表示中，区域的边界点着同一颜色。区域填充是指先将区域的一点赋予指定颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其他点。区域可分为四连通区域和八连通区域。多边形的区域填充的算法有区域填充的递归算法和区域填充的扫描线算法。2.3.4 直线和多边形的裁减算法直线段剪裁算

38、法比较简单，但非常重要，是复杂图元剪裁的基础。因为复杂的曲线可以通过折线段来近似，从而剪裁问题也可以化为直线段的剪裁问题。常用的线段剪裁方法有三种，即cohen-sutherland法和梁友栋-barskey剪裁算法。对于一个多边形，可以把它分解为边界的线段逐段进行剪裁，但这样做会使原来封闭的多边形变成不封闭或者一些离散的线段。当多边形作为实区域考虑时，封闭的多边形裁剪后仍应当是封闭的多边形，以便进行填充。为此，可以使用sutherland-hodgman算法，该算法的基本思想是一次用窗口的一条边裁剪多边形。2.3.5 曲线与曲面的生成算法几何造型技术是一项研究在计算机中如何表示物体模型形状的

39、技术。在几何造型系统中，有三种描述物体的三维模型，即线框模型、曲面模型和实体模型。曲面模型在线框模型的基础上，正加了物体中面的信息，但并没给出物体在面的哪一侧，则无法计算和分析物体的整体性质。虽然三维曲面模型表示三维物体的信息并不完整，但能够表达复杂的雕刻曲面，在几何造型中具有重要的地位。曲线、曲面可以用显式、隐式和参数表示，由于参数表示的曲线、曲面具有几何不变性等优点，计算机图形学中常用参数形式描述曲线、曲面。1962年，法国雷诺汽车公司的p.e.bezier构筑了一种已逼近为基础的参数曲线和曲面的设计方法，并用这种方法完成了一个称为unisurf的曲线和曲面设计系统。1972年，该系统被投

40、入应用。bezier曲线常用的生成算法为de casteljau算法。3 光栅图形学教学演示系统的详细设计3.1 总体设计根据上一章的分析以及，本文将该光栅图形学教学演示系统划分为五个功能块模块。分别是：直线模块，圆形模块，区域填充模块，裁剪图形模块和曲线曲面模块。图3.1 系统总体模块图系统总体模块图如图3.1所示。(1) 该系统的直线模块完成了绘制直线的功能，实现直线扫面转换算法包括数值微分（dda）法、中点画线法和bresenham算法；(2) 该系统的圆形模块完成了绘制圆形的功能，实现圆弧的扫描转换算法的中点画圆法；(3) 该系统的区域填充模块完成了图形填充的功能，实现区域填充的递归算

41、法和区域填充的扫描线算法；(4) 该系统的裁剪图形模块实现了直线段剪裁的演示和多边形裁剪的演示，完成了直线段剪裁的cohen-sutherland法和梁友栋-barskey剪裁算法和多边形裁剪的sutherland-hodgman算法；(5) 该系统的曲线曲面模块完成了绘制曲线和曲面的功能，实现了曲线的de casteljau算法。该系统能够在模拟的光栅区域上按照算法的原理将图形的光栅化过程展示出来，有利于分析和理解算法，能够更形象的展示各种算法的工作原理，便于在学习过程中能够更好的掌握基本图形生成的算法。其次根据该光栅图形学教学演示系统的总体模块以及功能结构，可以设计出系统的总流程，具体系统

42、总流程图如图3.2所示。该系统以菜单的方式工作，一旦选中某算法，按照算法的原理将图形的光栅化过程展示出来。图3.2 系统总流程图3.2 界面设计好的开端是从设计用户界面开始。首先，你要决定什么样的用户能使用该程序并根据需要来设置相应的用户界面对象。windows用户界面有一些标准的控制，如按钮、菜单、滚动条和列表等，这对那些 windows用户已经是很熟悉了。要记住的是，作为程序员必须选择一组控制并决定如何把它们安排到屏幕上。传统上，你需要在纸上做一下用户界面的草图，直到对各元素感到满意为止。这对于一些比较小的项目，以及一些大项目的早期原型阶段是可以的。3.2.1 窗口的设计windows支持

43、应用程序窗口，一个典型的应用程序应该活动在称为“框架窗口”中。一个框架窗口是一个全功能的主窗口，用户可以改变尺寸、最小化、最大化等。最简单的windows应用程序是使用单文档界面，只有一个框架窗口。在应用程序中要完成某个功能，都是以函数调用的形式实现的，同样，应用程序也是以函数调用的方式来通知操作系统执行相应的功能的。操作系统所能够完成的每一个特殊功能通常都有一个函数与其对应，也就是说，操作系统把它所能够完成的功能以函数的形式提供给应用程序使用，应用程序对这些函数的调用就叫做系统调用，这些函数的集合就是windows操作系统提供给应用程序编程的接口(application programmin

44、g interface)，简称windows api。如createwindow就是一个api函数，应用程序中调用这个函数，操作系统就会按照该函数提供的参数信息产生一个相应的窗口。visual c+不仅仅是一个编译器，还是一个全面的应用程序开发环境，使用它可以利用具有面向对象特性的c+来开发出专业级的windows应用程序。为了能充分利用这些特性，你必须理解c+程序设计语言。掌握了c+，你就必须掌握 microsoft基本类库(mfc)的层次结构，该层次结构包容了windows api中的用户界面部分，并使你能够很容易地以面向对象的方式建立windows应用程序。这种层次结构适用于所有版本的w

45、indows并彼此兼容。所以，创建mfc可执行程序mfc appwizard exe来完成界面的设计。3.2.2 菜单的设计用户与应用程序的交互通常是从菜单栏中选择命令，因此，菜单的资源在vc+编程中是很重要的。在windows中，菜单可以分为3大类：设计时用菜单资源编辑器定义的静态菜单，在运行时添加的动态菜单，还有前两种菜单的组合，快捷菜单是静态设计动态显示。根据该光栅图形学教学演示系统的总体模块以及功能结构，设计一个静态菜单。创建菜单最简单的方法是先在mfc中借助应用程序向导自动生成应用程序的基本框架，然后利用菜单资源编辑器进行加工设计。每个菜单项有两个基本要素，菜单项名和一个整数类型的命

46、令id号。通过给菜单的选项编写代码来完成应用程序的编程，使菜单id与应用程序主窗口连接起来，使应用程序的主窗口中显示菜单，来完成菜单操作设计的实现。3.3 直线模块设计该模块的主要功能是负责绘制直线段，实现了直线扫面转换算法包括数值微分（dda）法、中点画线法和bresenham算法，直线模块的流程图如图3.3所示。理想直线是由无数个点构成，绘制直线段即需要确定最佳逼近于该直线的一组像素，再对这些像素进行写操作。首先要确定线段端点的坐标（即起始点与结束点的坐标），从起始点开始，按照算法运算出下一个像素点的坐标，再从此像素点开始，继续算出下一个像素点的坐标，直到像素点为结束点为止，逐一绘制像素点

47、，即完成绘制线宽为一个像素的直线。其中根据不同直线扫描转换算法，算出下一个像素点坐标的方法不相同，每个算法都有各自的优点。图3.3 直线模块的流程图3.3.1 数值微分（dda）法已知过端点p0(,)，p1(,)的直线段l(p0,p1)；直线斜率为k=。画线过程为：从x的左端点开始，向x右端点步进，步长为=1（像素），按y=kx+b计算相应的y坐标，并取像素点(x,round(y)作为当前点的坐标。但这样做，计算每一个点需要做一个乘法、一个加法。设步长为x，有x=x+x， （3.1）用式（3.1）计算，当x=1时，则有。即x每递增1，y递增k（即直线斜率）。这样，计算就由一个乘法和一个加法减少

48、为一个加法。dda画线算法流程图如图3.4所示。应当注意的是，上述算法仅适用于情形。在这种情况下，x每增加1，y最多增加k.当时，必须把x，y的地位互换，y每增加1，x相应增加。同理，中点画线法，bresenham算法，也是如此。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整，这使得该算法不利于硬件实现。图3.4 dda画线算法流程图3.3.2 中点画线法通过观察可以发现，画直线段的过程中，当前像素点为(,)下一个像素点有两种可选择点p1(+1,)或p2(+1,+1)。若m=(+1,+0.5)为p1与p2的中点，q为理想直线与垂线的交点。当m在q的下方时，p2应为下

49、一个像素点；当m在q的上方时，应取p1为下一点。这就是中点画线法的基本原理（见图3.5）。图3.5 中点画线法每步迭代涉及的像素和中点示意图中点画线算法流程图如图3.6所示。图3.6 中点画线算法流程图对直线段l，采用方程表示，其中，。于是有下述点与l的关系：因此，预判断m在q点的上方还是下方，只要把m带入f(x,y)，并判断它的符号即可。构造下述判别式： （3.2）当d0时，m在l（q点）上方，取p1为下一个像素；当d=0时，选p1或p2均可，约定取p1为下一个像素。用式（3.2）计算符号时，需做4个加法和2个乘法。事实上，d是的线性函数，因此可采用增量计算，提高运算效率。方法如下。（1）

50、若，则取正右方像素p1(+1,)。判断下一个像素的位置时，应计算，增量为a。（2） 若d0，则取右上方像素p2(+1，+1)。要判断下一个像素的位置，应计算，增量为a+b。设从点(,)开始画线，d的初值。因f(,)=0，则。由于使用的只是d的符号，而d的增量都是整数，只是初始值包含小数。因此，可以用2d代替d来摆脱浮点运算，写出仅包含整数运算的算法。3.3.3 bresenham算法bresenham算法是在计算机图形学领域内使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个像素取右边点还是右上点。图3.7 bresenham算法所用误差项的几何意义如图3.7所示，设直线

51、方程为y=kx+b，则有,其中k为直线的斜率。假设x列的像素坐标已经确定为，其行坐标，那么下一个像素的列坐标为+1，而行坐标要么仍为，要么递增1为+1。是否增1，取决于图3.6所示误差项d的值。因为直线的起始点在像素中心，所以误差项d的初值=0。x下标每增加1，d的值相应递增直线的斜率值k，即d=d+k。当时，直线与+1列垂直网格的交点最接近于当前像素(,)的右上方像素(+1,+1)，该像素在y方向增加1，同时作为下一次计算的新基点，因此d值相应减去1；而当时，更接近于右方像素(+1,)。为方便计算，令e=d-0.5，e的初值为-0.5，增量为k。当时，取当前像素(,)的右上方像素(+1,+1

52、)，e减少1；而当时，更接近于右方像素(+1,)。图3.8 bresenham算法流程图bresenham算法流程图如图3.8所示。算法原理如下：过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。3.4 圆形模块设计圆形模块的流程图如图3.9所示。该模块的主要功能是负责绘制圆形。绘制圆形的常用算法为中点画圆法。图3.9 圆形模块的流程图3.4.1 中点画圆法构造函数，对于圆上的点，；对于圆外的点，；对于圆内的点，。

53、图3.10 当前像素与下一个像素的候选者与中点画线法一样，构造判别式：（1） 若d0，则应取p2为下一个像素。而且下一个像素的判别式为。（2） 若，则应取p1为下一像素。而且下一个像素的判别式。这里讨论的是按顺时针方向生成第二个八分圆（见图3.10），则第一个像素是(0,r)，判别式d的初始值为。中点画圆算法流程图如图3.11所示。图3.11 中点画圆算法流程图3.5 区域填充模块设计该模块的主要功能是负责填充图形，区域填充模块的流程图如图3.12所示。区域填充算法常用的算法有，区域填充的递归算法和区域填充的扫描线算法。图3.12 区域填充模块的流程图3.5.1 区域填充的递归算法和扫描线算法

54、种子填充算法假设在多边形内有一个像素已知，由此出发利用连通性找到区域内的所有像素。对于内点表示和边界表示的八连通区域的填充，只要将递归填充相邻的4个像素增加到递归填充8个像素即可。区域填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率，可以采用扫描线算法。扫描线算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在的扫描线上位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。区域填充扫描线算法流程图如图3.13所示，区域填充的扫描线算法可由下列四个步骤实

55、现。（1） 初始化。堆栈置空，将种子点(x,y)入栈。（2） 出栈。若栈空则结束；否则取栈顶元素(x,y)，以y作为当前扫描线。（3） 填充并确定种子点所在区段。从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。（4） 确定新的种子点。在区间中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回第（2）步。图3.13 区域填充扫描线算法流程图3.6 裁剪图形模块设计3.6.1 直线段裁剪直线段裁剪算法比较简单，但非常重要，是复杂原图的基础。因为复杂的曲线可以通过折

56、线段来近似，从而裁剪问题也可以化为直线段的剪裁问题。常用的线段剪裁方法，即cohen-sutherland法和梁友栋-barskey裁剪算法。（1） cohen-sutherland裁剪算法该算法的思想是：对于每条线段分为3种情况处理。第一种，若完全在窗口内，则显示该线段，简称“取”之。第二种，若明显在窗口外，则丢弃该线段，简称“弃”之。第三种，若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段，其中一段完全在窗口外，可弃之，然后对另一段重复上述处理。为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法：延长窗口的边，将二维平面分成9个区域，每个领域赋予4

57、位编码，如图3.14所示，其中各位编码的定义如下。图3.14 多边形裁剪区域编码裁剪一条线段时，先求出所在的区号code1，code2。若code1=0，且code2=0，则线段在窗口内，应取之。若按位与运算code1&code20，则说明两个端点同在窗口的上方、下方、左方或右方，可判断线段完全在窗口外，可弃之；否则，按第三种情况处理，求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之，在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只有按顺序检测到端点的编码不为0时，才对线段与对应的窗口边界求交。cohen-sutherland裁剪算法流程图如图3.15所示 。图3.15 cohen-sutherland裁剪算法流程图（2） 梁友栋-barskey裁剪算法梁友栋和barskey提出了更快的参数化裁剪算法。首先按参数化形式写出裁剪条件：这四个不等式可以表示为统一的形式：。