计算机图形学实验指导书-v1

计算机科学与技术学院 计算机图形学 实验指导书 陈笑威 张健 编写 适用专业 计算机科学 贵州大学 二 OO七年八月 前 言 计算机图形学是计算机学科最活跃的分支之一 也是计算机专业的必修课 程之一 计算机图形学是一门实践性非常强的学科 其内容变化也是日新月异 本指导书包含了光栅图形学 几何造型 真实感图形学三部分内容 对各 部分内容中的经典算法有详细的算法原理介绍及算法描述 通过本指导书 读 者可以快速地掌握计算机图形学中经典算法的应用及实现原理 在此基础之上 可以更好的了解计算机图形学的研究前沿 2 目 录 实验一 直线生成算法 3 数值微分法 DDA Digital Differential Analyzer 4 中点画线法 4 Bresenham 画线算法 6 实验二 圆的生成算法 7 生成园弧的中点算法 8 Bresendham 画园算法 12 实验三 椭园的生成算法 15 中点算法 16 实验四 多边形填充算法 19 扫描线算法 20 边填充算法 正负相消法 21 边标志算法 轮廓填充算法 21 种子填充算法 22 区域填充 种子填充法 22 扫描线种子算法 23 实验五 常用曲面和曲线的生成算法 24 三次 Hermite 曲线的生成 25 Bezier 曲线 以逼近为基础的参数曲线 26 B 样条曲线 27 实验六 二维图形的几何变换 30 标准齐次坐标 x y 1 二维变换的矩阵表示 32 实验七 裁减及消隐 36 直线裁减 37 多边形裁减 43 Roberts 消隐算法 45 Z 缓冲器算法 51 扫描线 Z 缓冲器算法 53 光线跟踪算法 53 实验八 曲线和曲面算法的应用 实体造型 56 实验九 真实感图形生成 57 简单光照模型 58 Gouraud 明暗处理 59 Phong 明暗处理 60 运用光照模型的光线跟踪算法 62 实验报告的基本内容及要求 65 附件 1 实验报告格式 66 3 实验一 直线生成算法 实验学时 4 实验类型 验证 综合 设计 实验要求 必修 一 实验目的 通过本实验 使学生了解并掌握在光栅显示系统中直线的生成和显示算法 熟悉相关 开发平台 为后继实验打下基础 二 实验内容 实现 DDA 画线算法 中点画线算法和 Bresenham 画线算法 并比较 三 实验原理 方法和手段 参见本指导书 四 实验组织运行要求 以学生自主训练为主的开放模式组织教学 五 实验条件 硬件平台 PC 软件 推荐 Windows 平台 Visual C matlab 六 实验步骤 1 掌握算法原理 2 依据算法 编写源程序并进行调试 3 对运行结果进行保存与分析 4 把源程序以文件的形式提交 5 按格式书写实验报告 七 思考题 八 实验报告 主要包括实验预习 实验记录和实验报告三部分 基本内容详见附件 1 4 01 01 xx yy x y k Bkxy ii 11 1 1 1 1 iiii ii ii ykxBk xxBkxBk x yyk x letx yykk 1 1 1 1 1 1 ii i ii yyBBy x kkkkk lety xxk k 数值微分法 DDA Digital Differential Analyzer 算法原理 设直线两端点为 P1 x1 y1 及 P0 x0 y0 则直线斜率为 直线方程为 当 k 1 y 每增加 1 x 最多增加 1 或增加小于 1 算法分析 复杂度 加法 取整 优点 避免了 y kx b 方程中的浮点乘法 比直接用点斜式画线快 缺点 需浮点数加法及取整运算 不利于硬件实现 中点画线法 算法原理 设 0 k 1 中点M在直线下方 下一点取p1点 中点 M 在直线上方取p2点 中点算法用整数加法及比较代替了 DDA 中的浮 点数加法及取整运算 效率大大提高 假设直线的 起点 终点分别为 X0 Y0 X1 Y1 直线将二 维空间划分为三个区域 直线方程 F x y ax by c 0 其中 a y1 y0 b x1 x0 c B x1 x0 如 F x y 0 则 x y 在直线上 如 F x y 0 则 x y 在直线上方 因此 可将中点 M 的坐标 Xp 1 Yp 0 5 代入 yi xi yi 1 xi 1 y x F x y 0 F x y 0 F x y 0 则M在理想直线上方 选正右方P2点 如果 d0 则新的中点M仅在x方向加 1 新的 d 值为 dnew F xi 2 yi 0 5 a xi 2 b yi 0 5 c 而 dold F xi 1 yi 0 5 a xi 1 b yi 0 5 c dnew dold a dold dy 2 如由pi点确定是右上方 P1 点 d 0 dnew dold 2 dy dx 当 dold 0 Bresenham 画线算法 算法原理 与 DDA 算法相似 Bresenham 画线算法也要在每 列象素中找到与理想直线最逼 近的象素点 根据直线的斜率来确定变 量在 x 或 y 方向递增一个单位 另一个方向 y 或 x 的增量为 0 或 1 它取决于实际直线与最 接近网格点位置的距离 这一 距离称为误差 算法的巧妙构 思 使每次只需检查误差项 增量 的符号即可 6 定义决策变量 d d k 0 k 1 设0 k 1 如直线上的一点为 x y 则下一点为 x 1 y d 0 5 当 d 1 时 让 d d 1 以保证 0 d 1 d0 0 令e d 0 5 0 k 1 则e0 0 5 则下一点为 x 1 y e 0 当e 0 时 让e e 1 重新初始化误差项 由于算法只用到误差项的符号 为了改用 整数以避免除法 可以作如下替换 e 2 e dx定义决策变量 e 2 e dx 则e0 dx e e 2 dy则下一点为 x 1 y e 0 当e 0 时 让 e e dx 重新初始化误差项 实验二 圆的生成算法 实验学时 4 实验类型 验证 综合 设计 实验要求 必修 一 实验目的 通过本实验 使学生了解并掌握在光栅显示系统中园的生成和显示算法 进一步熟悉 相关开发平台 二 实验内容 实现中点画园算法 二阶差分算法 及 Bresendham 画园算法 并比较各算法 三 实验原理 方法和手段 参见本指导书 四 实验组织运行要求 以学生自主训练为主的开放模式组织教学 五 实验条件 硬件平台 PC 软件 推荐 Windows 平台 Visual C matlab 六 实验步骤 1 掌握算法原理 2 依据算法 编写源程序并进行调试 3 对运行结果进行保存与分析 4 把源程序以文件的形式提交 7 5 按格式书写实验报告 七 思考题 八 实验报告 主要包括实验预习 实验记录和实验报告三部分 基本内容详见附件 1 8 生成园弧的中点算法算法原理 画出第二个八分园 45 90 利用八对称性 画出其它八分园 1 用中点算法画第二个八分园 从当前已获得的象素递推出下一个象素 园弧的隐函数的形式为 F x y x2 y2 R2 0 则园弧的正负划分性为 F x y 0 x y 在园 外 F x y 0 x y 在园内 F x y 0 x y 在园上 设 xi yi 为已确定的象素坐标 则下一个象素 只能是正右方的 E 点或右下方的 SE 点 设 M 是 E 和 SE 的中点 则 M xi 1 yi 0 5 如 F M 0 则 M 在园外 说明 SE 距离圆弧 更近 下一点取右下方 SE 点 如 F M 0 则 M 在园上 下一点取 E 点或 SE 点 构造判别式 d F M F xi 1 yi 0 5 xi 1 2 yi 0 5 2 R2 1 d 0 中点在圆外 选右下方的 SE 32 i xE 点 再下一个象素的判别式为 dnew F xi 2 yi 1 5 xi 2 2 yi 1 5 2 R2 d 2xi 3 yi 2 d 2 xi yi 5 沿右下方向 d 的增量为 3 d 初始值为 d0 F 1 R 5 2 ii yxSE 0 5 1 R 0 5 2 R2 1 25 R 在 d 的运算中包含了浮点数的运算 为了消除 d 中的浮点数运算 分析上述算法 可 以看出 算法中取作用的只是 d 的符号 所以可设另一整数变量 h h d 0 25 所以 初始化运算 d0 1 25 R 对应于 h0 1 R 判别式 d 0 对应于 h0 F x y 0F x y 0 xi yi M E SE 9 终为整数 所以可用 h 代替 d 作判断 其初始值 h0 d0 0 25 1 25 R 0 25 1 R 有以下对应关系 h 0 d0 d 0 h 0 d 0 例 用中点算法画一 R 5 的园 d0 1 R 1 5 4 0 M 在园内 取 E 点 1 5 d1 d0 2xi 3 4 2 0 3 10 M 在园外 取 SE 点 3 4 d3 d2 2 xi yi 5 4 2 2 5 5 3 0 M 在园外 取 SE 点 4 3 d4 d3 2 xi yi 5 3 2 3 4 5 6 0 M 在园外 取 SE 点 5 2 yx if d 0 d d 2 x 3 取 E 点 else d d 2 x y 5 取 SE 点 y y 1 end x x 1 X x 1 x Y x 1 y end 利用对称性求其它七个八分园 X1 Y Y1 X X2 Y Y2 X X3 X Y3 Y X4 Y Y4 X X5 X Y5 Y X6 X Y6 Y X7 Y Y7 X plot X Y X Y o X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6 X7 Y7 title R 5 算法分析 二阶差分法 二阶差分法 利用二阶差分降低增量的阶数 二阶差分 降低增量的阶数 用差分法消除中点算法中的乘法运算 10 中点算法中 1 如在现有点 p xp yp 上 对 p 1 点选择了 E xp 1 yp 点 1 增量 E 二阶差分增量为 2 增量 SE 2 oldnew EE 二阶差分增量为 2 oldnew SESE 2 如在现有点 p xp yp 上 对 p 1 点选择了 SE xp 1 yp 1 点 1 增量 E 二阶差分增量为 2 oldnew EE 2 增量 SE 二阶差分增量为 4 oldnew SESE xyd E SE x x 1 d0 y 1d SE E 2 SE 4 32 i xE5 2 ii yxSE 32 pold xE3 1 2 pnew xE 0 0 1 iii iii i dSEd dEd d 5 2 ppold yxSE5 1 2 ppnew yxSE 32 pold xE 312 pnew xE 5 2 ppold yxSE 5 1 1 2 ppnew yxSE 处计算的初始值在和R0 SE E 330 2 0 ERRSE25520 2 0 11 算法步骤 1 依据上一次迭代中的 d 的符号来选择现在点 E 或 SE d0 1 R 2 用在上一次迭代计算的和来计算新的 d 3 用移到新象素点的二次差分值 并用它来更新和移到下一点 例 设 R 5 试用二阶差分法画园 xyd E SE 051 5 435 2 5 5 15 4 3 13 2 5 5 2 3 25 1 5 45 2 7 3 2 1 344 1 37 2 9 1 4 3 433 3 69 2 115 4 9 画第二个八分园 clear R 5 0 Y 1 R X 1 0 d 1 R deltaE 3 deltaSE 5 2 R x 0 y R while y x if dx 1 X i x Y i y if delta 0 delta1 2 delta y 1 if delta10 delta2 2 delta x 1 if delta2 0 direction 2 else direction 3 end else direction 2 end end switch direction case 1 x x 1 delta delta 2 x 1 case 2 x x 1 y y 1 delta delta 2 x y 1 case 3 y y 1 delta delta 2 y 1 end i i 1 end While end 利用对称性求其它七个八分园 X1 Y Y1 X X2 Y Y2 X X3 X Y3 Y X4 Y Y4 X X5 X Y5 Y X6 X Y6 Y X7 Y Y7 X plot X Y X Y o X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6 X7 Y7 14 title R 5 plot X Y X Y o X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6 X7 Y7 title R 5 15 实验三 椭园的生成算法 实验学时 4 实验类型 验证 综合 设计 实验要求 选修 一 实验目的 通过本实验 使学生了解并掌握在光栅显示系统中椭圆的生成和显示算法 二 实验内容 实现中点椭圆算法 三 实验原理 方法和手段 参见本指导书 四 实验组织运行要求 以学生自主训练为主的开放模式组织教学 五 实验条件 硬件平台 PC 软件 推荐 Windows 平台 Visual C matlab 六 实验步骤 1 掌握算法原理 2 依据算法 编写源程序并进行调试 3 对运行结果进行保存与分析 4 把源程序以文件的形式提交 5 按格式书写实验报告 七 思考题 八 实验报告 要求在指导书中明确学生实验报告的内容及具体要求 主要包括实验预习 实验记录 和实验报告三部分 基本内容详见附件 1 16 中点算法 算法原理 中点算法可以推广到一般二次曲线如椭圆 中心在原点的椭圆方程为 隐函数的形式为 a b 时 该方程表示的是圆 椭圆具有四对称性 可只考虑第一 象限的椭圆弧 椭圆上任一点 x y 处的法向量为 如在 p 点法线两分量相等 则 p 点将椭圆第一象限分成两部份 上半部份法向量在 y 方 向的分量比 x 方向的大 在下半部份相反 在 p 点 在当前中点处 法向量 2b2 Xp 1 2a2 Yp 0 5 的 y 分量比 x 分量大 即 b2 Xp 1 a2 Yp 0 5 而在下一中点 不等式改变方向 则说明椭圆弧从上部分转入下部分 与圆弧中点算法类似 确定一个象素 Pi后 接着在下两个候选象素的中点计算一个判 别式 d F M 的值 由判别式的符号确定更近的点 1 先讨论椭圆弧的上半部分 令 x 1 设 Pi xi yi 已确定 则下一对待选像素的中点是 M xi 1 yi 0 5 对初始点 0 b 第一个中点为 1 b 0 5 则 1 当 d 0 取 B 点 时 下一点 i 1 点的坐标为 xi 1 Yi 1 为确定 i 2 点取的下一个中点 22 22 1 xy ab y x b a 22222 0F x yb xa yab 22 22 xy FF N x yijf if jb xia y j xy 22 xy fforb xa y x y p x y N 上 下 B M TPi xi yi 222222 1 0 5 1 0 5 iiii dF MF xybxaya b 22 0 1 1 0 5 4 dFbbab 2 222 1 2 0 5 23 23 2 newiioldi ii dF xydbx dbxb xb 22 22222 11 2 1 5 23 22 23 22 22 newiioldii iiii dF xydbxay dbxayb xba y 17 M 的坐标为 xi 2 Yi 1 5 2 在每一次迭代中都要判断椭圆是否已从上半部进入了下半部 如果 b2x a2y 则椭圆进 入下半部份 此时令 y 1 且 1 若 d 0 取正下方像素 L 则 3 终止条件为 y 0 MidpointEllipe a b color int a b color int x y float d1 d2 x 0 y b d1 b b a a b 0 25 putpixel x y color while b b x 1 a a y 0 5 if d10 if d2 0 d2 b b 2 x 2 a a 2 y 3 x y else d2 a a 2 y 3 y putpixel x y color 下部分 2 22222 0 0 5 1dbxaya b LM R Pi xi yi 22 222 11 1 5 2 22 23 22 newpp oldpp oldii dF xy dbxay db xa ya 2 22 1 0 5 2 23 2 newpp oldp oldi dF xy day da ya 18 算法优化 提示 联解以下方程 得到椭圆上 下部分分界点 P 的坐标为 1 令 x 由 0 Px y 由 0 Py 从而避免上述算法中反复计算循环中止条件 2 采用增量算法 避免在计算d时的乘法和平方运算 22222 22 0F x yb xa yab b xa y 22 2222 ab abab 19 实验四 多边形填充算法 实验学时 4 实验类型 验证 综合 设计 实验要求 必修 一 实验目的 使学生掌握光栅显示系统中多边形的扫描转换和区域填充算法 掌握 4 连通与 8 连通 区域的扩展性 二 实验内容 实现多边形的扫描转换算法和区域填充算法 任选两个算法并实现 三 实验原理 方法和手段 对于设计性实验 应根据 由学生自行设计实验方案并加以实现的实验 内涵要求 注意省略由学生自主设计的 实验方案 四 实验组织运行要求 根据本实验的特点 要求和具体条件 采用 以学生自主训练为主的开放模式组织教 学 还是采用集中授课形式 须加以明确 五 实验条件 硬件平台 PC 软件 推荐 Windows 平台 Visual C matlab 六 实验步骤 1 掌握算法原理 2 依据算法 编写源程序并进行调试 3 对运行结果进行保存与分析 4 把源程序以文件的形式提交 5 按格式书写实验报告 七 思考题 八 实验报告 要求在指导书中明确学生实验报告的内容及具体要求 主要包括实验预习 实验记录 和实验报告三部分 基本内容详见附件 1 20 扫描线算法算法原理 利用相邻像素之间的连贯性 提高算法效率 根据多边形内部点的连续性知 一条扫 描线与多边形的交点中 入点和出点之间所有点都是多边形的内部点 所以 对所有的扫 描线填充入点到出点之间所有的点就可填充多边形 处理对象 非自交多边形 边与边之 间除了顶点外无其它交点 判断扫描线上 的点是否在多边形之内 根据多边形区域连 续性 分为 3 个步骤 求出扫描线与多边形所有边的交点 把这些交点的 x 坐标值以升序排列 对每一对交点间的区域进行填充 第三个步骤是从奇数个交点出发到 偶数个交点 如右图 对 y 8 的扫描线排 序 x 坐标得到的表是 2 4 9 13 然后对 交点 2 与 4 之间 9 与 13 之间的所有象素点进行填充 边界上的象素 左闭右开 下闭上开 将左边界和下边界的点算为内部 而 将右边界和上边界算为外部 顶点 上开下闭 几种特殊情况 1 扫描线交于一顶点 共享的两条边分另处于扫描线的两边 这时交点只取一个 如扫描 线 y 3 该点被填充一次 2 共享交点的两条边处于扫描线的上方 这时交点取二个 如 扫描线 y 1 该点被填充一次 3 共享交点的两条边处于扫描线的下方 这时交点取 0 个 如扫描线 y 9 无交点 不填 充 4 水平边在算法中不起任何作用 可不考虑 活性边表 提高效率 为了减少求交的计算量 要利用一条边与相继的两条扫描线的交点的连贯性 在处理 一条扫描线时只对活性边 与它相交的多边形的边 进行求交运算 把交点按 x 增加方向 存在一个链表 活性边表 中 活性边 与当前扫描线相交的边 活性边表 AEL 按交点 x 的增量顺序存放在一个链表中 该链表称作活性边表 AEL 10 24681012 0 2 4 6 8 1234 21 MM M 边填充算法 正负相消法 算法原理 对每一条扫描线和每条多边形边的交点 都将扫描线上右边的所有象素求余 偶数次 取余 结果不变 设 A 为一正整数 正整数 M 的余定义为 A M 记为 风 当计算机中用 n 位表示 M 时 可取 A 为 n 位能表示的最大整数 即 A 2n 1 可 知 即对 M 作偶数次取余 结果仍为 M 求余可用异或显示模式实现 以扫描线为中心的边缘填充法 设是当前扫描线与多边形的交点的 x 坐标数列 填充该扫描线上位于多边 m xxx 10 形内的区段由下列步骤完成 算法 1 以扫描线为中心的边缘填充算法 1 将当前扫描线上的所有象素着上颜色 M 2 求余 for i 0 i ymax Ct 1 else 0 下 if yxmax Cr 1 else 0 左 if x xmax Cl 1 else 0 对某线段的两个端点的区号进行位与运算 可知这两个端点是否同在视区的上 下 左 右 如果两端点的编码均为 0000 表示直线在窗口内 如果两端点的编码相与不为 0000 表示直线在窗口外 如果两端点的编码不全为 0000 但相与为 0000 则该直线部分可见 需计算直线 与窗口的交点 确定哪一部分可见 算法描述 算法描述 BOOL done draw done 表示是否完成 draw 表示是否可见 Unsigned char code1 code2 端点 1 端点 2 的编码 While done begin if 判断 code1 code2 若为第 1 种情况 begin done TRUE draw TRUE end else if 为第 2 种情况 begin done TRUE draw FALSE end else if 检查 code1 若在窗口内 第 3 种情况 1001 0001 0101 1000 0000 0100 1010 0010 0110 38 begin 交换端点及端点的编码 以左 上 右 下的次序对端点 1 进行判断及求交 将 交点的值赋给端点 1 end end 算法分析 算法分析 本算法的优点在于简单 易于实现 用编码方法可快速判断线段的完全可见和显然不 可见 他可以简单的描述为将直线在窗口左边的部分删去 按左 右 下 上的顺序依次 进行 处理之后 剩余部分就是可见的了 在这个算法中求交点是很重要的 他决定了算 法的速度 本算法对于其他形状的窗口是否同样有效就值得讨论了 这也证明了在图形算法中 没有几个是对大多数情况有效的 特别适用二种情形 大窗口场合 窗口特别小场合 光标拾取图形 光标看作小的裁剪 窗口 中点分割算法 算法原理 算法原理 基本思想 从 P0点出发 找出离 P0最近的可见点 A 从 P1点出发找出离 P1最近 的可见点 B 这两个可见点的 连线 AB 就是原线段的可见部 分 与 Cohen Sutherland 算 法一样 首先对线段端点进 行编码 并把线段与窗口的 关系分为三种情况 1 线段完全可见 2 显然不可见 3 其它 对前两种情况 进行一样的处理 对于第三种情况 用中点分割的方法求出线段与窗 口的交点 A B 分别为距 P0 P1最近的可见点 Pm 为 P0P1中点 中点分割法从 P0出发找距离 P0最近可见点 先求出 P0P1的中点 Pm 若 P0Pm不是显然不可见的 并且 P0Pm在窗口中有可见部分 则距 P0最近的可见 点一定落在 P0Pm上 所以用 P0Pm代替 P0P1 否则取 PmP1代替 P0P1 再对新的 P0P1求中点 Pm 重复上述过程 直到 PmP1长度小于给定的控制常数为 止 此时 Pm收敛于交点 从 P1出发找距离 P1最近可见点的方法类似 算法描述 算法描述 P0 P1 PmA B 39 算法分析 算法分析 与 Cohen Sutherlang 算法在思想上没有任何区别 计算裁剪线段与窗口各边的交点 中点算法 二分查找 C S 算法 直接计算 中点算法 更利于硬件实现 可看作 C S 算法 的一个特例 Liang Barsky 算法 算法原理 算法原理 设要裁剪的线段是 P1P2 P1P2和窗 口边界交于 A B C D 四点 见右图 算法的基本思想是从 A B 和 P1三点中找 出最靠近 P2的点 图中要找的点是 P1 从 C D 和 P2中找出最靠近 P1的点 图 中要找的点是 C 点 那么 P1C 就是 P1P2 线段上的可见部分 线段的参数表示 x x1 t x y y1 t y 0 t 1 P0P1显然不可见 显然不可见 Exit Y Y P0可见 可见 N N N D Pm P1 Exit P P0 P0P1不可见不可见 Pm P0 P1 2 P0Pm显然不可见 显然不可见 Y P Pm P1 Pm N P0 Pm Y XL XR YB YT P1 P2 A B C D t1 t2 t3 t4 P P P1 1 1 P P P2 2 2 t1 t4 P1 P2 t3 t2 40 x x2 x1 y y2 y1 窗口边界的四条边分为两类 始边和终边 有向线段 求出 P1P2与两条始边两条始边的交点参数 t1 t2 令 tL max t1 t2 0 则 tL即为三者中 离 p2最近的点的参数 求出 p1p2与两条终边两条终边的交点参数 t3 t4 令 tU min t3 t4 1 则 tU即为三者中离 p1最近的点的参数 若 tU tL 则可见线段区间为 tL tU 否则 p1p2完全不可见 如 p1 p2 tU t3 tL t2 tU tL 裁剪区域的内部可表示为 xL x xR yB y yT 将线段的参数表示 x x1 t x y y1 t y 0 t 1 x x2 x1 y y2 y0 代入 上述不等式 得到裁剪区域内部的另一种表示 t x x1 xL t x xR x1 t y y1 yB t y yT x1 即 ti Di Qi i L R B T QL x QR x QB y QT y DL x