计算机图形学课件PPT课件.ppt

计算机图形学 教学要求 了解图形系统的框架及其涉及的软件 硬件技术 了解图形学的基本问题 掌握图形学的基本概念 方法与算法 对与图形相关的应用及当前的研究热点有一个初步认识 具有一定实践体会和相关的编程能力 本课程的主要内容 绪论光栅图形学扫描转换 裁减 反走样 消影几何造型曲线曲面造型 实体造型真实感图形学Phong模型 光线跟踪 辐射度算法指导实验 主要参考书目 孙家广 计算机图形学 第三版 清华大学出版社 1999 唐泽圣 计算机图形学基础 清华大学出版社 1995DonaldHearn M PaulineBaker ComputerGraphics CVersion PrenticeHall 1997 JamesD Foley AndriesvanDametc IntroductiontoComputerGraphics Addison Wesley 1996唐荣锡 计算机图形学教程 修订版 科学出版社 2000计算机辅助设计与图形学学报中国图形图像学报 成绩评定办法 作业 考勤 实验 20 笔试 80 第1章引言 提出问题 什么是计算机图形学 计算机图形学研究的对象是什么 计算机图形处理系统的构造 1 1计算机图形学及其相关概念 什么是计算机图形学 ComputerGraphics 计算机图形学是研究怎样利用计算机来显示 生成和处理图形的原理 方法和技术的一门学科 IEEE定义 Computergraphicsistheartorscienceofproducinggraphicalimageswiththeaidofcomputer 3D虚拟影像摄影系统协同工作摄影机面部表演捕捉还原系统 计算机图形学与传统理论 交叉 界线模糊 相互渗透CAGD 计算几何 逼近论 计算数学 微分几何形态学混沌学小波理论 计算机图形学的研究对象 图形通常意义下的图形 能够在人的视觉系统中形成视觉印象的客观对象都称为图形 计算机图形学中所研究的图形从客观世界物体中抽象出来的带有颜色及形状信息的图和形 图形的表示点阵法是用具有颜色信息的点阵来表示图形的一种方法 它强调图形由哪些点组成 并具有什么灰度或色彩 参数法是以计算机中所记录图形的形状参数与属性参数来表示图形的一种方法 通常把参数法描述的图形叫做图形 Graphics 把点阵法描述的图形叫做图像 Image end 与计算机图形学相关的学科计算机图形学试图从非图象形式的数据描述来生成 逼真的 图象 数字图象处理旨在对图象进行各种加工以改善图象的视觉效果 计算机视觉是研究用计算机来模拟生物外显或宏观视觉功能的科学和技术 end 酝酿期 50年代 1950年 美国MIT的旋风1号 WhirlwindI 计算机配备了阴极射线管 CRT 来显示一些简单的图形 不具备人 机交互功能 1 2计算机图形学的发展 1 2 1计算机图形学的确立 萌芽期 60年代 1962年 美国MIT林肯实验室的Ivan E Sutherland发表了一篇题为 Sketchpad 一个人 机通信的图形系统 的博士论文 其中首次使用了 ComputerGraphics 提出图形学的概念 成就 图形学之父 的英名获 图灵 奖IEEE计算机杰出成就奖Coons奖 发展期 70年代 普及期 80年代 出现了带有光栅图形显示器的个人计算机和工作站提高增强期 90年代 总体特征 技术发展 需求驱动 1 3计算机图形学的应用 CAD CAM 可视化与可视计算海量的数据的图形表示1986年 美国科学基金会 NSF 专门召开了一次研讨会 会上提出了 科学计算可视化 VisualizationinScientificomputing 科学计算可视化广泛应用于医学 流体力学 有限元分析 气象分析当中在医学领域 机械手术和远程手术 医用CT扫描数据的三维重建 基于CT数据的人体内漫游 计算机动画二维动画图象变形形状混合三维动画关键帧动画变形物体的动画过程动画关节动画与人体动画基于视频 Video 的动画虚拟现实 4图形设备 图形显示设备图形输出包括图形的显示和图形的绘制 图形显示指的是在屏幕上输出图形图形绘制通常指把图形画在纸上 也称硬拷贝 打印机和绘图仪是两种最常用的硬拷贝设备 彩色CRT显示器CRT CRTCathode RayTube 阴极射线管 组成电子枪聚焦系统加速系统磁偏转系统 CRT显示器的简易结构图 工作原理高速的电子束由电子枪发出 经过聚焦系统 加速系统和磁偏转系统就会到达荧光屏的特定位置 由于荧光物质在高速电子的轰击下会发生电子跃迁 即电子吸收到能量从低能态变为高能态 由于高能态很不稳定 在很短的时间内荧光物质的电子会从高能态重新回到低能态 这时将发出荧光 屏幕上的那一点就会亮了要保持显示一幅稳定的画面 必须不断地发射电子束 电平控制器是用来控制电子束的强弱的 当加上正电压时 电子束就会大量通过 将会在屏幕上形成较亮的点 当控制电平加上负电压时 依据所加电压的大小 电子束被部分或全部阻截 通过的电子很少 屏幕上的点也就比较暗聚焦系统是一个电透镜 能使众多的电子聚集于一点加速阳极使电子达到轰击激发荧光屏应有的速度 最后由磁偏转系统来达到指定位置 电子束要到达屏幕的边缘时 偏转角度就会增大 到达屏幕最边缘的偏转角度被称为最大偏转角CRT显示器屏幕越大整个显象管就越长刷新频率刷新一次是指电子束从上到下扫描一次的过程刷新频率高到一定值后 图象才能稳定显示隔行扫描与逐行扫描 电子束扫描过程示意图 彩色CRT显示器显示彩色的原理彩色CRT显示器的荧光屏上涂有三种荧光物质 它们分别能发红 绿 兰三种颜色的光 而电子枪也发出三束电子束来激发这三种物质 中间通过一个控制栅格来决定三束电子到达的位置三束电子经过荫罩的选择 分别到达三个荧光点的位置 通过控制三个电子束的强弱就能控制屏幕上点的颜色 荫罩式彩色CRT显色原理 end LCD显示器CRT固有的物理结构限制了它向更广的显示领域发展屏幕的加大必然导致显象管的加长 显示器的体积必然要加大 在使用时候就会受到空间的限制CRT显示器是利用电子枪发射电子束来产生图像 容易受电磁波干扰长期电磁辐射会对人们健康产生不良影响 LCD显示器的优点外观小巧精致 厚度只有1 5cm左右 不会产生CRT那样的因为刷新频率低而出现的闪烁现象工作电压低 功耗小 节约能源没有电磁辐射 对人体健康没有任何影响 索尼公司的两款LCD外形 LCD显示器基本原理液晶是一种介于液体和固体之间的特殊物质 它具有液体的流态性质和固体的光学性质 当液晶受到电压的影响时 就会改变它的物理性质而发生形变 此时通过它的光的折射角度就会发生变化 而产生色彩液晶屏幕后面有一个背光 这个光源先穿过第一层偏光板 再来到液晶体上 而当光线透过液晶体时 就会产生光线的色泽改变 从液晶体射出来的光线 还得必须经过一块彩色滤光片以及第二块偏光板 液晶显示有主动式和被动式两种被动式液晶屏幕有STN SuperTN超扭曲向列LCD 和DSTN DoublelayerSuperTN双层超扭曲向列LCD 等最流行的主动式液晶屏幕是TFT ThinFilmTransistor薄膜晶体管 主动式液晶显示器使用了FET场效晶体管以及共通电极 这样可以让液晶体在下一次的电压改变前一直保持电位状态 这样主动式液晶显示器就不会产生在被动式液晶显示器中常见的鬼影 或是画面延迟的残像等 LCD显示器的基本指标可视角度视线与屏幕中心法向成一定角度时 人们就不能清晰地看到屏幕图象 而那个能看到清晰图象的最大角度被我们称为可视角度 一般所说的可视角度是指左右两边的最大角度相加 工业上有CR10 ContrastRatio CR5两种标准来判断液晶显示器的可视角度 点距与分辨率液晶屏幕的点距就是两个液晶颗粒 光点 之间的距离 一般0 28 0 32mm就能得到较好的显示效果通常所说的液晶显示器的分辨率是指其真实分辨率 表示水平方向的像素点数与垂直方向的像素点数的乘积 end 第一章小结 1 计算机图形学的概念什么是计算机图形学 图形的种类 相关的学科2 计算机图形学的发展 应用3 图形显示设备CRT LCD 第二章光栅图形学 光栅图形学的研究内容 直线段的扫描转换算法圆弧的扫描转换算法多边形的扫描转换与区域填充字符裁剪反走样消隐 图形的生成 是在指定的输出设备上 根据坐标描述构造二维几何图形 图形的扫描转换 在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程 光栅图形显示器可以看作一个像素的矩阵确定最佳逼近图形的像素集合 并用指定属性写像素的过程称为图形的扫描转换 光栅化二维图形的光栅化必须确定区域对应的像素集 并用指定的属性或图案显示 称为区域填充确定图形的哪部分需要显示 哪部分不需要显示的过程称为裁剪因像素逼近误差导致图形产生畸变的现象称为走样用于减少或消除走样的技术称为反走样删除图形中隐藏的部分称为消隐 2 1直线的扫描转换 直线的绘制要求 1 直线要直2 直线的端点要准确 即无定向性和断裂情况3 直线的亮度 色泽要均匀4 画线的速度要快5 要求直线具有不同的色泽 亮度 线型等 2 1 1数值微分 DDA 法 基本思想已知过端点的直线段L 直线斜率为从的左端点开始 向右端点步进 步长 1 个象素 计算相应的y坐标 取象素点 x round y 作为当前点的坐标 作为最底层的光栅图形算法 在通常的CAD 图形系统中 会被大量应用 因此 哪怕节约一个加法或减法 也是很了不起的改进 由此出发点 导致增量算法的思想 计算当时 即 当x每递增1 y递增k 即直线斜率 例 画直线段xint y 0 5 y 0 5000100 4 0 5210 8 0 5311 2 0 5421 6 0 5522 0 0 5注 网格点表示象素 voidDDALine intx0 inty0 intx1 inty1 intcolor intx floatdx dy y k dx x1 x0 dy y1 y0 k dy dx y y0 for x x0 x x1 x drawpixel x int y 0 5 color y y k 问题 当 k 1时 会如何 答案见下页 注意上述分析的算法仅适用于 k 1的情形 在这种情况下 x每增加1 y最多增加1 当 k 1时 必须把x y地位互换 k 1示意图 特点 增量算法直观 易实现不利于用硬件实现思考 采用增量思想的DDA算法 每计算一个象素 只需计算一个加法 是否最优 如非最优 如何改进 2 1 2中点画线法 目标 进一步将一个加法改为一个整数加法 新思路 DDA算法采用两点式 可否采用其他的直线表示方式 2 1 2中点画线算法 直线的方程 该直线方程将平面分为三个区域 对于直线上的点 F x y 0 对于直线上方的点 F x y 0 对于直线下方的点 F x y 0 基本原理 假定0 k 1 x是最大位移方向 判别式 则有 但这样做 每一个象素的计算量是3个加法 一个乘法 如果也采用增量算法呢 误差项的递推d 0 误差项的递推d 0 初始值d的计算 0 k 1时中点画线算法的算法步骤为 1 输入直线的两端点P0 x0 y0 和P1 x1 y1 2 计算初始值 x y d 0 5 k x x0 y y0 3 绘制点 x y 判断d的符号 若d 0 则 x y 更新为 x 1 y 1 d更新为d 1 k 否则 x y 更新为 x 1 y d更新为d k 4 当直线没有画完时 重复步骤3 否则结束 思考一 能否再做改进 思考二 能否实现整数运算 改进 用2d x代替d1 输入直线的两端点P0 x0 y0 和P1 x1 y1 2 计算初始值 x y d x 2 y x x0 y y0 3 绘制点 x y 判断d的符号 若d 0 则 x y 更新为 x 1 y 1 d更新为d 2 x 2 y 否则 x y 更新为 x 1 y d更新为d 2 y 4 当直线没有画完时 重复步骤3 否则结束 作业 参考DDA代码写出中点画线算法的代码 对比 DDA算法采用点斜式 中点法采用隐式表示 中点法可以有整数算法 思考 其他表示可以推出整数算法吗 2 1 3改进的Bresenham算法 假定直线段的0 k 1基本原理 误差项的计算d初 0 每走一步 d d k一旦y方向上走了一步 d d 1 算法步骤 1 输入直线的两端点P0 x0 y0 和P1 x1 y1 2 计算初始值 x y d 0 x x0 y y0 3 绘制点 x y 4 d更新为d k 判断d的符号 若d 0 5 则 x y 更新为 x 1 y 1 同时将d更新为d 1 否则 x y 更新为 x 1 y 5 当直线没有画完时 重复步骤3和4 否则结束 能改进么 改进1 令e d 0 5 e初 0 5 每走一步有e e k if e 0 thene e 1 算法步骤为 1 输入直线的两端点P0 x0 y0 和P1 x1 y1 2 计算初始值 x y e 0 5 x x0 y y0 3 绘制点 x y 4 e更新为e k 判断e的符号 若e 0 则 x y 更新为 x 1 y 1 同时将e更新为e 1 否则 x y 更新为 x 1 y 5 当直线没有画完时 重复步骤3和4 否则结束 Bresenham画线算法 voidBresenhamline intx0 y0 intx1 y1 intcolor intx y dx dy floatk e dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 for i 0 i 0 y e e 1 还能改进么 改进2 用2e x来替换ee初 x 每走一步有e e 2 y if e 0 thene e 2 x 算法步骤 1 输入直线的两端点P0 x0 y0 和P1 x1 y1 2 计算初始值 x y e x x x0 y y0 3 绘制点 x y 4 e更新为e 2 y 判断e的符号 若e 0 则 x y 更新为 x 1 y 1 同时将e更新为e 2 x 否则 x y 更新为 x 1 y 5 当直线没有画完时 重复步骤3和4 否则结束 Bresenham画线算法的改进 voidBresenhamline intx0 y0 intx1 y1 intcolor intx y dx dy e floatk e dx x1 x0 dy y1 y0 e dx k dy dx e 0 5 x x0 y y0 for i 0 i 0 y e e 1 e e 2 dx 蓝色为原算法中的语句 红色为改进算法中的语句 最终 Bresenham算法也是每个象素 需一个整数算法 其优点是可以用于其他二次曲线 新方法 BRDC binaryrepresentationofdisplacementcodeforlineMiaoLF LiuXG PengQS BaoHJCOMPUTERS GRAPHICS UK26 3 401 408JUN2002 2 2圆的扫描转换 解决的问题 绘出圆心在原点 半径为整数R的圆x2 y2 R2 2 2 1八分法画圆 八分法画圆 y x y x x y x y y x y x x y 解决问题 2 2 2简单方程产生圆弧 算法原理 利用其函数方程 直接离散计算 圆的函数方程为 圆的极坐标方程为 2 2 3中点Bresenham画圆 构造函数F x y x2 y2 R2 对于圆上的点 有F x y 0 对于圆外的点 F x y 0 而对于圆内的点 F x y 0 算法原理 当d 0时 下一点取Pu xi 1 yi 当d 0时 下一点取Pd xi 1 yi 1 M的坐标为 M xi 1 yi 0 5 当F xM yM 0时 取Pd xi 1 yi 1 当F xM yM 0时 约定取Pu 构造判别式 误差项的递推d 0 d 0 判别式的初始值 算法步骤 1 输入圆的半径R 2 计算初始值d 1 25 R x 0 y R 3 绘制点 x y 及其在八分圆中的另外七个对称点 4 判断d的符号 若d 0 则先将d更新为d 2x 3 再将 x y 更新为 x 1 y 否则先将d更新为d 2 x y 5 再将 x y 更新为 x 1 y 1 5 当x y时 重复步骤3和4 否则结束 改进 用d 0 25代替d算法步骤 1 输入圆的半径R 2 计算初始值d 1 R x 0 y R 3 绘制点 x y 及其在八分圆中的另外七个对称点 4 判断d的符号 若d 0 则先将d更新为d 2x 3 再将 x y 更新为 x 1 y 否则先将d更新为d 2 x y 5 再将 x y 更新为 x 1 y 1 5 当x y时 重复步骤3和4 否则结束 程序 椭圆的扫描转换 1椭圆的特征 对于椭圆上的点 有F x y 0 对于椭圆外的点 F x y 0 对于椭圆内的点 F x y 0 解决问题 以弧上斜率为 1的点作为分界将第一象限椭圆弧分为上下两部分 引理5 1 若在当前中点 法向量的y分量比x分量大 即 而在下一个中点 不等号改变方向 则说明椭圆弧从上部分转入下部分 法向量 椭圆的中点Bresenham算法 算法原理 先推导上半部分的椭圆绘制公式 判别式 若d1 0 取Pu xi 1 yi 若d1 0 取Pd xi 1 yi 1 误差项的递推d1 0 d1 0 判别式的初始值 再来推导椭圆弧下半部分的绘制公式原理 判别式 若d2 0 取Pl xi yi 1 若d2 0 取Pr xi 1 yi 1 误差项的递推d2 0 d2 0 注意 上半部分的终止判别下半部分误差项的初值算法步骤 1 输入椭圆的长半轴a和短半轴b 2 计算初始值d b2 a2 b 0 25 x 0 y b 3 绘制点 x y 及其在四分象限上的另外三个对称点 4 判断d的符号 若d 0 则先将d更新为d b2 2x 3 再将 x y 更新为 x 1 y 否则先将d更新为d b2 2x 3 a2 2y 2 再将 x y 更新为 x 1 y 1 5 当b2 x 1 a2 y 0 5 时 重复步骤3和4 否则转到步骤6 6 用上半部分计算的最后点 x y 来计算下半部分中d的初值 7 绘制点 x y 及其在四分象限上的另外三个对称点 8 判断d的符号 若d 0 则先将d更新为b2 2xi 2 a2 2yi 3 再将 x y 更新为 x 1 y 1 否则先将d更新为d a2 2yi 3 再将 x y 更新为 x y 1 9 当y 0时 重复步骤7和8 否则结束 2 3多边形的扫描转换与区域填充 多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充 区域填充是从给定的位置开始涂描直到指定的边界条件为止 2 3 1多边形的扫描转换 多边形有两种重要的表示方法 顶点表示和点阵表示 多边形的扫描转换 把多边形的顶点表示转换为点阵表示 区域可采用内点表示和边界表示两种表示形式 区域填充 指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 1 什么是多边形的扫描转换 多边形分为凸多边形 凹多边形 含内环的多边形 2 x 扫描线算法基本思想 算法步骤 1 确定多边形所占有的最大扫描线数 得到多边形顶点的最小和最大y值 ymin和ymax 2 从y ymin到y ymax 每次用一条扫描线进行填充 3 对一条扫描线填充的过程可分为四个步骤 a 求交b 排序c 交点配对d 区间填色 存在问题 当扫描线与多边形顶点相交时 交点的取舍问题 解决 当扫描线与多边形的顶点相交时 若共享顶点的两条边分别落在扫描线的两边 交点只算一个 若共享顶点的两条边在扫描线的同一边 这时交点作为零个或两个 0 1 1 1 1 0 2 2 2 3 改进的有效边表算法 Y连贯性算法 改进原理 处理一条扫描线时 仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性 有效边 ActiveEdge 指与当前扫描线相交的多边形的边 也称为活性边 有效边表 ActiveEdgeTable AET 把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中 此链表称为有效边表 有效边表的每个结点 xymax1 knext 边表 EdgeTable 边表的构造 1 首先构造一个纵向链表 链表的长度为多边形所占有的最大扫描线数 链表的每个结点 称为一个桶 则对应多边形覆盖的每一条扫描线 2 将每条边的信息链入与该边最小y坐标 ymin 相对应的桶处 也就是说 若某边的较低端点为ymin 则该边就放在相应的扫描线桶中 3 每条边的数据形成一个结点 内容包括 该扫描线与该边的初始交点x 即较低端点的x值 1 k 以及该边的最大y值ymax x yminymax1 kNEXT 4 同一桶中若干条边按X ymin由小到大排序 若X ymin相等 则按照1 k由小到大排序 解决顶点交点计为1时的情形 算法步骤 1 初始化 构造边表 AET表置空 2 将第一个不空的ET表中的边与AET表合并 3 由AET表中取出交点对进行填充 填充之后删除y ymax的边 4 yi 1 yi 1 根据xi 1 xi 1 k计算并修改AET表 同时合并ET表中y yi 1桶中的边 按次序插入到AET表中 形成新的AET表 5 AET表不为空则转 3 否则结束 2 3 2区域填充 区域是指已经表示成点阵形式的填充图形 它是像素集合 4 邻接点和8 邻接点 4 连通区域和8 连通区域把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法 边界填充算法 Boundary fillAlgorithm 枚举出给定区域内所有象素的表示方法称为内点表示 泛填充算法 Flood fillAlgorithm 1 边界填充算法算法的输入 种子点坐标 x y 填充色和边界颜色 栈结构实现4 连通边界填充算法的算法步骤为 种子象素入栈 当栈非空时重复执行如下三步操作 1 栈顶象素出栈 2 将出栈象素置成填充色 3 检查出栈象素的4 邻接点 若其中某个象素点不是边界色且未置成多边形色 则把该象素入栈 栈结构实现8 连通边界填充算法的算法步骤为 种子象素入栈 当栈非空时重复执行如下三步操作 1 栈顶象素出栈 2 将出栈象素置成填充色 3 检查出栈象素的8 邻接点 若其中某个象素点不是边界色且未置成多边形色 则把该象素入栈 特点 可以用于填充带有内孔的平面区域 把太多的象素压入堆栈改进通过沿扫描线填充水平象素段 来代替处理4 邻接点和8 邻接点 沿扫描线填充水平象素段的4 连通边界填充算法步骤 种子象素入栈 当栈非空时作如下三步操作 1 栈顶象素出栈 2 填充出栈象素所在扫描行的连续象素段 直到遇到边界象素为止 即每出栈一个象素 就对包含该象素的整个扫描线区间进行填充 3 在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素 若存在非边界 未填充边界的象素 则把每一区间的最右象素取作种子象素入栈 2 泛填充算法算法的输入 种子点坐标 x y 填充色和内部点的颜色 算法原理 算法从指定的种子 x y 开始 用所希望的填充颜色赋给所有当前为给定内部颜色的象素点 4 连通泛填充算法步骤如下 种子象素入栈 当栈非空时重复执行如下三步操作 1 栈顶象素出栈 2 将出栈象素置成填充色 3 检查出栈象素的4 邻接点 若其中某个象素点是给定内部点的颜色且未置成新的填充色 则把该象素入栈 内点表示的4连通区域的递归填充算法 voidFloodFill4 intx inty intoldcolor intnewcolor if getpixel x y oldcolor 属于区域内点oldcolor drawpixel x y newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor 注意 当以边界表示时 4 连通边界填充算法只能填充4 连通区域 8 连通边界填充算法也只能填充8 连通区域 当以内点表示时 8 连通泛填充算法可以填充8 连通区域也可以填充4 连通区域 当然4 连通泛填充算法还是只能填充4 连通区域 2 4字符处理 ASCII码 美国信息交换用标准代码集 AmericanStandardCodeforInformationInterchange 简称ASCII码 它是用7位二进制数进行编码表示128个字符 包括字母 标点 运算符以及一些特殊符号 国际码 中华人民共和国国家标准信息交换编码 简称为国际码 代号GB2312 80 是汉字编码的国家标准字符集 该字符集分为94个区 94个位 每个符号由一个区码和一个位码共同标识 区码和位码各用一个字节表示 为了能够区分ASCII码与汉字编码 采用字节的最高位来标识 最高位为0表示ASCII码 最高位为1表示表示汉字编码 字库 为了在显示器等输出设备上输出字符 系统中必须装备有相应的字库 字库中存储了每个字符的形状信息 字库分为矢量型和点阵型两种 字库中储存了每个字符的图形信息 2 4 1点阵字符 在点阵表示中 每个字符由一个点阵位图来表示显示时 形成字符的象素图案存储空间庞大 可采用轮廓字型法压缩黑白段压缩 点阵字库中的位图表示矢量轮廓字符 2 4 2矢量字符 矢量字符采用直线和曲线段来描述字符形状 矢量字符库中记录的是笔划信息 显示时 解释字符的每个笔划信息存储空间小 方便变换 特点 点阵字符 存储量大 易于显示矢量字符 存储量小 美观 变换方便 但需要光栅化后才能显示 字符属性 字体宋体仿宋体楷体黑体隶书字高宋体宋体宋体宋体字宽字倾斜角倾斜倾斜对齐 左对齐 中心对齐 右对齐 字色红色 绿色 蓝色 补充 属性处理 当前属性值表 1 线型处理实心段和中间空白段的长度 象素数目 可用象素模板 pixelmask 例如 16 16 指定 存在问题 如何保持任何方向的划线长度近似地相等 解决可根据线的斜率来调整实心段和中间空白段的象素数目 2 线刷子和方刷子处理线宽线刷子 垂直刷子 水平刷子 特点实现简单 效率高 斜线与水平 或垂直 线不一样粗 当线宽为偶数个象素时 线的中心将偏移半个象素 利用线刷子生成线的始末端总是水平或垂直的 看起来不太自然 解决 添加 线帽 linecap 当比较接近水平的线与比较接近垂直的线汇合时 汇合处外角将有缺口 解决 斜角连接 miterjoin 圆连接 roundjoin 斜切连接 beveljoin 方刷子 特点 方刷子绘制的线条 斜线 比用线刷子所绘制的线条要粗一些方刷子绘制的斜线与水平 或垂直 线不一样粗方刷子绘制的线条自然地带有一个 方线帽 3 其它线宽处理方式区域填充改变刷子形状 2 5裁剪 裁剪 确定图形中哪些部分落在显示区之内 哪些落在显示区之外 以便只显示落在显示区内的那部分图形 这个选择过程称为裁剪 在使用计算机处理图形信息时 计算机内部存储的图形往往比较大 而屏幕显示的只是图的一部分 2 5 1直线段裁剪 Cohen Sutherland法 区域编码法 中点分割裁剪算法梁友栋 Barskey裁剪算法 Cohen Sutherland法 区域编码法 对每条线段P1P2的处理可分为三种情况 1 P1P2完全处于窗口之内 则显示该线段 2 P1P2完全处于窗口之外 则丢弃该线段 3 若线段不满足以上两种情况 则在交点处把线段分为两段 其中一段完全处于窗口外 丢弃之 然后对另一段重复上述处理 P1 P2 P3 P4 为了快速判断直线与窗口的关系 对窗口可采取编码方法 将二维平面分成9个区域 每个区域赋予4位编码CtCbCrCl 1010 0110 1000 0000 0001 0101 0100 1001 0010 则说明该线段完全在窗口外 判断条件 则说明该线段可能与窗口有交点 中点分割裁剪算法 在区域编码的基础上进行改进 完全在窗口内和完全在窗口外采用之前的处理方法 对不完全在窗口内 寻找距离P0P1最近的可见点 P3 P4 P1 P2 Pm 设要裁剪的线段是P0P1 P0P1和窗口边界交于A B C D四点 见图 算法的基本思想是从A B和P0三点中找出最靠近的P1点 图中要找的点是P0 从C D和P1中找出最靠近P0的点 图中要找的点是C点 那么P0C就是P0P1线段上的可见部分 梁友栋 Barskey裁剪算法 线段的参数表示x x0 t xy y0 t y0 t 1 x x1 x0 y y1 y0窗口边界的四条边分为两类 始边和终边 求出P0P1与两条始边的交点参数t0 t1 令tl max t0 t1 0 则tL即为三者中离p1最近的点的参数求出p0p1与两条终边的交点参数t2 t3 令tu min t2 t3 1 则tU即为三者中离p0最近的点的参数若tu tl 则可见线段区间 tl tu t0 t1 t2 t3 0 1 始边和终边的确定及交点计算 令QL xDL x0 xLQR xDR xR x0QB yDB y0 yBQT yDT yT y0交点为ti Di Qii L R B TQi0ti为与终边交点参数Qi 0Di0时 分析另一D E F A B 当Qi 0时若Di0时 分析另一D 如图中的EF就是这种情况 它使QL 0 DL 0和QR 0 DR 0 这时由于EF和x xL及x xR平行 故不必去求出EF和x xL及x xR的交点 而让EF和y yT及y yB的交点决定直线段上的可见部分 E F A B 二多边形的裁剪 错觉 直线段裁剪的组合 新的问题 1 边界不再封闭 需要用窗口边界的恰当部分来封闭它 如何确定其边界 Sutherland Hodgman算法 逐边裁剪算法 分割处理策略 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪 流水线过程 左上右下 前边的结果是后边的输入 亦称逐边裁剪算法 Sutherland Hodgman算法 基本思想是一次用窗口的一条边裁剪多边形 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分 可见一侧 不可见一侧多边形的各条边的两端点S P 它们与裁剪线的位置关系只有四种 Sutherland Hodgman算法 情况 1 仅输出顶点P 情况 2 输出0个顶点 情况 3 输出线段SP与裁剪线的交点I 情况 4 输出线段SP与裁剪线的交点I和终点P Sutherland Hodgman算法框图 处理线段SP过程子框图 Sutherland Hodgman算法 上述算法仅用一条裁剪边对多边形进行裁剪 得到一个顶点序列 作为下一条裁剪边处理过程的输入 对于每一条裁剪边 算法框图同上 只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变 Sutherland Hodgeman算法 对凸多边形应用本算法可以得到正确的结果 但是对凹多边形的裁剪将如图所示显示出一条多余的直线 这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现 因为只有一个输出顶点表 所以表中最后一个顶点总是连着第一个顶点 解决这个问题有多种方法 一是把凹多边形分割成若干个凸多边形 然后分别处理各个凸多边形 二是修改本算法 沿着任何一个裁剪窗口边检查顶点表 正确的连接顶点对 再有就是Weiler Atherton算法 2 双边裁剪法 Weiler Atherton算法 裁剪窗口为任意多边形 凸 凹 带内环 的情况 主多边形 被裁剪多边形 记为Ps裁剪多边形 裁剪窗口 记为Pc同时设每一多边形按顺时针方向排列 则右边为多边形的内部 内环相反 算法首先沿Ps任一点出发 跟踪检测Ps的每一条边 当Ps与Pc相交时 1 若Ps的边进入Pc 则继续沿Ps的边往下处理 同时输出该线段 2 若Ps的边是Pc出来 则从此点 前交点 开始 沿着窗口边框向右检测Ps的边 即用Pc的有效边框去裁剪Ps的边 找到Ps与Pc最靠近前交点的新交点 同时输出由前交点到此新交点之间窗边上的线段 3 返回前交点 再沿Ps处理各条边 直到处理完所有Ps的边 返回起点为止 起点 2 1 3 4 5 6 7 8 9 10 11 13 Pc Ps P1 P6 P5 P4 P3 P2 Q1 P8 P7 Q6 Q5 Q4 Q3 Q2 2 6反走样 用离散量表示连续量引起的失真 就叫做走样 Liasing 走样现象 一是光栅图形产生的阶梯形一是图形中包含相对微小的物体时 这些物体在静态图形中容易被丢弃或忽略 在动画序列中时隐时现 产生闪烁 用于减少或消除这种效果的技术 称为反走样 antialiasing 常用的反走样方法有 提高分辨率 区域采样和加权区域采样如 阶梯程度小一倍 但存储空间大4倍 扫描时间大2倍过取样 supersampling 或后滤波区域取样 areasampling 或前滤波 2 6 1过取样 简单过取样 将屏幕看成是比实际所具有的更细的网格来增加取样率 而后沿这种更细网格使用取样点来确定每个屏幕象素的合适亮度等级 例 对于直线段的灰度显示 可以将每个象素分成一定数目的子象素并统计沿线路径的子象素数目 将每个象素的亮度等级设置为正比于这个子象素数目的值 2 6 2简单的区域取样 当直线段与像素有交时 求出两者相交区域的面积 然后根据相交区域面积的大小确定该像素的灰度值 如何计算直线段与象素相交区域的面积 d e a 的面积为D2 2k b 的面积为D k 2 c d e 的面积可由 a b 推出 也可以利用一种求相交区域的近似面积的离散计算方法 1 将屏幕象素分割成n个更小的子象素 2 计算中心落在直线段内的子象素的个数m 3 m n为线段与象素相交区域面积的近似值 特点 直线段对一个象素亮度的贡献与两者重叠区域的面积成正比相同面积的重叠区域对象素的贡献相同非加权区域采样方法有两个缺点 象素的亮度与相交区域的面积成正比 而与相交区域落在象素内的位置无关 这仍然会导致锯齿效应 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差 2 6 3加权区域取样 加权区域取样原理使相交区域对象素亮度的贡献依赖于该区域与象素中心的距离当直线经过该象素时 该象素的亮度F是在两者相交区域A 上对滤波器 函数w 进行积分的积分值 可采用离散计算方法如 我们将屏幕划分为n 3 3个子象素 加权表可以取作特点 接近理想直线的象素将被分配更多的灰度值 相邻两个象素的滤波器相交 有利于缩小直线条上相邻象素的灰度差 2 7消隐 物体的消隐或隐藏线面的消除 在给定视点和视线方向后 决定场景中哪些物体的表面是可见的 哪些是被遮挡不可见的 物体的消隐或隐藏线面的消除 经过消隐得到的投影图称为物体的真实图形 按消隐对象分类线消隐消隐对象是物体上的边 消除的是物体上不可见的边 面消隐消隐对象是物体上的面 消除的是物体上不可见的面 深度缓冲器算法 A缓冲器算法 区间扫描线算法等 BSP算法 多边形区域排序算法 深度排序算法 区域细分算法 光线投射算法等 两个基本原则 排序 连贯性选择z轴的负向为观察方向 1深度缓存器算法 Z buffer算法 Z buffer算法的原理 例如 两块缓冲区 Z缓存 保存屏幕坐标系上各象素点所对应的深度值帧缓存 保存各点的颜色 Z buffer算法的步骤如下 1 初始化 把Z缓存中各 x y 单元置为z的最小值 而帧缓存各 x y 单元置为背景色 2 在把物体表面相应的多边形扫描转换成帧缓存中的信息时 对于多边形内的每一采样点 x y 进行处理 1 计算采样点 x y 的深度z x y 2 如z x y 大于Z缓存中在 x y 处的值 则把z x y 存入Z缓存中的 x y 处 再把多边形在z x y 处的颜色值存入帧缓存的 x y 地址中 问题 计算采样点 x y 的深度z x y 假定多边形的平面方程为 Ax By Cz D 0 利用连贯性加速深度的计算 扫描线上所有后继点的深度值 当处理下一条扫描线y y 1时 该扫描线上与多边形相交的最左边 x最小 交点的x值可以利用上一条扫描线上的最左边的x值计算 扫描线深度缓存器算法 扫描线Z buffer算法 特点分析 A缓冲器算法 2区间扫描线算法 算法原理 避免对被遮挡区域的采样是进一步提高扫描线算法计算效率的关键 算法 三张表 边表 多边形表 有效边表 算法的关键 分割子区间 确定子区间上的唯一可见面 特殊情形 贯穿情形 循环遮挡情形 贯穿情形 为了使算法能处理互相贯穿的多边形 扫描线上的分割点不仅应包含各多边形的边与扫描线的交点 而且应包含这些贯穿边界与扫描线的交点 循环遮挡 将多边形进行划分以消除循环遮挡 例如 3深度排序算法 画家算法 算法原理 若场景中任何多边形在深度上均不贯穿或循环遮挡 则各多边形的优先级顺序可完全确定 深度排序算法 1 将多边形按深度进行排序 距视点近的优先级高 距视点远的优先级低 2 由优先级低的多边形开始逐个对多边形进行扫描转换 其中的关键是将多边形按深度进行排序 P不遮挡Q的各种情况 ab c d e 及互相遮挡f 4区域细分算法 算法原理一种简单的细分方式是将区域分割为四块大小相等的矩形 算法描述 把物体投影到全屏幕窗口上 然后递归分割窗口 直到窗口内目标足够简单 可以显示为止 A 如果窗口内没有物体 则按背景色显示B 若窗口内只有一个面 则把该面显示出来C 若窗口内含有两个以上的面 则把窗口等分成四个窗口 有下列情况之一 窗口足够简单 1 所有多边形均与窗口分离 该窗口置背景色2 只有一个多边形与窗口相交 或该多边形包含窗口 则先将整个窗口置成背景色 然后再对多边形在窗口内的部分用扫描线算法绘制 3 有一个多边形包围了窗口 或窗口与多个多边形相交 但有一个多边形包围窗口 而且在最前面最靠近观察点 可见性测试 5光线投射算法 算法原理 算法步骤可简单描述如下 1 通过视点和投影平面 显示屏幕 上的所有象素点作一入射线 形成投影线 2 将任一投影线与场景中的所有多边形求交 3 若有交点 则将所有交点按z值的大小进行排序 取出最近交点所属多边形的颜色 若没有交点 则取出背景的颜色 4 将该射线穿过的象素点置为取出的颜色 第三章几何造型技术 在几何造型系统中 有3种描述物体的三维模型 线框模型 用顶点和棱边来表示物体 没有面的信息曲面模型 在线框模型的基础上添加面的信息 并用面的集合来表示物体实体模型 是最高级的模型 能完整的表示物体的所有形状信息 3 1曲线曲面基础1 曲线曲面的参数化表示 参数化 p x t y t z t 参数表示方法的优点 1 与坐标系的选取无关2 自变量和因变量分开 因变量的变化可明显表示3 斜率4 t 0 1 使其相应的几何分量是有界的 2 样条 插值 逼近 拟合 采用模线样板法表示和传递自由曲线曲面的形状称为样条 样条曲线是指由多项式曲线段连接而成的曲线 在每段的边界处满足特定的连续条件 样条曲面则可以用两组正交样条曲线来描述 在自由曲线的设计中常常遇到两类问题 一类是由已知的离散点来决定曲线一类是已知自由曲线 如何通过交互方式修改完全通过给定点列 型值点 来构造曲线的方法称为曲线的拟合 求给定型值点之间曲线上的点称为曲线的插值 求出几何形状上与给定型值点列的连接线相近似的曲线称为曲线的逼近 逼近的曲线不必通过型值点列 曲线曲面的拟合 当用一组型值点来指定曲线曲面的形状时 形状完全通过给定的型值点列 曲线曲面的逼近 当用一组控制点来指定曲线曲面的形状时 求出的形状不必通过控制点列 求给定型值点之间曲线上的点称为曲线的插值 将连接有一定次序控制点的直线序列称为控制多边形或特征多边形 3 连续性条件 假定参数曲线段pi以参数形式进行描述 参数连续性几何连续性 1 参数连续性0阶参数连续性 记作C0连续性 是指曲线的几何位置连接 即 1阶参数连续性记作C1连续性 指代表两个相邻曲线段的方程在相交点处有相同的一阶导数 2阶参数连续性 记作C2连续性 指两个相邻曲线段的方程在相交点处具有相同的一阶和二阶导数 2 几何连续性0阶几何连续性 记作G0连续性 与0阶参数连续性的定义相同 满足 1阶几何连续性 记作G1连续性 指一阶导数在相邻段的交点处成比例2阶几何连续性 记作G2连续性 指相邻曲线段在交点处其一阶和二阶导数均成比例 例 令 V0 t V1 V0 3 t 0 1 P t V0 V1 V0 3 t 1 2 V1 V0 3 t 1 2 P t 为在 0 2 上表示一条连接V1 V0的直线段结论 C1连续能保证G1连续 C2连续能保证G2连续 但是反过来去不行 即 Cn连续的条件比Gn连续的条件要苛刻 3 2Bezier曲线曲面 3 2 1Bezier曲线的定义 定义 Bernstein基函数具有如下形式 注意 当i 0 t 0时 ti 1 i 1 Bernstein基函数的性质 1 正性2 端点性质3 权性4 对称性 5 递推性6 导函数7 最大值8 升阶公式9 积分 1 一次Bezier曲线 n 1 2 二次Bezier曲线 n 2 3 三次Bezier曲线 n 3 3 2 2Bezier曲线的性质 1 端点 2 一阶导数 三次Bezier曲线段在起始点和终止点处的一阶导数为 3 二阶导数 三次Bezier曲线段在起始点和终止点处的二阶导数为 4 对称性5 凸包性 这一结果说明当t在 0 1 区间变化时 对某一个t值 P t 是特征多边形各顶点的加权平均 权因子依次是 在几何图形上 意味着Bezier曲线P t 在中各点是控制点Pi的凸线性组合 即曲线落在Pi构成的凸包之中 6 几何不变性这是指某些几何特性不随坐标变换而变化的特性 Bezier曲线位置与形状与其特征多边形顶点的位置有关 它不依赖坐标系的选择 7 变差减少性若Bezier曲线的特征多边形是一个平面图形 则平面内任意直线与C t 的交点个数不多于该直线与其特征多边形的交点个数 这一性质叫变差缩减性质 此性质反映了Bezier曲线比其特征多边形的波动还小 也就是说Bezier曲线比特征多边形的折线更光顺 8 控制顶点变化对曲线形状的影响 3 2 3Bezier曲线的生成 1 绘图一段Bezier曲线 2Bezier曲线的递推 deCasteljau 算法 计算Bezier曲线上的点 可用Bezier曲线方程 但使用deCasteljau提出的递推算法则要简单的多 如下图所示 设 是一条抛物线上顺序三个不同的点 过和点的两切线交于点 在点的切线交和于和 则如下比例成立 这是所谓抛物线的三切线定理 示意图见下页 当P0 P2固定 引入参数t 令上述比值为t 1 t 即有 t从0变到1 第一 二式就分别表示控制二边形的第一 二条边 它们是两条一次Bezier曲线 将一 二式代入第三式得 当t从0变到1时 它表示了由三顶点P0 P1 P2三点定义的一条二次Bezier曲线 并且表明 这二次Bezier曲线P20可以定义为分别由前两个顶点 P0 P1 和后两个顶点 P1 P2 决定的一次Bezier曲线的线性组合 依次类推 由四个控制点定 义的三次Bezier曲线P30可被定义为分别由 P0 P1 P2 和 P1 P2 P3 确定的二条二次Bezier曲线的线性组合 由 n 1 个控制点Pi i 0 1 n 定义的n次Bezier曲线Pn0可被定义为分别由前 后