1、 计算机图形学课本课本:计算机图形学计算机图形学原理、方法及原理、方法及应用应用 潘云鹤潘云鹤 高等教育出版社高等教育出版社实验参考书：实验参考书：计算机图形学课程设计计算机图形学课程设计唐敏唐敏 童若锋童若锋 浙江大学出版社浙江大学出版社 计算机图形学课程目标：课程目标：1.掌握计算机图形学基本原理和方法掌握计算机图形学基本原理和方法2.培养实际动手能力，掌握使用培养实际动手能力，掌握使用OpenGL进进行三维图形的构建、显示等的编程技巧行三维图形的构建、显示等的编程技巧3.培养对计算机图形学的兴趣及独立解决培养对计算机图形学的兴趣及独立解决问题的习惯和能力问题的习惯和能力 计算机图形学简介
2、 计算机图形学的概念和主要内容 计算机图形学的发展 计算机图形学的应用 计算机图形学硬件简介1.1 计算机图形学的概念计算机图形学的概念 计算机图形学计算机图形学：是研究怎样用计算机表示、生成、处理和显示图形的一门学科。图形:指物体的轮廓、形状或外部的界限客观存在的物体（桌、椅、山、水、人）几何图形（点、线、面）1.1 计算机图形学的概念计算机图形学的概念1.1 计算机图形学的概念计算机图形学的概念 用计算机表示表示图形：给出合适的数据结构来存放图形给出合适的数据结构来存放图形 点：Point3D double x;double y;double z;长方体:cuboid LCS3D loca
3、l;double x;double y;double z;1.1 计算机图形学的概念计算机图形学的概念 桌子，椅子：？任意多面体：？眼镜：？山，水，云，雾：？猫，狗，虫，人：？评价图形表示的好坏的标准：1.表达能力 2.存储量 3.易生成、处理、显示1.1 计算机图形学的概念计算机图形学的概念 用计算机生成生成图形：将上述数据结构实例化（交互手段）用计算机处理处理图形：图形变换、变形（位置，形状）图形A 图形B用计算机显示显示图形：图像：1.绘制、摄制或印制的形象。2.图形在媒介上的投影。照片：镜子中的形象，屏幕上的形象1.1 计算机图形学的概念计算机图形学的概念1.1 计算机图形学的概念计算
4、机图形学的概念Pixels:象素象素是计算机屏幕用来显示图象的最小单位12最终 Resolution:分辨率 分辨率指屏幕或打印的图象上的点的密度，分辨率越高，图越清晰。分辨率用DPI度量(Dots per Inch)1.1 计算机图形学的概念计算机图形学的概念1.1 计算机图形学的概念计算机图形学的概念 Pixel Depth（象素位数，颜色位数，颜色深象素位数，颜色位数，颜色深度）度）Pixel Depth（Color Depth）每个象素点的bit数.Pixel Depth越大,每个象素点的颜色越丰富.彩色图象的效果取决于分辨率.Pixel Depth越大,图象文件越大.1.1 计算机图
5、形学的概念计算机图形学的概念 用计算机显示图形：计算机:本质：图像：颜色值（RGB），没有物体的概念。图形：）。物体（形状、外表属性、客观世界：用计算机表示、生成、处理和显示图形.显示图形-图像Display,rendering光线刺激视网膜神经感知物体-视觉形像原始Lena图像 直方图均衡后的Lena图像 1.1 计算机图形学的概念计算机图形学的概念 几个计算机图形学的相关概念几个计算机图形学的相关概念：图像处理图像处理：将客观世界中原来存在的物体的影像处理成新的数字化图像的相关技术，如CT扫描、X射线探伤等。模式识别模式识别 ：对所输入的图像进行分析和识：对所输入的图像进行分析和识别，找出
6、其中蕴涵的内在联系或抽象模型，别，找出其中蕴涵的内在联系或抽象模型，如邮政分拣、地形地貌识别等如邮政分拣、地形地貌识别等 。计算几何计算几何 ：研究几何模型和数据处理的学：研究几何模型和数据处理的学科，探讨几何形体的计算机表示、分析和科，探讨几何形体的计算机表示、分析和综合综合 。数数字字图图像像数数据据模模型型计算机图形学计算机图形学模式识别模式识别计算几何计算几何图像处理图像处理1.1 计算机图形学的概念计算机图形学的概念1.2 计算机图形学的发展计算机图形学的发展 计算机图形学的研究起源于美国麻省理工学院计算机图形学的研究起源于美国麻省理工学院,从从20世纪世纪50年代初期到年代初期到6
7、0年代中期，美国麻省理工学院积极从事现年代中期，美国麻省理工学院积极从事现代计算机辅助设计代计算机辅助设计/制造技术的开拓性研究。制造技术的开拓性研究。1952年，在该校诞生了世界上第一台数控铣床的原型。年，在该校诞生了世界上第一台数控铣床的原型。随后，麻省理工学院发展了随后，麻省理工学院发展了APT，这演变成国际上最，这演变成国际上最通用的加工编程工具。通用的加工编程工具。1964年，孔斯年，孔斯(Steve Coons)在麻省理工学院提出了用在麻省理工学院提出了用小块曲面片组合表示自由型曲面时使曲面片边界达到小块曲面片组合表示自由型曲面时使曲面片边界达到 任意高次连续阶的理论，此方法得到工
8、业界和学术界任意高次连续阶的理论，此方法得到工业界和学术界 的极大推崇，称之为孔斯曲面。的极大推崇，称之为孔斯曲面。1962年第一台光笔交互式图形显示器在美国麻省理工年第一台光笔交互式图形显示器在美国麻省理工学院林肯实验室研制成功，学院林肯实验室研制成功，在美国工业界，研制交互式图形显示器的工作也同时在美国工业界，研制交互式图形显示器的工作也同时开展，其中所起作用最重要的是开展，其中所起作用最重要的是IBM公司公司 在在1964年秋，年秋，IBM公司推出了公司推出了IBM 2250显示器。显示器。洛克希德飞机公司利用洛克希德飞机公司利用IBM 2250施行开发的施行开发的CAD/CAM绘图加工
9、系统，成为当时绘图加工系统，成为当时IBM主机上应主机上应用最广的用最广的CAD/CAM软件。软件。IBM 2250在在1978年前后改型为年前后改型为IBM 3250，1984年年又改型为又改型为IBM 5080，采用光栅扫描技术，采用光栅扫描技术。20世纪世纪60年代末和年代末和70年代初，美国年代初，美国Tektronix公司公司发展了存储管技术。发展了存储管技术。由于大规模集成电路技术的发展和专用图形处理由于大规模集成电路技术的发展和专用图形处理芯片的出现，光栅扫描型显示器的质量越来越好，芯片的出现，光栅扫描型显示器的质量越来越好，价格越来越低，已成为图形显示器的常规形式。价格越来越低
10、，已成为图形显示器的常规形式。1.2 计算机图形学的发展计算机图形学的发展1.2 计算机图形学的发展计算机图形学的发展 在图形显示技术发展的历程中，需要强调两家公司的产品，在图形显示技术发展的历程中，需要强调两家公司的产品，这就是这就是Evans&Sutherland公司的公司的PS 300型和型和Silicon Graphics公司的公司的IRIS型显示设备。型显示设备。PS 300采用数据驱动式原理；图形处理中的矩阵运算和其他基本算法使用3个位片处理机组成的流水线。三维物体轮廓线的显示亮度可以随距离远近而变化，离眼睛越远的部分线条越淡，这样可更好地体现出立体图 的真实感。Silicon G
11、raphics公司的IRIS工作站采用数字成像工作原理。此后，其他公司纷纷效仿。这种持续不断的提高显示画面质量、加快交互速度的努力会继续进行，必将进一步推动计算机图形学技术的飞速发展。Spacewars:first computer graphics game(MIT 1961)SketchPad:first interactive graphics(1961)Whirlwind:early graphics using VectorScope(1951)first CAD system(IBM 1959)1.2 计算机图形学的发展计算机图形学的发展1.2 计算机图形学的发展计算机图形学的发展
12、EGACGAVGA 1987 ATIGRAPHICS CARD 1991 ATI MACH8Video Card 19943D Accelerator CARD 1994GPU 1999CUDA Geforce8 NVidia 200823ShaderShader Model ModelGPUGPU代表代表显卡显卡时代时代特点特点 19991999年第一代年第一代NV NV Geforce256Geforce256DirectX 7DirectX 71999200119992001GPUGPU可以处理顶点的矩阵变换和进行光照计算可以处理顶点的矩阵变换和进行光照计算（T<&L），操作固定，功
13、能单一，不具备可编程），操作固定，功能单一，不具备可编程性性SM 1.0SM 1.020012001年第二代年第二代NV Geforce3NV Geforce3DirectX 8DirectX 8将图形硬件流水线作为流处理器来解释，顶点部将图形硬件流水线作为流处理器来解释，顶点部分出现可编程性，像素部分可编程性有限（访问分出现可编程性，像素部分可编程性有限（访问纹理的方式和格式受限，不支持浮点）纹理的方式和格式受限，不支持浮点）SM 2.0SM 2.02003 2003 年年ATI R300ATI R300和第三代和第三代NV NV Geforce FXGeforce FXDirectX Di
14、rectX 9.0b9.0b顶点和像素可编程性更通用化，像素部分支持顶点和像素可编程性更通用化，像素部分支持FP16/24/32FP16/24/32浮点，可包含上千条指令，处理纹理浮点，可包含上千条指令，处理纹理更加灵活：可用索引进行查找，也不再限制更加灵活：可用索引进行查找，也不再限制0,10,1范围，从而可用作任意数组（这一点对通用计算范围，从而可用作任意数组（这一点对通用计算很重要）很重要）SM 3.0SM 3.020042004年年第四代第四代NV NV Geforce 6Geforce 6和和 ATI X1000ATI X1000DirectX DirectX 9.0c9.0c顶点程
15、序可以访问纹理顶点程序可以访问纹理VTFVTF，支持动态分支操作，支持动态分支操作，像素程序开始支持分支操作（包括循环、像素程序开始支持分支操作（包括循环、if/elseif/else等），支持函数调用，等），支持函数调用，6464位浮点纹理滤波和融合，位浮点纹理滤波和融合，多个绘制目标多个绘制目标SM 4.0SM 4.020072007年年第五代第五代NV G80NV G80和和ATI R600ATI R600DirectX 10DirectX 102007200920072009统一渲染架构，支持统一渲染架构，支持IEEE754IEEE754浮点标准，引入浮点标准，引入Geometry S
16、haderGeometry Shader（可批量进行几何处理），指（可批量进行几何处理），指令数从令数从1K1K提升至提升至64K64K，寄存器从，寄存器从3232个增加到个增加到40964096个，纹理规模从个，纹理规模从16+416+4个提升到个提升到128128个，材质个，材质TextureTexture格式变为硬件支持的格式变为硬件支持的RGBERGBE格式，最高纹格式，最高纹理分辨率从理分辨率从20482048*20482048提升至提升至81928192*81928192SM 5.0SM 5.020092009年年ATI RV870ATI RV870和和20102010年年NV N
17、V GF100GF100DirectX 11DirectX 1120092009明确提出通用计算明确提出通用计算API Direct ComputeAPI Direct Compute概念和概念和Open CLOpen CL分庭抗衡，以更小的性能衰减支持分庭抗衡，以更小的性能衰减支持IEEE754IEEE754的的6464位双精度浮点标准，硬件位双精度浮点标准，硬件TessellationTessellation单元，更好地利用多线程资源加速多单元，更好地利用多线程资源加速多个个GPUGPU24新进展 随着计算机图形学的不断发展，它的应用范围也日趋随着计算机图形学的不断发展，它的应用范围也日趋
18、广泛。目前，计算机图形学应用领域主要有以下几种广泛。目前，计算机图形学应用领域主要有以下几种:3 计算机动画和艺术计算机动画和艺术 1 计算机辅助设计与制造计算机辅助设计与制造(CAD/CAM)2 地形地貌和自然资源图地形地貌和自然资源图 7 用户接口用户接口 4 分析计算及视图中的应用分析计算及视图中的应用 5 游戏游戏 6 虚拟现实虚拟现实 （Virtual RealityVirtual Reality）1.3 计算机图形学的应用计算机图形学的应用1.1.计算机辅助设计与制造计算机辅助设计与制造(CAD/CAM)CAD机械机械CAD电路电路CAD建筑建筑CAD服装服装CAD。机械CAD系统
19、所生成的零件、装配件 1.3 计算机图形学的应用计算机图形学的应用1.1.计算机辅助设计与制造计算机辅助设计与制造(CAD/CAM)续续二维绘图二维绘图（AutoCAD）三维造型三维造型（Pro/E,UG,CATIA）CAMCAE发展方向发展方向:Computer Aided Drawing Design 概念设计概念设计 三维造型三维造型 虚拟装配虚拟装配协同设计工具协同设计工具1.3 计算机图形学的应用计算机图形学的应用2.2.地形地貌和自然资源图地形地貌和自然资源图 我国正在筹建国土基础信息系统，此系统是国家我国正在筹建国土基础信息系统，此系统是国家 经济信息系统的组成部分。经济信息系统
20、的组成部分。三维的地形地貌图三维的地形地貌图 1.3 计算机图形学的应用计算机图形学的应用网上地图网上地图GIS+GPS1.3 计算机图形学的应用计算机图形学的应用2.2.地形地貌和自然资源图地形地貌和自然资源图 续续计算机动画已经成为计算机图形学的一个分支，并逐计算机动画已经成为计算机图形学的一个分支，并逐步进入实用阶段。步进入实用阶段。1996 IndependenceDay 因其可视效果获因其可视效果获Oscar.3.3.计算机动画和艺术计算机动画和艺术 1.3 计算机图形学的应用计算机图形学的应用3.3.计算机动画和艺术计算机动画和艺术 续续 1.3 计算机图形学的应用计算机图形学的应
21、用4.4.分析计算及可视化分析计算及可视化既可用二维曲线图表和三维模型，也有彩色高维几何表示既可用二维曲线图表和三维模型，也有彩色高维几何表示 1.3 计算机图形学的应用计算机图形学的应用1.3 计算机图形学的应用计算机图形学的应用4.分析计算及可视化分析计算及可视化目前图形硬件发展的动力所在目前图形硬件发展的动力所在。“Tekken Tag Tournament”Playstation 2 1.3 计算机图形学的应用计算机图形学的应用5.5.游戏游戏 6.6.虚拟现实虚拟现实 （Virtual RealityVirtual Reality）飞行等模拟训练飞行等模拟训练,游戏。游戏。1.3 计
22、算机图形学的应用计算机图形学的应用6.6.虚拟现实虚拟现实 （Virtual RealityVirtual Reality）虚拟装配虚拟装配1.3 计算机图形学的应用计算机图形学的应用7.7.用户界面用户界面 Macintosh微机首先在商品化产品上用形象的图微机首先在商品化产品上用形象的图形表示操作命令，使得普通用户也会用计算机画图、形表示操作命令，使得普通用户也会用计算机画图、作日常计算，打破了人们对操作计算机所持的神秘作日常计算，打破了人们对操作计算机所持的神秘感。图文形式相结合大大改善了计算机交互操作的感。图文形式相结合大大改善了计算机交互操作的用户界面，开辟了计算机应用的很多新领域。
23、用户界面，开辟了计算机应用的很多新领域。Fastest browser on the Mac 1.3 计算机图形学的应用计算机图形学的应用常用的图形输入设备分为两种：常用的图形输入设备分为两种：向量型图形输入设备向量型图形输入设备 它采取跟踪轨迹、记录坐标点的方法输入图形。常用的有数字化仪、鼠标器、光笔等。光栅扫描型图形输入设备光栅扫描型图形输入设备 它采取逐行扫描、按一定密度采样的方式输入图形。常用的有扫描仪和摄像机。图形输入设备的功能可分为图形输入设备的功能可分为6类：类：确定点坐标即定位 确定一系列点的坐标即笔划 确定数值 进行选择 进行图形识别 识别字符串 1.4 计算机图形硬件介绍计
24、算机图形硬件介绍几种主要图形输入设备几种主要图形输入设备1.1.键盘键盘 2.2.鼠标鼠标 :光电式鼠标 机械式鼠标 3.3.光笔光笔 4.触摸屏触摸屏:电阻式和电容式 红外线式 声表面波式 5.5.扫描仪扫描仪:二维：扫描仪通过光电转换、点阵采样的方式，将 一幅画面变为数字图像 三维：三维物体的几何形状及表面颜色属性。1.4 计算机图形硬件介绍计算机图形硬件介绍美国CALCOMP公司生产的数字化仪1.4 计算机图形硬件介绍计算机图形硬件介绍图形输出设备介绍：图形输出设备介绍：光栅扫描式图形显示器光栅扫描式图形显示器 光栅扫描式图形显示器(简称光栅显示器)是画点设备，可看作是一个点阵单元发生器
25、，并可控制每个点阵单 元的亮度。光栅扫描式图形显示器的直线显示效果 它不能直接从单元阵列中的一个可编址的像素画一条直线到另一个可编址的像素，只能用尽可能靠近这条直线路径的像素点集来近似地表示这条直线。1.4 计算机图形硬件介绍计算机图形硬件介绍一个黑白光栅显示器的工作状况图一个黑白光栅显示器的工作状况图:在光栅图形显示器中，需要有足够的位面和帧缓冲存储器结合才能反映图形的颜色和灰度等级。具有颜色查找表的N位面灰度等级帧缓冲存储器 1.4 计算机图形硬件介绍计算机图形硬件介绍为了限制帧缓冲存储器的增加，可采用颜色查找表来提为了限制帧缓冲存储器的增加，可采用颜色查找表来提高灰度级别，如图所示高灰度
26、级别，如图所示:具有颜色查找表的N位面灰度等级帧缓冲存储器 1.4 计算机图形硬件介绍计算机图形硬件介绍彩色光栅显示器的工作状况图彩色光栅显示器的工作状况图:1.4 计算机图形硬件介绍计算机图形硬件介绍全色光栅显示器工作状况图全色光栅显示器工作状况图:1.4 计算机图形硬件介绍计算机图形硬件介绍配有颜色查找表的全色帧缓冲存储器配有颜色查找表的全色帧缓冲存储器:1.4 计算机图形硬件介绍计算机图形硬件介绍具有具有3个位面的帧缓冲存储器的颜色表个位面的帧缓冲存储器的颜色表:红(R)绿(G)蓝(B)黑(Black)000红(Red)100绿(Green)010蓝(Blue)001黄(Yellow)1
27、10青(Cyan)011紫(Magenta)101白(White)1111.4 计算机图形硬件介绍计算机图形硬件介绍 图形绘制设备图形绘制设备 图形显示设备只能在屏幕上产生各种图形，但在计算机图形学应用中还需把图形画在纸上。常用的图形绘制设备也称为硬复制设备，有打印机和绘图仪两种。喷墨打印机 激光打印机 静电绘图仪 是一种光栅扫描设备，它利用静电同极相斥、异 极相吸的原理。笔式绘图仪 分为滚筒式和平板式两种(5)快速成型机1.4 计算机图形硬件介绍计算机图形硬件介绍绘图机绘图机 1.4 计算机图形硬件介绍计算机图形硬件介绍End of the chapter 基本图形的生成与计算 直线的生成算
28、法 圆的生成算法 区域填充算法 字符的生成 图形求交 图形裁剪画一条从画一条从(x x1 1,y y1 1)到到(x x2 2,y y2 2)的直线，实质上是一个的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。发现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为直线光栅化。这过程也称为直线光栅化。连续性连续性 粗细、亮粗细、亮度要均匀度要均匀 像素逼近像素逼近待画直线待画直线 速度速度2.1 直线的生成算法直线的生成算法2.1 直线的生成算法直线的生成算法(x1,y1),(x2,y2)Question1:How?y=kx+bx1+1y=?,取整取整x1+2y=?
29、,取整取整x1+iy=?,取整取整Question2:How to speed up?假设假设 直线的起点坐标为直线的起点坐标为P P1 1(x(x1 1,y,y1 1)，终点坐标为，终点坐标为P P2 2(x(x2 2,y,y2 2)x x方向的增量为方向的增量为 x xx x2 2x x1 1 ；y y方向上增量为方向上增量为 y yy y2 2y y1 1 直线的斜率为直线的斜率为 k ky yx x 当当 x xy y 时，让时，让 x x 从从 x x1 1 到到 x x2 2 变化，每步递增变化，每步递增 1 1，那么，那么，x x 的变化可以表示为的变化可以表示为 x xi+1i
30、+1x xi i1 1 y y 的变化可以表示为的变化可以表示为 y yi+1i+1y yi ik k 用上式可求得图中直线用上式可求得图中直线 P P1 1P P2 2 和和 y y 向网格线的交点，但显示时要用舍入向网格线的交点，但显示时要用舍入 找到最靠近交点处的象素点耒表示。找到最靠近交点处的象素点耒表示。.1.直线直线DDA算法算法(Digital Differential Analyzer)Discussion1:What technique makes it faster?Discussion2:Is there any problem in the algorithm?How
31、to avoid it?当 xx d dy y?D Dx xD Dy y1a true 1 m1b false 1/m 12a true -1 m2b false -1/m 13a true -1 -m3b false -1/m -14a true 1 -m4b false 1/m -1表表2.1 82.1 8个象限中的坐标增量值个象限中的坐标增量值.1.直线直线DDA算法算法研究表中的数据，可以发现研究表中的数据，可以发现两个规律。两个规律。当当d dx x d dy y时时D Dx x=1=1，D Dy y=m m否则否则D Dx x=1/=1/m m，D Dy y =1=1 D Dx x
32、、D Dy y的符号与的符号与d dx x、d dy y的的符符号相同。号相同。算法描述如下：算法描述如下：dda_line(xa,ya,xb,yb,dda_line(xa,ya,xb,yb,c)c)int xa,ya,xb,yb,c;int xa,ya,xb,yb,c;float delta_x,delta_y,float delta_x,delta_y,x,y;x,y;int dx,dy,steps,k;int dx,dy,steps,k;dx=xbdx=xb xa;xa;dy=ybdy=yb ya;ya;if(abs(dx)abs(dy)if(abs(dx)abs(dy)steps=ab
33、s(dx);steps=abs(dx);else steps=abs(dy);else steps=abs(dy);delta_x=(float)dx/(float)steps;delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;delta_y=(float)dy/(float)steps;.1.直线直线DDA算法算法x=xa;x=xa;y=ya;y=ya;set_pixel(x,y,c);set_pixel(x,y,c);for(k=1;k=steps;k+)for(k=1;k00，则，则y yi i+1+1=y yi
34、i+1+1，否则，否则y yi i+1+1=y yi i。将式将式(2.1)(2.1)、(2.2)(2.2)、(2.3)(2.3)代入代入d d1 1 d d2 2，d1 d2=2y 2 yi-1=2dy/dx*xi+2dy/dx+2b-2yi-1再用再用d dx x乘等式两边，并以乘等式两边，并以P Pi i=(=(d d1 1 d d2 2)d)dx x代入上述等式，得代入上述等式，得 P Pi i=2=2x xi id dy y 2 2y yi id dx x+2d+2dy y+(2+(2b b 1)d1)dx x (2.4)(2.4)d d1 1 d d2 2是用以判断符号的误差。由于
35、在是用以判断符号的误差。由于在1 1a a象限，象限，d dx x总大于总大于0 0，所，所以以P Pi i仍旧可以用作判断符号的误差。仍旧可以用作判断符号的误差。P Pi i+1+1为为 P Pi i+1+1=2=2x xi i+1+1 d dy y 2 2y yi i+1+1 d dx x+2d+2dy y+(2+(2b b 1)d1)dx xP Pi i+1+1=P Pi i+2d+2dy y 2(2(y yi i+1+1 y yi i)d)dx x (2.5)2.5).1.直线直线Bresenham算法算法 求误差的初值求误差的初值P P1 1，可将，可将x x1 1、y y1 1和和
36、b b代入式代入式(2.4)(2.4)中的中的x xi i、y yi i而得到而得到 P P1 1=2d=2dy y d dx x 综述上面的推导，第综述上面的推导，第1 1a a象限内的直线象限内的直线BresenhamBresenham算法思想如下：算法思想如下：画点画点(x x1 1,y y1 1)，d dx x=x x2 2 x x1 1，d dy y=y y2 2 y y1 1，计算误差初值，计算误差初值P P1 1=2d=2dy y d dx x，i i=1=1；求直线的下一点位置求直线的下一点位置 x xi i+1+1=x xi i+1+1 如果如果P Pi i00，则，则y y
37、i i+1+1=y yi i+1+1，否则，否则y yi i+1+1=y yi i；画点画点(x xi i+1+1,y yi i+1+1)；求下一个误差求下一个误差P Pi i+1+1，如果，如果P Pi i00，则，则P Pi i+1+1=P Pi i+2d+2dy y 2d2dx x，否则，否则 P Pi i+1+1=P Pi i+2d+2dy y；i i=i i+1+1；如果；如果i id|dy|dx|dy|为分支，并分别将为分支，并分别将2 2a a、3 3a a象限的直线和象限的直线和3 3b b、4 4b b象限的直线变换到象限的直线变换到1 1a a、4 4a a和和2 2b b
38、、1 1b b象限方向去，以实象限方向去，以实现程序处理的简洁。现程序处理的简洁。.1.直线直线Bresenham算法算法2.2.1 基础知识基础知识 给出圆心坐标给出圆心坐标(x xc c,y yc c)和半径和半径r r，逐点画出一个圆周，逐点画出一个圆周的公式有下列两种：的公式有下列两种：直角坐标法直角坐标法(x x x xc c)2 2+(+(y y y yc c)2 2=r r2 2由上式导出：由上式导出：cc22()yyrxx当当x x x xc c从从 r r到到r r作加作加1 1递增时，就可以求递增时，就可以求出对应的圆周点的出对应的圆周点的y y坐标。坐标。但是这样求出的圆
39、周上的点是不均匀但是这样求出的圆周上的点是不均匀的，的，x x x xc c越大，对应生成圆周点之间越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆周距离也就越长。因此，所生成的圆不美观。的圆不美观。2.2 圆的生成算法圆的生成算法2.2.1 基础知识基础知识(续）续）极坐标法极坐标法x x=x xc c+r r cos cos，y y=y yc c+r r sin sin当当从从0 0到到作递增时，由此式便可求出圆周上均匀分布的作递增时，由此式便可求出圆周上均匀分布的360360个点的个点的(x x,y y)坐标。坐标。xi=xc+r cos(i*)yi=yc+r sin(i*)
40、利用圆周坐标的对称性，此利用圆周坐标的对称性，此算法还可以简化。将圆周分为算法还可以简化。将圆周分为8 8个象限个象限(图图2.3)2.3)，只要将第，只要将第1 1a a象象限中的圆周光栅点求出，其余限中的圆周光栅点求出，其余7 7部分圆周就可以通过对称法则部分圆周就可以通过对称法则计算出来。计算出来。图图2.3 2.3 圆心在圆心在(0,0)(0,0)点圆点圆周周生成时的对称变换生成时的对称变换2.2 圆的生成算法圆的生成算法x x=r r cos cosy y=r r sin sin2.2 圆的生成算法圆的生成算法xi=r cosiyi=r siniXi+1=r cos(i+)=r co
41、sicos-rsinisin=xicos-yisin Discussion 3:How to speed upDiscussion 3:How to speed up？=i*,i=0,1,2,3,.2.2.2 圆的圆的Bresenham算法算法 设圆的半径为设圆的半径为r r。先考虑圆心在。先考虑圆心在(0,0)(0,0)，并从，并从x x=0=0、y y=r r开始的顺时针方向的开始的顺时针方向的1/81/8圆周的生成过程。在这种情况下，圆周的生成过程。在这种情况下，x x每步增加每步增加1 1，从，从x x=0=0开始，到开始，到x x=y y结束。即有结束。即有x xi i+1+1=x
42、xi i+1+1相应的相应的y yi i+1+1则在两种可能中选择：则在两种可能中选择：y yi i+1+1=y yi i或者或者y yi i+1+1=y yi i 1 1选择的原则是考察精确值选择的原则是考察精确值y y是靠近是靠近y yi i还是还是靠近靠近y yi i 1(1(图图2.4)2.4)，计算式为计算式为y y2 2=r r2 2(x xi i+1)+1)2 2d d1 1=y yi i2 2 y y2 2=y yi i2 2 r r2 2+(+(x xi i+1)+1)2 2d d2 2=y y2 2(y yi i 1)1)2 2=r r2 2(x xi i+1)+1)2 2
43、(y yi i 1)1)2 2图图2.4 y的位置的位置 2.2 圆的生成算法圆的生成算法2.2.2 圆的圆的Bresenham算法算法(续）续）令令p pi i=d d1 1 d d2 2，并代入，并代入d d1 1、d d2 2，则有，则有 p pi i=2(=2(x xi i+1)+1)2 2+y yi i2 2+(+(y yi i 1)1)2 2 2 2r r2 2 (2.6)(2.6)p pi i称为误差。如果称为误差。如果p pi i00则则y yi i+1+1=y yi i，否则，否则y yi i+1+1=y yi i 1 1。p pi i的递归式为的递归式为 p pi i+1+
44、1=p pi i+4+4x xi i +6+2(+6+2(y yi i2 2+1+1 y yi i2 2)2(2(y yi i+1+1 y yi i)(2.7)(2.7)p pi i的初值由式的初值由式(2.6)(2.6)代入代入x xi i=0=0，y yi i=r r而得而得 p p1 1=3=3 2 2r r (2.8)(2.8)根据上面的推导，圆周生成算法思想如下：根据上面的推导，圆周生成算法思想如下：求误差初值，求误差初值，p p1 1=3=3 2 2r r，i i=1=1，画点，画点(0,(0,r r)；求下一个光栅位置，其中求下一个光栅位置，其中x xi i+1+1=x xi i
45、+1+1，如果，如果p pi i00则则y yi i+1+1=y yi i，否则否则y yi i+1+1=y yi i 1 1；画点画点(x xi i+1+1,y yi i+1+1)；计算下一个误差，如果计算下一个误差，如果p pi i00则则p pi i+1+1=p pi i+4+4x xi i+6+6，否则，否则p pi i+1+1=p pi i+4(+4(x xi i y yi i)+10)+10；i i=i i+1+1，如果，如果x x=y y则结束，否则返回步骤则结束，否则返回步骤2 2。2.2 圆的生成算法圆的生成算法2.2.2 圆的圆的Bresenham算法算法(续）续）圆的圆的
46、BresenhamBresenham算法的程序实现如下：算法的程序实现如下：circle(xc,yc,radius,c)circle(xc,yc,radius,c)int xc,yc,radius,c;int xc,yc,radius,c;int x,y,p;int x,y,p;x=0;x=0;y=radius;y=radius;p=3p=3 2 2*radiusradius；while(xy)while(xy)plot_circle_points(xc,yc,x,y,c);plot_circle_points(xc,yc,x,y,c);if(p0)p=p+4if(p0)p=p+4*x+6;x
47、+6;elseelsep=p+4p=p+4*(x(x y)+10;y)+10;y y=1;=1;x+=1;x+=1;if(x=y)if(x=y)plot_circle_points(xc,yc,x,y,c);plot_circle_points(xc,yc,x,y,c);2.2 圆的生成算法圆的生成算法2.2.2 圆的圆的Bresenham算法算法(续）续）plot_circle_points(xc,yc,x,y,c)plot_circle_points(xc,yc,x,y,c)int xc,yc,x,y,c;int xc,yc,x,y,c;set_pixel(xc+x,yc+y,c);set
48、_pixel(xc+x,yc+y,c);set_pixel(xcset_pixel(xc x,yc+y,c);x,yc+y,c);set_pixel(xc+x,ycset_pixel(xc+x,yc y,c);y,c);set_pixel(xcset_pixel(xc x,ycx,yc y,c);y,c);set_pixel(xc+y,yc+x,c);set_pixel(xc+y,yc+x,c);set_pixel(xcset_pixel(xc y,yc+x,c);y,yc+x,c);set_pixel(xc+y,ycset_pixel(xc+y,yc x,c);x,c);set_pixel(
49、xcset_pixel(xc y,ycy,yc x,c);x,c);2.2 圆的生成算法圆的生成算法 (x x x xc c)2 2+(+(y y y yc c)2 2=r r2 2cc22()yyrxxx x=x xc c+r r cos cosy y=y yc c+r r sin siny=f(x)g(x,y)=0)()(tyytxx2.2 圆的生成算法圆的生成算法t t(t0,t1)x x(x0,x1)显式曲线显式曲线 （explicit curve）参数曲线参数曲线 (parametric curve)隐式曲线隐式曲线（implicit curve）Discussion 4:How t
50、o display an explicit curve,How to display a parametric curve2.3.1 基础知识基础知识 区域填充即给出一个区域的边界，要求对边界范围内的所区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。边形填色。多边形的表示方法多边形的表示方法 顶点表示顶点表示 点阵表示点阵表示2.3 区域填充算法区域填充算法2.3.1 基础知识基础知识(续）续）填色算法分为两大类：填色算法分为两大类：扫描线填色扫描线填色(Scan-Line Fi
