《计算机图形学 --原理、方法及实现.ppt》由会员分享，可在线阅读，更多相关《计算机图形学 --原理、方法及实现.ppt（210页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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年，第一台图形显示器作为美国麻省理工学院（MIT）旋风I号（Whirlwind I）计算机的附件诞生了1958年，美国Cal
5、comp公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪50年代末期，MIT的林肯实验室在“旋风”计算机上开发SAGE空中防御体系,历史追溯,60年代1962年，MIT林肯实验室的I. E. Sutherland发表了一篇题为“Sketchpad：一个人机交互通信的图形系统”的博士论文-确定了交互图形学作为一个学科分支（提出基本交互技术、图元分层表示概念及数据结构)。1962年，雷诺汽车公司的工程师Pierre Bzier 提出Bzier曲线、曲面的理论1964年MIT的教授Steven A. Coons提出了超限插值的新思想，通过插值四条任意的边界曲线
6、来构造曲面。,历史追溯,70年代光栅图形学迅速发展区域填充、裁剪、消隐等基本图形概念、及其相应算法纷纷诞生图形软件标准化1974年，ACM SIGGRAPH的“与机器无关的图形技术”的工作会议ACM成立图形标准化委员会，制定“核心图形系统”（Core Graphics System）ISO发布CGI、CGM、GKS、PHIGS,真实感图形学1970年，Bouknight提出了第一个光反射模型1971年Gourand提出“漫反射模型插值”的思想，被称为Gourand明暗处理1975年，Phong提出了著名的简单光照模型- Phong模型实体造型技术英国剑桥大学CAD小组的Build系统美国罗彻斯
7、特大学的PADL-1系统,历史追溯,80年代1980年Whitted提出了一个光透视模型-Whitted模型，并第一次给出光线跟踪算法的范例，实现Whitted模型1984年，美国Cornell大学和日本广岛大学的学者分别将热辐射工程中的辐射度方法引入到计算机图形学中图形硬件和各个分支均在这个时期飞速发展,历史追溯,90年代：微机和软件系统的普及使得图形学的应用领域日益广泛。标准化、集成化、智能化多媒体技术、人工智能、科学计算可视化、虚拟现实三维造型技术,历史追溯,ACM SIGGRAPH会议小知识全称 “the Special Interest Group on Computer Graph
8、ics and Interactive Techniques”60年代中期，由Brown 大学的教授Andries van Dam (Andy) 和IBM公司的Sam Matsa发起1974年，在Colorado大学召开了第一届SIGGRAPH 年会，并取得了巨大的成功每年只录取大约50篇论文,历史追溯,硬件发展,图形显示器的发展 图形显示器是计算机图形学中关键的设备 60年代中期：画线显示器（亦称矢量显示器） 需要刷新。设备昂贵，限制普及 60年代后期：存储管式显示器 不需刷新，价格较低，缺点是不具有动态修改 图形功能，不适合交互式。,硬件发展,70年代初，刷新式光栅扫描显示器出现，大大地推
9、动了交互式图形技术的发展。以点阵形式表示图形，使用专用的缓冲区存放点阵，由视频控制器负责刷新扫描。,图形显示设备的发展：,画线显示器（矢量显示器/随机扫描显示器）,存储管式显示器,刷新式光栅扫描显示器,硬件发展,图形输入设备的发展第一阶段：控制开关、穿孔纸等等第二阶段：键盘第三阶段：二维定位设备，如鼠标、光笔、图形输入板、触摸屏等等，语音第四阶段：三维输入设备（如空间球、数据手套、数据衣），用户的手势、表情等等第五阶段：用户的思维,第一章 绪论,1.1 研究内容1.2 发展历史1.3 计算机图形学的应用及研究前沿,1.3计算机图形学的应用及研究前沿,计算机图形学的应用,图形用户界面介于人与计算
10、机之间，人与机器的通信。人机界面（HCI）：软件硬件发展：由指示灯和机械开关组成的操纵界面由终端和键盘组成的字符界面（80年代）由多种输入设备和光栅图形显示设备构成的图形用户界面（GUI）（90年代）。PC，工作站，WIMP(W-windows、I-icons、M-menu、P-pointing devices)界面，所见即所得VR技术（发展方向）,计算机辅助设计与制造（CAD/CAM）,-CAD/CAM是计算机图形学在工业界最广泛、最活跃的应用领域飞机、汽车、船舶的外形的设计发电厂、化工厂等的布局土木工程、建筑物的设计电子线路、电子器件的设计设计结果直接送至后续工艺进行加工处理，如波音777
11、飞机的设计和加工过程,奥迪效果图和线框图,计算机辅助设计与制造（CAD/CAM）,基于工程图纸的三维形体重建定义：从二维信息中提取三维信息，通过对这些信息进行分类、综合等一系列处理，在三维空间中重新构造出二维信息所对应的三维形体，恢复形体的点、线、面及其拓扑关系，从而实现形体的重建优势：可以做装配件的干涉检查、以及有限元分析、仿真、加工等后续操作，代表CAD技术的发展方向,工程图及其三维重建结果1,工程图及其三维重建结果2,可视化,科学计算可视化(Scientific Visualization)海量的数据使得人们对数据的分析和处理变得越来越难，用图形来表示数据的迫切性与日俱增1986年，美国
12、科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（Visualization in Scientific Computing）”科学计算可视化广泛应用于医学、流体力学、有限元分析、气象分析当中,可视化,在医学领域，可视化有着广阔的发展前途是机械手术和远程手术的基础将医用CT扫描的数据转化为三维图象，帮助医生判别病人体内的患处由CT数据产生在人体内漫游的图象可视化的前沿与难点可视化硬件的研究实时的三维体绘制体内组织的识别分割Segmentation,真实感图形实时绘制与自然景物仿真,计算机中重现真实世界的场景叫做真实感绘制真实感绘制的主要任务是模拟真实物体的物理属性，简单的说
13、就是物体的形状，光学性质，表面的纹理和粗糙程度，以及物体间的相对位置，遮挡关系等等,真实感图形实时绘制与自然景物仿真,光照模型简单光照模型整体光照模型绘制方法光线跟踪辐射度加速算法包围体树、自适应八叉树等等,地理信息系统（GIS）,建立在地理图形之上的关于各种资源的综合信息管理系统。数字地球，地形数据作为载体。军事，政府决策，旅游，资源调查。,娱乐,电脑游戏实时性逼真性蕴含了先进的图形处理技术电视广告，节目片头，科教演示（CAI） Quake III，“古墓丽影”，“侏罗纪公园”、“皇帝的新衣”、完美风暴 MAYA, 3D-MAX, SOFTIMAGE,多媒体,在计算机控制下，对多种媒体信息进
14、行生成、操作、表现、存储、通信、或集成的信息系统其中媒体至少应包括一种“连续媒体”或一种“离散媒体”。计算机处理的常见媒体：文本、图形、图像、语音、音频、视频、动画特点：媒体的多样性、操作的交互性、系统的集成性CAI， 娱乐。,Virtual Reality（虚拟现实、灵境）,Virtual Reality 或称虚拟环境（Virtual Environment)是用计算机技术来生成一个逼真的三维视觉、听觉、触觉或嗅觉等感觉世界，让用户可以从自己的视点出发，利用自然的技能和某些设备对这一生成的虚拟世界客体进行浏览和交互考察。输入输出设备,虚拟现实（Virtual Reality简称VR）,虚拟现
15、实是指用立体眼镜、传感手套等一系列传感辅助设施来实现的一种三维现实，人们通过这些设施以自然的方式（如头的转动、手的运动等）向计算机送入各种动作信息，并且通过视觉、听觉以及触觉设施使人们得到三维的视觉、听觉等感觉世界。随着人们不同的动作，这些感觉也随之改变。,QuickTime技术简介,QuickTime是苹果公司开发的新一代虚拟现实技术。它是一种基于静态图像处理的，在微机平台上能够实现的初级虚拟现实技术。它的出现使得以往专业实验室中成本昂贵的虚拟现实技术的应用普及有了广阔的前景。 假定我们在一室空间进行观察，室内空间一般有六个面，如果我们获取了这六个面的许多不同距离，不同方位的实景照片并将它们
16、按照相互的关系有机连接起来，就可以在视觉上形成这个房间整个空间的整体认识，这就是全景概念。,当前研究热点,真实感图形实时绘制物体网格模型的面片简化：对网格面片表示的模型，在一定误差的精度范围内，删除点、边、面，从而简化所绘制场景的复杂度，加快图形绘制速度基于图象的绘制(IBR，Image Based Rendering)：完全摒弃传统的先建模，然后确定光源的绘制的方法。它直接从一系列已知的图象中生成未知视角的图象，适用于野外极其复杂场景的生成和漫游,野外自然景物的模拟野外场景远远复杂于室内场景，绘制难度更大，方法更趋多样化主要绘制山、水、云、树、草、火等等绘制火的粒子系统（Particle S
17、ystem），基于生理模型的绘制植物的方法，绘制云的细胞自动机方法等,由清华大学自然景物平台生成的野外场景,日本Yoshinori Dobashi等人绘制的真实感云,Xfrog3.0生成的挪威云杉,与计算机网络技术的紧密结合,远程医疗与诊断远程导航与维修远程教育,计算机动画,计算机动画近十多年来取得了很大的发展，已渗透到人们生活的各个角落商业广告、影视特技/片头、动画片教育、军事、飞行模拟等分类二维动画图象变形形状混合,计算机动画,三维动画关键帧动画变形物体的动画过程动画关节动画与人体动画,基于特征的图象变形（猫变虎）,用户接口,用户接口是人们使用计算机的第一观感。一个友好的图形化的用户界面能
18、够大大提高软件的易用性图形学已经全面融入计算机的方方面面，很多软件几乎可以不看任何说明书，而根据它的图形、或动画界面的指示进行操作,用户接口,目前几个大的软件公司都在研究下一代用户界面，开发面向主流应用的、自然、高效多通道的用户界面。研究多通道语义模型、多通道整合算法及其软件结构和界面范式是当前用户界面和接口方面研究的主流方向，而图形学在其中起主导作用。,计算机艺术,用计算机软件从事艺术创作二维平面的画笔程序（如CorelDraw，Photoshop，PaintShop）图表绘制软件（如Visio）三维建模和渲染软件包（如3DMAX，Maya）、以及一些专门生成动画的软件（如Alias，Sof
19、timage）,计算机艺术,优点：提供多种风格的画笔画刷提供多种多样的纹理贴图，甚至能对图象进行雾化，变形等操作可以任意修改，取消败笔不足：无法达到传统绘画中风格化的 艺术效果很难得到有素描效果、油画效果的艺术品,计算机艺术,非真实感绘制（NPR，Non-Photorealistic Rendering）用于模拟艺术效果，研究方法有别于真实感图形学钢笔素描的生成钢笔素描产生于中世纪，从19世纪开始成为一门艺术20世纪90年代开始研究用计算机模拟中国国画与书法的生成,Georges Winkenb1ach绘制的壶和碗(Siggraph96),Salisbury绘制的茶壶(Siggraph97),
20、Salisbury绘制的熊(Siggraph97),Oliver Deussen绘制的素描树(Siggraph2000),第二讲,图形系统,计算机图形硬件简介,图形输入设备 1 向量型图形输入设备 它采取跟踪轨迹、记录坐标点的方法输入图形。常用的向量型图形输入设备有数字化仪、鼠标器、光笔等。2 光栅扫描型图形输入设备 它采取远行扫描、按一定密度采样的方式输入图形，输入数据为一灰度图。这方面的研究已逐步达到实用阶段。常用的光栅扫描型图形输入设各有扫描仪和摄像机。栅格数据经过图形识别可以转换为矢量图形 。,计算机图形硬件简介,图形输出设备 图形输出设备是以纸、胶片、塑料薄膜等物质为介质，输出入眼可
21、视并能长期保存的图形的计算机外部设备。1 向量型设备作画机构随着图形的输出形状而移动并成像。如笔式绘图仪。2 光栅扫描型设备作画机构按光栅矩阵方式扫描整张图面，并按输出内容对图形成像。光栅扫描型输出设备包括点阵式打印机、热敏印刷机、静电印刷机、喷墨印刷机以及激光打印机等。,计算机图形硬件简介,常用图形显示设备 1 阴极射线管阴极射线管的技术指标主要有两条，一是分辨率，二是显示速度。 2 显示器显示器有随机扫描显示器、存储管式显示器、光栅扫描式显示器、液晶显示器、等粒子显示器等。,第三讲,VC+开发环境,VC+开发环境,1 VC+ 6.0是一个集成开发环境，它以C+语言为基础，实施面向对象编程。
22、 2 VC+ 6.0 的集成环境能完成绝大多数编程事务，包括菜单设置、图标绘制、对话窗口设置、工具按钮以及帮助文件的设置等等。3 VC+ 6.0 的导航功能遍及各个方面，能为编程人员提供快速的原型。4 VC+ 6.0 能实现不同层次的编程，从底层的面向硬件的编程到高级的各种应用集成。,VC+程序的基本架构,程序入口(App)框架类(Main/ChildFrame)文档类(Doc)负责数据的存取视图类(View)-负责信息的展示资源（对话框、菜单等）,VC+程序的基本架构,程序入口(App)WinMain函数隐藏在应用程序框架内部。类CExamApp的对象代表了一个应用程序。定义了一个单独的全局
23、CExamApp对象theApp。基类CWinApp。应用程序启动，首先调用WinMain函数，这个函数就查找该应用程序的全局构造对象theApp,VC+程序的基本架构,框架类(Main/ChildFrame)CMainFram应用程序的主框架窗口。当构造函数调用基类CFrameWnd的Create函数时，Windows将创建具体的窗口结构。主框架窗口包括标题栏、菜单栏。而工具栏窗口、状态栏窗口和视图窗口则占据着主框架窗口的客户区域。,VC+程序的基本架构,框架类(Main/ChildFrame),VC+程序的基本架构,文档类(Doc)负责数据的存取Microsoft在设计基础类库时，考虑到把
24、数据与它的显示分离开，于是就采用文档类和视类结构来实现。数据的存储和加载由文档类来完成，数据的显示和修改则由视类来完成，从而把数据管理和显示方法分离开来。,VC+程序的基本架构,视图类(View)-负责信息的展示,VC+程序的基本架构,资源（对话框、菜单等）包括对话框、菜单、快捷键、图标等。对话框：模式对话框和无模式对话框,VC+程序的基本架构,Frame、View、Document是互相联系的。如SDI程序，CMainFrame调用GetActiveView获得CView而CView可以调用GetDocument获得CDocument。如果已知CDocument，可以使用GetFirstVi
25、ewPosition获得第一个相关的CView，然后使用GetNextView获得下一个的CView。,消息处理与交互式绘图,Windows应用程序具有俘获各种操作和事件的能力，并提供相应的机会对之进行反应，这实质上是一个消息处理机制，按消息的级别和到达的次序进行相应的处理。交互式绘图一般要求对鼠标/键盘的操作（MouseClick/MouseMove等）进行反应，并通过获取相应信息来建立相应的图形。CDC类一包括用于图形绘制的全部函数和操作。OpenGL提供了用于三维图形实体设计的全部函数和操作。,Windows系统把应用程序的所有输入传入给应用程序窗口，每一个窗口都有一个称作窗口过程的函数
26、，当窗口有输入时Windows系统要调用它，窗口过程处理输入并把控制返回给Windows。Windows系统以消息的形式把输入传给窗口过程，消息是由Windows系统或应用程序产生的，Windows系统对于每一个输入事件都要产生消息-例如键盘、鼠标的动作。Windows系统为了响应应用程序给系统带来的变化也会产生消息-例如应用程序改变了系统字体或改变了一个窗口的大小。应用程序可以通过产生消息指导它自己的窗口来完成某项任务，或是与其他应用程序的窗口进行通信。消息有六个参数： typedef struct tagMSG HWND hwnd; UINT message; WPARAM wParam;
27、 LPARAM lParam; DWORD time; POINT pt; MSG;,消息处理与交互式绘图,目的窗口(hwnd):,接收消息的窗口，也就是那一个窗口的窗口过程将被调用。,消息标志(message):,一个命名的常量，用来标志消息的目的，也就是消息的含义。如果窗口过程收到一条消息，它就通过消息标志来决定如何处理这条消息。,消息的附加内容，具体的含义取决于具体消息标志message。参数分为高低位。消息参数可以是一个整数、紧缩的位标志、一个含有附加数据结构的指针等等。,参数1(wParam):,消息处理与交互式绘图,参数2(lParam):,消息的附加内容，具体的含义取决于具体消息
28、标志message。参数分为高低位。消息参数可以是一个整数、紧缩的位标志、一个含有附加数据结构的指针等等。,消息发出的时间。,分发时间(time):,光标位置(pt):,消息发生时鼠标光标的位置。以设备坐标系定位。,消息处理与交互式绘图,交互绘图实例,Scribble线条的任意绘制，主要是跟踪鼠标的操作。,几个基本的图形操作函数,CDC类-设备类，能提供图形、文本等的输出设备。 CDC类里包含了大量的基本图形函数，包括线型、颜色、填充模式、位图等的设置，以及点、线、多变形等各种基本图形绘制函数，而其中最为基本的函数是SetPixel，它是其他函数的实现基础。以下将重点介绍几个基础函数。RGB
29、函数，根据提供的三原色参数合成一个颜色，如RGB(255,0,0)即合成红色，返回类型通常为以长整型，且以COLORREF类型表示。,几个基本的图形操作函数,/* SetPixel函数的使用COLORREF SetPixel( int 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);,几个基本的图形操作函数,/-/* C
30、Pen类的使用 BOOL CreatePen( int nPenStyle, int nWidth, COLORREF crColor );-nPenStyle:PS_SOLID 实线PS_DASH 短线PS_DOT 点*/,几个基本的图形操作函数,CPen apen;if (apen.CreatePen(PS_SOLID,2,RGB(255,0,0)CPen* odlpen=pDC-SelectObject(,几个基本的图形操作函数,/* CBrush类的使用BOOL CreateSolidBrush( COLORREF crColor );BOOL CreateHatchBrush( in
31、t nIndex, COLORREF crColor );-nIndex:HS_BDIAGONAL HS_CROSSHS_DIAGCROSS HS_FDIAGONALHS_HORIZONTALHS_VERTICAL*/,几个基本的图形操作函数,CBrush abrush;if (abrush.CreateSolidBrush(RGB(0,255,0)CBrush* oldbrush=pDC-SelectObject(,几个基本的图形操作函数,对于任何采用SetPixel绘图的函数，必须包括两个基本的参数，即设备参数CDC *pDC, COLORREF aColorvoid Cmap:DrawL
32、ineBySetpixel(CDC *pDC, COLORREF aColor)int i=0;for (i=1;iSetPixel(i,i*3,aColor);return;,第四讲,基本图形元素的生成算法,基本图形元素,点、线、圆（圆弧）、区域填充和字符等。基本图形生成算法：速度、质量，通常情况下速度是第一位的，因为算法通常被调用很多次。,点的生成,点是最基本的图形，通常情况下，点由一个像素（设置其显示缓冲器的灰度值）来描述。对于光栅显示器，象素点的多少决定了显示器的分辨率。横向分辨率通常为320、640、1024，8 的倍数，纵向通常为200、480、1024。,直线的生成,在光栅显示器
33、的荧光屏上生成一个对象，实质上是往帧暂存寄存器的相应单元中填入数据。画一条从(x1,y1)到(x2,y2)的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。基本要求：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),栅格交点
34、表示象素点位置,。,。,。,。,数值微分(DDA)法,基本思想已知过端点P0 (x0, y0), P1(x1, y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,数值微分(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值是用前一步的值加上一个增
35、量来获得，则称为增量算法。DDA算法就是一个增量算法。,数值微分(DDA)法,void DDALine(int x0,int y0,int x1,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.5000+0.5100.4+0
36、.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,直线生成算法中点法,讨论情况（直线斜率限定在0-1之间）:对于任意直线方程F(x,y)=ax+by+c=0,在高斯平面上将平面分为两部分，上半部分F(x,y)0，而下半部分F(x,y)0。如果想要判定某个平面点在直线的上方还是下方，只需要将其坐标代入，而后看F(x,y)的值即可判定其位置。,中点画线法,原理：,假定直线斜率0K P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与
37、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;此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b
38、(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 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提
39、高效率。,中点画线法,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 */,中点画线法,例：用中点画线法P0(0,0) P1(5,2)a=y0
40、-y1=-2 b=x1-x0=5d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6i xi yid1 0 012 1 0-33 2 134 3 1-15 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,直线Bresenham算法,直线Bresenham算法,作业及答案,1 DDA法生成直线的基本原理是什么
41、?2 为什么说Bresenham画圆的算法效率较高?3 为什么说直线生成算法是二维图形生成技术的基础？4 准备下一节课实验的内容,圆的基本知识,圆的位图,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为： X2 + Y2 = R2,圆的基本知识,圆弧扫描算法,X2 + Y2 = R2Y = Sqrt(R2 - X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。,圆的逐点比较法算法,用逆时针画第一象限中AB圆弧的过程如下：从始点（Xa，Ya）开始，首先向(-X方向)圆内走一步，然后比较判断结果，落在圆内则向Y方向走
42、一步，依次类推，一直到达圆外为止当判断结果落在圆外时，向X方向走一步，直到再次到达圆内为止当画到终点以（Xb，Yb）时，终止比较，结束。,圆的逐点比较法算法,圆的角度DDA法,x = x0 + Rcos y = y0 + Rsindx =- Rsinddy = Rcosdxn+1 =x n + dxy n+1 =y n + dyxn+1 = x n + dx = x n - Rsind =x n - (y n - y 0 )dy n+1 = y n + dy = y n + Rcosd =y n + (x n - x 0 )d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后
43、取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,生成圆弧的正负法,原理：,设圆的方程为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 = xi， yi+1 = yi - 1;这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，故称正负法。快速计算的关键是F(xi,
44、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 +12、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +13、初始值：略,中
45、点画圆法,利用圆的对称性，只须讨论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）= 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.,