计算机图形学北京建筑

1、计算机图形学,主讲教师：吕书强 Email: ,适合GIS专业,教学要求,了解图形系统的框架及其涉及的软件、硬件技术； 了解图形学的基本问题，掌握图形学的基本概念、方法与算法； 对与图形相关的应用及当前的研究热点有一个初步认识； 具有一定实践体会和相关的编程能力。,教材或参考书：,杜晓增，计算机图形学基础，高教，2005 王汝传等，计算机图形学，人民邮电出版社，2003. 李东等，计算机图形学实用教程，人民邮电出版社，2004。 主要参考书： 潘云鹤等，“计算机图形学原理、方法及应用”，高等教育出版社，2003。 孙家广等，计算机图形学（第三版），清华大学出版社，2002。,讲授内容,第1章

2、概述 第2章 计算机图形系统 第3章 VC开发环境简介 第4章 基本图形元素的生成算法 第5章 图形变换 第6章 图形裁剪 第7章 真实感物体绘制,第一章 绪论,1.1 研究内容 1.2 发展历史 1.3 计算机图形学的应用及研究前沿,1.1 研究内容,何谓图形 构成图形的要素 图形的两种表示法 图形学所研究的内容,图形以及构成图形的要素,图形：计算机图形学的研究对象 能在人的视觉系统中产生视觉印象的客观对象 包括自然景物、拍摄到的图片、用数学方法描述的图形等等 构成图形的要素 几何要素：刻画对象的轮廓、形状等 非几何要素：刻画对象的颜色、纹理等,计算机中表示图形的方法,点阵表示 枚举出图形中

3、所有的点(强调图形由点构成) 简称为图像（数字图像） 参数表示 由图形的形状参数(方程或分析表达式的系数，线段的端点坐标等)+属性参数(颜色、线型等)来表示图形 简称为图形：,什么是计算机图形学,定义1：计算机图形学是研究怎样用计算机生成、处理和显示图形的一门学科。 定义2：计算机图形学是研究通过计算机将数据转换为图形，并在专用显示设备上显示的原理、方法和技术的一门学科。 计算机图形学计算机科学中，最为活跃、得到广泛应用的分支之一,计算机图形学的研究内容,如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法，构成了计算机图形学的主要研究内容。 图形硬件、图形标准、图

4、形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。,与相关学科的关系,数字图像,数据模型,图像生成（计算机图形学）,模型（特征）提取 （计算机视觉，模式识别）,模型变换 （计算几何）,图像变换 （图像处理）,.发展特点: 交叉、界线模糊、相互渗透,第一章 绪论,1.1 研究内容 1.2 发展历史 1.3 计算机图形学的应用及研究前沿,1.2 发展历史,历史追溯 硬件发展 图形显示器的发展 图形输入设备的发展 图形软件及软件标准的发展,历史追溯,50年代 1950年，第一台图形显示器作为美国麻省理工学院（MI

5、T）旋风I号（Whirlwind I）计算机的附件诞生了 1958年，美国Calcomp公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪 50年代末期，MIT的林肯实验室在“旋风”计算机上开发SAGE空中防御体系,历史追溯,60年代 1962年，MIT林肯实验室的I. E. Sutherland发表了一篇题为“Sketchpad：一个人机交互通信的图形系统”的博士论文-确定了交互图形学作为一个学科分支（提出基本交互技术、图元分层表示概念及数据结构)。 1962年，雷诺汽车公司的工程师Pierre Bzier 提出Bzier曲线、曲面的理论 1964年MI

6、T的教授Steven A. Coons提出了超限插值的新思想，通过插值四条任意的边界曲线来构造曲面。,历史追溯,70年代 光栅图形学迅速发展 区域填充、裁剪、消隐等基本图形概念、及其相应算法纷纷诞生 图形软件标准化 1974年，ACM SIGGRAPH的“与机器无关的图形技术”的工作会议 ACM成立图形标准化委员会，制定“核心图形系统”（Core Graphics System） ISO发布CGI、CGM、GKS、PHIGS,真实感图形学 1970年，Bouknight提出了第一个光反射模型 1971年Gourand提出“漫反射模型插值”的思想，被称为Gourand明暗处理 1975年，Pho

7、ng提出了著名的简单光照模型- Phong模型 实体造型技术 英国剑桥大学CAD小组的Build系统 美国罗彻斯特大学的PADL-1系统,历史追溯,80年代 1980年Whitted提出了一个光透视模型-Whitted模型，并第一次给出光线跟踪算法的范例，实现Whitted模型 1984年，美国Cornell大学和日本广岛大学的学者分别将热辐射工程中的辐射度方法引入到计算机图形学中 图形硬件和各个分支均在这个时期飞速发展,历史追溯,90年代：微机和软件系统的普及使得图形学的应用领域日益广泛。 标准化、集成化、智能化 多媒体技术、人工智能、科学计算可视化、虚拟现实 三维造型技术,历史追溯,ACM

8、 SIGGRAPH会议小知识 全称 “the Special Interest Group on Computer Graphics and Interactive Techniques” 60年代中期，由Brown 大学的教授Andries van Dam (Andy) 和IBM公司的Sam Matsa发起 1974年，在Colorado大学召开了第一届SIGGRAPH 年会，并取得了巨大的成功 每年只录取大约50篇论文,历史追溯,硬件发展,图形显示器的发展 图形显示器是计算机图形学中关键的设备 60年代中期：画线显示器（亦称矢量显示器） 需要刷新。设备昂贵，限制普及 60年代后期：存储管式

9、显示器 不需刷新，价格较低，缺点是不具有动态修改 图形功能，不适合交互式。,硬件发展,70年代初，刷新式光栅扫描显示器出现，大大地推动了交互式图形技术的发展。 以点阵形式表示图形，使用专用的缓冲区存放点阵，由视频控制器负责刷新扫描。,图形显示设备的发展：,画线显示器（矢量显示器/随机扫描显示器）,存储管式显示器,刷新式光栅扫描显示器,硬件发展,图形输入设备的发展 第一阶段：控制开关、穿孔纸等等 第二阶段：键盘 第三阶段：二维定位设备，如鼠标、光笔、图形输入板、触摸屏等等，语音 第四阶段：三维输入设备（如空间球、数据手套、数据衣），用户的手势、表情等等 第五阶段：用户的思维,第一章 绪论,1.1

10、 研究内容 1.2 发展历史 1.3 计算机图形学的应用及研究前沿,1.3计算机图形学的应用及研究前沿,计算机图形学的应用,图形用户界面 介于人与计算机之间，人与机器的通信。 人机界面（HCI）：软件硬件 发展：由指示灯和机械开关组成的操纵界面由终端和键盘组成的字符界面（80年代）由多种输入设备和光栅图形显示设备构成的图形用户界面（GUI）（90年代）。PC，工作站，WIMP(W-windows、I-icons、M-menu、P-pointing devices)界面，所见即所得VR技术（发展方向）,计算机辅助设计与制造（CAD/CAM）,-CAD/CAM是计算机图形学在工业界最广泛、最活跃的

11、应用领域 飞机、汽车、船舶的外形的设计 发电厂、化工厂等的布局 土木工程、建筑物的设计 电子线路、电子器件的设计 设计结果直接送至后续工艺进行加工处理，如波音777飞机的设计和加工过程,奥迪效果图和线框图,计算机辅助设计与制造（CAD/CAM）,基于工程图纸的三维形体重建 定义：从二维信息中提取三维信息，通过对这些信息进行分类、综合等一系列处理，在三维空间中重新构造出二维信息所对应的三维形体，恢复形体的点、线、面及其拓扑关系，从而实现形体的重建 优势：可以做装配件的干涉检查、以及有限元分析、仿真、加工等后续操作，代表CAD技术的发展方向,工程图及其三维重建结果1,工程图及其三维重建结果2,可视

12、化,科学计算可视化(Scientific Visualization) 海量的数据使得人们对数据的分析和处理变得越来越难，用图形来表示数据的迫切性与日俱增 1986年，美国科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（Visualization in Scientific Computing）” 科学计算可视化广泛应用于医学、流体力学、有限元分析、气象分析当中,可视化,在医学领域，可视化有着广阔的发展前途 是机械手术和远程手术的基础 将医用CT扫描的数据转化为三维图象，帮助医生判别病人体内的患处 由CT数据产生在人体内漫游的图象 可视化的前沿与难点 可视化硬件的研究 实

13、时的三维体绘制 体内组织的识别分割Segmentation,真实感图形实时绘制与自然景物仿真,计算机中重现真实世界的场景叫做真实感绘制 真实感绘制的主要任务是模拟真实物体的物理属性，简单的说就是物体的形状，光学性质，表面的纹理和粗糙程度，以及物体间的相对位置，遮挡关系等等,真实感图形实时绘制与自然景物仿真,光照模型 简单光照模型 整体光照模型 绘制方法 光线跟踪 辐射度 加速算法 包围体树、自适应八叉树等等,地理信息系统（GIS）,建立在地理图形之上的关于各种资源的综合信息管理系统。 数字地球，地形数据作为载体。 军事，政府决策，旅游，资源调查。,娱乐,电脑游戏 实时性 逼真性 蕴含了先进的图

14、形处理技术 电视广告，节目片头，科教演示（CAI） Quake III，“古墓丽影”，“侏罗纪公园”、“皇帝的新衣”、完美风暴 MAYA, 3D-MAX, SOFTIMAGE,多媒体,在计算机控制下，对多种媒体信息进行生成、操作、表现、存储、通信、或集成的信息系统其中媒体至少应包括一种“连续媒体”或一种“离散媒体”。 计算机处理的常见媒体：文本、图形、图像、语音、音频、视频、动画 特点：媒体的多样性、操作的交互性、系统的集成性 CAI， 娱乐。,Virtual Reality（虚拟现实、灵境）,Virtual Reality 或称虚拟环境（Virtual Environment) 是用计算机技

15、术来生成一个 逼真的三维视觉、听觉、触觉 或嗅觉等感觉世界，让用户可 以从自己的视点出发，利用自 然的技能和某些设备对这一生 成的虚拟世界客体进行浏览和 交互考察。 输入输出设备,虚拟现实（Virtual Reality简称VR）,虚拟现实是指用立体眼镜、传感手套等一系列传感辅助设施来实现的一种三维现实，人们通过这些设施以自然的方式（如头的转动、手的运动等）向计算机送入各种动作信息，并且通过视觉、听觉以及触觉设施使人们得到三维的视觉、听觉等感觉世界。随着人们不同的动作，这些感觉也随之改变。,QuickTime技术简介,QuickTime是苹果公司开发的新一代虚拟现实技术。它是一种基于静态图像处

16、理的，在微机平台上能够实现的初级虚拟现实技术。它的出现使得以往专业实验室中成本昂贵的虚拟现实技术的应用普及有了广阔的前景。 假定我们在一室空间进行观察，室内空间一般有六个面，如果我们获取了这六个面的许多不同距离，不同方位的实景照片并将它们按照相互的关系有机连接起来，就可以在视觉上形成这个房间整个空间的整体认识，这就是全景概念。,当前研究热点,真实感图形实时绘制 物体网格模型的面片简化：对网格面片表示的模型，在一定误差的精度范围内，删除点、边、面，从而简化所绘制场景的复杂度，加快图形绘制速度 基于图象的绘制(IBR，Image Based Rendering)：完全摒弃传统的先建模，然后确定光源

17、的绘制的方法。它直接从一系列已知的图象中生成未知视角的图象，适用于野外极其复杂场景的生成和漫游,野外自然景物的模拟 野外场景远远复杂于室内场景，绘制难度更大，方法更趋多样化 主要绘制山、水、云、树、草、火等等 绘制火的粒子系统（Particle System），基于生理模型的绘制植物的方法，绘制云的细胞自动机方法等,由清华大学自然景物平台生成的野外场景,日本Yoshinori Dobashi等人绘制的真实感云,Xfrog3.0生成的挪威云杉,与计算机网络技术的紧密结合,远程医疗与诊断 远程导航与维修 远程教育,计算机动画,计算机动画近十多年来取得了很大的发展，已渗透到人们生活的各个角落 商业广

18、告、影视特技/片头、动画片 教育、军事、飞行模拟等 分类 二维动画 图象变形 形状混合,计算机动画,三维动画 关键帧动画 变形物体的动画 过程动画 关节动画与人体动画,基于特征的图象变形（猫变虎）,用户接口,用户接口是人们使用计算机的第一观感。一个友好的图形化的用户界面能够大大提高软件的易用性 图形学已经全面融入计算机的方方面面，很多软件几乎可以不看任何说明书，而根据它的图形、或动画界面的指示进行操作,用户接口,目前几个大的软件公司都在研究下一代用户界面，开发面向主流应用的、自然、高效多通道的用户界面。研究多通道语义模型、多通道整合算法及其软件结构和界面范式是当前用户界面和接口方面研究的主流方

19、向，而图形学在其中起主导作用。,计算机艺术,用计算机软件从事艺术创作 二维平面的画笔程序（如CorelDraw，Photoshop，PaintShop） 图表绘制软件（如Visio） 三维建模和渲染软件包（如3DMAX，Maya）、以及一些专门生成动画的软件（如Alias，Softimage）,计算机艺术,优点： 提供多种风格的画笔画刷 提供多种多样的纹理贴图，甚至能对图象进行雾化，变形等操作 可以任意修改，取消败笔 不足： 无法达到传统绘画中风格化的 艺术效果 很难得到有素描效果、油画效果的艺术品,计算机艺术,非真实感绘制（NPR，Non-Photorealistic Rendering）

20、用于模拟艺术效果，研究方法有别于真实感图形学 钢笔素描的生成 钢笔素描产生于中世纪，从19世纪开始成为一门艺术20世纪90年代开始研究用计算机模拟 中国国画与书法的生成,Georges Winkenb1ach绘制的壶和碗(Siggraph96),Salisbury绘制的茶壶(Siggraph97),Salisbury绘制的熊(Siggraph97),Oliver Deussen绘制的素描树(Siggraph2000),第二讲,图形系统,计算机图形硬件简介,图形输入设备 1 向量型图形输入设备 它采取跟踪轨迹、记录坐标点的方法输入图形。常用的向量型图形输入设备有数字化仪、鼠标器、光笔等。 2 光

21、栅扫描型图形输入设备 它采取远行扫描、按一定密度采样的方式输入图形，输入数据为一灰度图。这方面的研究已逐步达到实用阶段。常用的光栅扫描型图形输入设各有扫描仪和摄像机。栅格数据经过图形识别可以转换为矢量图形 。,计算机图形硬件简介,图形输出设备 图形输出设备是以纸、胶片、塑料薄膜等物质为介质，输出入眼可视并能长期保存的图形的计算机外部设备。 1 向量型设备 作画机构随着图形的输出形状而移动并成像。如笔式绘图仪。 2 光栅扫描型设备 作画机构按光栅矩阵方式扫描整张图面，并按输出内容对图形成像。光栅扫描型输出设备包括点阵式打印机、热敏印刷机、静电印刷机、喷墨印刷机以及激光打印机等。,计算机图形硬件简

22、介,常用图形显示设备 1 阴极射线管 阴极射线管的技术指标主要有两条，一是分辨率，二是显示速度。 2 显示器 显示器有随机扫描显示器、存储管式显示器、光栅扫描式显示器、液晶显示器、等粒子显示器等。,第三讲,VC+开发环境,VC+开发环境,1 VC+ 6.0是一个集成开发环境，它以C+语言为基础，实施面向对象编程。 2 VC+ 6.0 的集成环境能完成绝大多数编程事务，包括菜单设置、图标绘制、对话窗口设置、工具按钮以及帮助文件的设置等等。 3 VC+ 6.0 的导航功能遍及各个方面，能为编程人员提供快速的原型。 4 VC+ 6.0 能实现不同层次的编程，从底层的面向硬件的编程到高级的各种应用集成

23、。,VC+程序的基本架构,程序入口(App) 框架类(Main/ChildFrame) 文档类(Doc)负责数据的存取 视图类(View)-负责信息的展示 资源（对话框、菜单等）,VC+程序的基本架构,程序入口(App) WinMain函数隐藏在应用程序框架内部。 类CExamApp的对象代表了一个应用程序。定义了一个单独的全局CExamApp对象theApp。基类CWinApp。 应用程序启动，首先调用WinMain函数，这个函数就查找该应用程序的全局构造对象theApp,VC+程序的基本架构,框架类(Main/ChildFrame) CMainFram应用程序的主框架窗口。当构造函数调用基

24、类CFrameWnd的Create函数时，Windows将创建具体的窗口结构。 主框架窗口包括标题栏、菜单栏。而工具栏窗口、状态栏窗口和视图窗口则占据着主框架窗口的客户区域。,VC+程序的基本架构,框架类(Main/ChildFrame),VC+程序的基本架构,文档类(Doc)负责数据的存取 Microsoft在设计基础类库时，考虑到把数据与它的显示分离开，于是就采用文档类和视类结构来实现。 数据的存储和加载由文档类来完成，数据的显示和修改则由视类来完成，从而把数据管理和显示方法分离开来。,VC+程序的基本架构,视图类(View)-负责信息的展示,VC+程序的基本架构,资源（对话框、菜单等）

25、包括对话框、菜单、快捷键、图标等。 对话框：模式对话框和无模式对话框,VC+程序的基本架构,Frame、View、Document是互相联系的。 如SDI程序，CMainFrame调用GetActiveView获得CView 而CView可以调用GetDocument获得CDocument。 如果已知CDocument，可以使用GetFirstViewPosition获得第一个相关的CView，然后使用GetNextView获得下一个的CView。,消息处理与交互式绘图,Windows应用程序具有俘获各种操作和事件的能力，并提供相应的机会对之进行反应，这实质上是一个消息处理机制，按消息的级别和

26、到达的次序进行相应的处理。 交互式绘图一般要求对鼠标/键盘的操作（MouseClick/MouseMove等）进行反应，并通过获取相应信息来建立相应的图形。 CDC类一包括用于图形绘制的全部函数和操作。 OpenGL提供了用于三维图形实体设计的全部函数和操作。,Windows系统把应用程序的所有输入传入给应用程序窗口，每一个窗口都有一个称作窗口过程的函数，当窗口有输入时Windows系统要调用它，窗口过程处理输入并把控制返回给Windows。Windows系统以消息的形式把输入传给窗口过程，消息是由Windows系统或应用程序产生的，Windows系统对于每一个输入事件都要产生消息-例如键盘、

27、鼠标的动作。Windows系统为了响应应用程序给系统带来的变化也会产生消息-例如应用程序改变了系统字体或改变了一个窗口的大小。应用程序可以通过产生消息指导它自己的窗口来完成某项任务，或是与其他应用程序的窗口进行通信。 消息有六个参数： typedef struct tagMSG HWND hwnd; UINT message; WPARAM wParam; LPARAM lParam; DWORD time; POINT pt; MSG;,消息处理与交互式绘图,目的窗口(hwnd):,接收消息的窗口，也就是那一个窗口的窗口过程将被调用。,消息标志(message):,一个命名的常量，用来标志消

28、息的目的，也就是消息的含义。如果窗口过程收到一条消息，它就通过消息标志来决定如何处理这条消息。,消息的附加内容，具体的含义取决于具体消息标志message。参数分为高低位。消息参数可以是一个整数、紧缩的位标志、一个含有附加数据结构的指针等等。,参数1(wParam):,消息处理与交互式绘图,参数2(lParam):,消息的附加内容，具体的含义取决于具体消息标志message。参数分为高低位。消息参数可以是一个整数、紧缩的位标志、一个含有附加数据结构的指针等等。,消息发出的时间。,分发时间(time):,光标位置(pt):,消息发生时鼠标光标的位置。以设备坐标系定位。,消息处理与交互式绘图,交互

29、绘图实例,Scribble线条的任意绘制，主要是跟踪鼠标的操作。,几个基本的图形操作函数,CDC类-设备类，能提供图形、文本等的输出设备。 CDC类里包含了大量的基本图形函数，包括线型、颜色、填充模式、位图等的设置，以及点、线、多变形等各种基本图形绘制函数，而其中最为基本的函数是SetPixel，它是其他函数的实现基础。 以下将重点介绍几个基础函数。 RGB 函数，根据提供的三原色参数合成一个颜色，如RGB(255,0,0)即合成红色，返回类型通常为以长整型，且以COLORREF类型表示。,几个基本的图形操作函数,/* SetPixel函数的使用 COLORREF SetPixel( int

30、x, int y, COLORREF crColor ); COLORREF SetPixel( POINT point, COLORREF crColor ); - */ pDC-SetPixel(100,100,RGB(0,0,255); int i=1; for(i=1;iSetPixel(i,i*2,RGB(0,0,255); ,几个基本的图形操作函数,/- /* CPen类的使用 BOOL CreatePen( int nPenStyle, int nWidth, COLORREF crColor ); - nPenStyle: PS_SOLID 实线 PS_DASH 短线 PS_D

31、OT 点 */,几个基本的图形操作函数,CPen apen; if (apen.CreatePen(PS_SOLID,2,RGB(255,0,0) CPen* odlpen=pDC-SelectObject( ,几个基本的图形操作函数,/* CBrush类的使用 BOOL CreateSolidBrush( COLORREF crColor ); BOOL CreateHatchBrush( int nIndex, COLORREF crColor ); - nIndex: HS_BDIAGONAL HS_CROSS HS_DIAGCROSS HS_FDIAGONAL HS_HORIZONTA

32、L HS_VERTICAL */,几个基本的图形操作函数,CBrush abrush; if (abrush.CreateSolidBrush(RGB(0,255,0) CBrush* oldbrush=pDC-SelectObject( ,几个基本的图形操作函数,对于任何采用SetPixel绘图的函数，必须包括两个基本的参数，即设备参数CDC *pDC, COLORREF aColor void Cmap:DrawLineBySetpixel(CDC *pDC, COLORREF aColor) int i=0; for (i=1;iSetPixel(i,i*3,aColor); retur

33、n; ,第四讲,基本图形元素的生成算法,基本图形元素,点、线、圆（圆弧）、区域填充和字符等。 基本图形生成算法：速度、质量，通常情况下速度是第一位的，因为算法通常被调用很多次。,点的生成,点是最基本的图形，通常情况下，点由一个像素（设置其显示缓冲器的灰度值）来描述。 对于光栅显示器，象素点的多少决定了显示器的分辨率。横向分辨率通常为320、640、1024，8 的倍数，纵向通常为200、480、1024。,直线的生成,在光栅显示器的荧光屏上生成一个对象，实质上是往帧暂存寄存器的相应单元中填入数据。画一条从(x1,y1)到(x2,y2)的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数

34、据的过程。这个过程也称为直线光栅化。 基本要求： 1、应该为最佳逼近线；2、端点位置应该是正确的；3、线浓度应该是均匀的；4、生成速度应该尽可能的快。 几种基本直线算法： 1、DDA；2、中点法；3、Bresenham算法。,直线生成算法-DDA,数值微分法（）,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),栅格交点表示象素点位置,。,。,。,。,数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为

35、这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,数值微分(DDA)法,计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1;yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)； 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。 当 k 1时，必须把x，y地位互换,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,数值微分(DDA)法,void DDALine(int x0,int y0,int x1

36、,int y1,CDC* pDC, COLORREF aColor) int x; float dx, dy, y, k; dx = x1-x0; dy=y1-y0; k=dy/dx ; y=y0; for (x=x0; xx1; x+) pDC-SetPixel (x, int(y+0.5), acolor); y=y+k; ,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2) x int(y+0.5) y+0.5 000+0.5 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0+0.5,数值微分(DDA)法,缺点： 在此算法中，y、k

37、必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,直线生成算法中点法,讨论情况（直线斜率限定在0-1之间）: 对于任意直线方程F(x,y)=ax+by+c=0,在高斯平面上将平面分为两部分，上半部分F(x,y)0，而下半部分F(x,y)0。如果想要判定某个平面点在直线的上方还是下方，只需要将其坐标代入，而后看F(x,y)的值即可判定其位置。,中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点 现需确定下一个点亮的象素。,中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。

38、 M在Q的上方- P1离直线更近更近-取P1 M与Q重合， P1、P2任取一点。 问题：如何判断M与Q点的关系？,中点画线法,假设直线方程为：ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由常识知： 欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,中点画线法,构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？,中点画线法,若d0-M在直线上方-取P1; 此时再下一个象素的

39、判别式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为a,中点画线法,若dM在直线下方-取P2; 此时再下一个象素的判别式为 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为ab,中点画线法,画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用

40、d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。,中点画线法,void Midpoint Line (int x0,int y0,int x1, int y1,CDC* pDC, COLORREF aColor) int a, b, d1, d2, d, x, y; a=y0-y1; b=x1-x0; d=2*a+b; d1=2*a ; d2=2* (a+b); x=x0; y=y0; pDC-SetPixel(x, y, aColor); while (xSetPixel (x, y, color); /* while */ /* mid PointLine *

41、/,中点画线法,例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 i xi yid 1 0 01 2 1 0-3 3 2 13 4 3 1-1 5 4 25,如前所述，直线绘制的总步长数一般取dx,dy中绝对值较大者，如果较大跨度者（假设在1a向限，dxdy）步长(Dx)取为1，则另一个步长（Dy）应小于1。由于光栅化效应，画点在整数位置，故y 的位置只能取其最接近的点，如图2.2所示。 设d1 ,d2为：d1=y-yi;d2=yi+1-y 则有d1d2时y取yi否则取yi+1,直线Brese

42、nham算法,直线Bresenham算法,作业及答案,1 DDA法生成直线的基本原理是什么? 2 为什么说Bresenham画圆的算法效率较高? 3 为什么说直线生成算法是二维图形生成技术的基础？ 4 准备下一节课实验的内容,圆的基本知识,圆的位图,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： X2 + Y2 = R2,圆的基本知识,圆弧扫描算法,X2 + Y2 = R2 Y = Sqrt(R2 - X2) 在一定范围内，每给定一 X值，可得一Y值。 当X取整数时，Y须取整。 缺点：浮点运算，开方， 取整，不均匀。,圆的逐点比较法算法,用逆时针画第一象限中AB

43、圆弧的过程如下： 从始点（Xa，Ya）开始，首先向(-X方向)圆内走一步，然后比较 判断结果，落在圆内则向Y方向走一步，依次类推，一直到达圆外为止 当判断结果落在圆外时，向X方向走一步，直到再次到达圆内为止 当画到终点以（Xb，Yb）时，终止比较，结束。,圆的逐点比较法算法,圆的角度DDA法,x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 = x n + dx = x n - Rsind =x n - (y n - y 0 )d y n+1 = y n + dy = y

44、 n + Rcosd =y n + (x n - x 0 )d 显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,生成圆弧的正负法,原理：,设圆的方程为F(x,y)=X2 + Y2 - R2=0; 假设求得Pi的坐标为(xi,yi)； 则当Pi在圆内时- F(xi,yi) 向右- 向圆外 Pi在圆外时- F(xi,yi)0 - 向下- 向圆内,生成圆弧的正负法,即求得Pi点后选择下一个象素点Pi+1的规则为： 当F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi; 当F(xi,yi) 0 取xi+1 =

45、 xi， yi+1 = yi - 1; 这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，故称正负法。 快速计算的关键是F(xi,yi) 的计算，能否采用增量算法？,生成圆弧的正负法,若F(xi,yi) 已知，计算F(xi+1,yi+1) 可分两种情况： 1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +1 2、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,yi

46、+1)= (xi+1 )2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1 3、初始值：略,中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆 P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。,中点画圆法,构造函数：F（X，Y）=X2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y）在圆外。 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,中点画圆法,有如下结论： F（M）M在圆内- 取P1 F（M）=

47、0 -M在圆外- 取P2 为此，可采用如下判别式：,M,P1,P2,中点画圆法,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2 = d + 2xp +3 即d 的增量为 2xp +3.,中点画圆法,若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp

48、- 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - R,M,P1,P2,中点画圆法,MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) drawpixel(x,y,color); if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) +

49、5; x+;y-; ,中点画圆法,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-R,圆的Bresenham算法,设圆的半径为r，先考虑圆心在(0,0)，并从(0，r)开始的顺时针方向的18圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有xi+1xi+1，相应的yi+1则在两种可能中选择： yi+1=yi或者yi+1=yi-1 。 选择的原则是考察精确值y是靠近yi还是靠近yi-1,圆的Bresenham算法,4.4 区域填充算法,基础知识: 区域填充即给出一个

50、区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色， 多边形填色即给出一个多边形的边界，要求对多边形边界范围内的所有像素单元赋予指定的颜色代码。要完成这个任务，一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判断法”。 1将多边形画在平面上。 2用一根水平扫描线自左向右通过多边形从而与多边形的边界相交。描线与边界相交奇数次后进入该多边形，相交偶数次后走出该多边形。,实区域填充算法分类,扫描线填充算法-扫描线顺序 有序边表算法 边填充算法 种子填充算法-内部一个点出发 简单种子算法 扫描线种子算法,扫描线填色算

51、法,扫描线填色存在的问题： 错判，如A点错判为进入多边形 交点个数错误，如B/C交点多余应有数 填色算法的两个大类： 扫描线填色，可以实现自动化或交互填色。 种子填色，只能交互填色。,扫描线填色算法,扫描线填色算法的基本思想是： 用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形，每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。,扫描线填充算法,求交：I4, I3, I2, I1 排序：I1, I2, I3, I4 交点配对：(I1, I2), (I3, I4) 区间填

52、色,利用图形的空间连贯性和扫描线的连贯性,148,顶点交点的计数问题,检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数,计数2次,计数1次,计数2次,扫描线填充算法,扫描线填充算法,影响一般扫描线填充算法效率的因素？,所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。,如何提高效率？,建立每条扫描线的活性边表,何谓活性边？,求交和排序,目标是简化交点计算,有序边表算法,与当前扫描线相交的边称为活性边（active edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，边的活性边表 （ AEL, Active edge table)。它记录了多边形边沿

53、扫描线的交点序列。 只需对当前扫描线的活性边表作更新，即可得到下一条扫描线的活性边表。,扫描线填充算法,扫描线填充算法,如何计算下一条扫描线与边的交点。 直线方程：ax+by+c = 0 当前交点坐标：(xi, yi) 下一交点坐标：(xi+1,yi+1) xi+1= (-byi+1)-c)/a = (-byi-b)-c)/a =xi-b/a=xi+1/k 活动边表中需要存放的信息： x：当前扫描线与边的交点 x-b/a：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线,y=yi+1,y=yi,Pj,Pj+1,(xi,yi),(xi+1,yi+1),扫描线填充算法,活性边表

54、的更新 为了方便边的活性边表的更新，建立另一个表-新边表，存放在该扫描线第一次出现的边。 存放的信息： x：扫描线与该边的初始交点 x：x的增量 ymax：该边的最大y值,新边插入、旧边删除,即算法中采用较灵活的数据结构。它由新边表ET（Edge Table）和活性边表AEL（Active Edge List）两部分组成。 表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成： x: 在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线的交点的坐标； x:边的斜率的倒数； ymax:边的上端点的y坐标； next:指向下一条边的指针。,扫描线填充算法,扫描线填色算法,水平

55、边处理 水平线与水平边无法求交，故应去掉。 采用递归算法 扫描线与边的求交点方法采用递归算法。 以(x1，y1)、(x2，y2)为端点的边与第I+1条扫描线的交点为:,数据结构与实现步骤,边的分类表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线，就设多少类。同一类中，各边按x值（x值相等时，按x的值）递增的顺序排列成行。,边表,(Ymax, x,x, next),(Ymax, x,x, next),活动边表的例子,3,4,-2,P3 P4,5,6.5,0.5,P3 P2,扫描线2,AET指针,6,2,0,P4 P5,5,7,0.5

56、,P3 P2,扫描线3,AET指针,(Ymax, x,x, next),3,6,-2,P3 P4,5,6,0.5,P3 P2,扫描线1,AET指针,算法实现步骤,这样，当建立了边的分类表ET后，扫描线算法可按下列步骤进行： （1）取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 （2）将边的活化链表AEL设置为空。 （3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。,算法实现步骤,1）如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表中，AEL中的各边按照x值（当x值相等时，按x值）递增方

57、向排序。 2）若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。 3）将边的活化链表AEL中满足y=ymax的边删去。 4）将边的活化链表AEL剩下的每一条边的x域累加x，即x:=x+x。 5）将当前的扫描线的纵坐标值y累加1，即y:=y+1。,扫描线算法,特点：算法效率较高。 缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。,种子填冲算法,基本思想： 给出多边形光栅化后的边界位置及边界色代码，以及多边形内的一点

58、(x，y)，然后按照4邻域、8邻域法填充多边形。,种子填冲算法,区域填充要求区域是连通的 连通性 4连通、8连通 4连通： 8连通,适合于内点表示区域的填充算法 设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。 步骤如下： 种子象素入栈，当栈非空时，执行如下三步操作： （1）栈顶象素出栈； （2）将出栈象素置成多边形色； （3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,种子填充算法,种子填充算法,递归算法可实现如下,void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) PutPixel(x