计算机图形学ppt课件.ppt

第二章光栅图形学 2 1直线段的扫描转换算法2 2圆弧的扫描转换算法2 3多边形的扫描转换与区域填充2 4字符2 5裁剪2 6反走样2 7消隐 1 2 1直线段的扫描转换算法 数值微分法 DDA算法 中点画线法Bresenham画线算法 2 数值微分法 DigitalDifferentialAnalyzer 基本思想假定直线的起点 终点分别为 x0 y0 x1 y1 且都为整数 已知过端点P0 x0 y0 P1 x1 y1 的直线段L P0 P1 直线斜率为 按照y kx b计算相应的y坐标 3 数值微分 DDA 法 设步长为 x 有xi 1 xi x则yi 1 kxi 1 b kxi k x b yi k x因为光栅点的单位是1 对每一个x方向的增量 x 1时 有yi 1 yi k 即 当x每递增1 y递增k 即直线斜率 经过round 函数处理得到显示的光栅点 x round y 坐标 xi 1 xi 1yi 1 yi k 4 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 数值微分 DDA 法 5 例 画直线段P0 0 0 P1 5 2 xy 0 5int y 0 5 00 0 50 10 4 0 50 20 8 0 51 31 2 0 51 41 6 0 52 52 0 0 52 优点 在同一坐标上 不可能连续停留两次 缺点 在此算法中 y k必须是float 且每一步都必须对y进行舍入取整 不利于硬件实现 算法特点 注意 网格点表示像素 6 增量算法 在一个迭代算法中 如果每一步的x y值是用前一步的值加上一个增量来获得 则称为增量算法 DDA算法就是一个增量算法 缺点注意上述分析的算法仅适用于 k 1的情形 在这种情况下 x每增加1 y最多增加1 当 k 1时 必须把x y地位互换 y每增加1 x相应增加1 k 在此算法中 y k必须是float 且每一步都必须对y进行舍入取整 有浮点数取整运算 不利于硬件实现 效率低 数值微分 DDA 法 7 原理 假定直线斜率0 K 1 且已确定点像素点P Xp Yp 则下一个与直线最接近的像素只能是P1点或P2点 设M为中点 Q为交点问题 现需判断距离理想直线最近的下一个像素点 中点画线法 8 当M在Q的下方 P2离直线更近更近 取P2 M在Q的上方 P1离直线更近更近 取P1M与Q重合 P1 P2任取一点 算法原理 如何判断M点在Q点上方还是在Q点下方 9 已知 线段两端点 x0 y0 x1 y1 直线方程为 F x y ax by c 0其中a y0 y1 b x1 x0 c x0y1 x1y0 M 中点画线法 欲判断M点是在Q点上方还是在Q点下方 只需把M代入F x y 并检查它的符号 10 构造判别式 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 能否采用增量算法呢 中点画线法 11 若d 0 中点M在直线上方 取正右方像素P1 Xp 1 Yp 再下一个像素的判别式为 d1 F Xp 1 1 Yp 0 5 a Xp 2 b Yp 0 5 c d ad的增量为a若d 0 中点M在直线下方 取右上方像素P2 Xp 1 Yp 1 再下一个像素的判别式为 d2 F Xp 1 1 Yp 1 0 5 a Xp 2 b Yp 1 5 c d a bd的增量为a b 分两种情形考虑再下一个像素的判定 12 画线从 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来摆脱小数 提高效率 优点 只有整数运算 不含乘除法可用硬件实现 中点画线法 因 X0 Y0 在直线上 所以F X0 Y0 0 13 voidMidpointLine intx0 inty0 intx1 inty1 intcolor inta 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 drawpixel x y color while x x1 if d 0 x y d d2 else x d d1 drawpixel x y color while midPointLine 中点画线法 14 例 用中点画线法P0 0 0 P1 5 2 a y0 y1 2b x1 x0 5d0 2a b 1d1 2a 4d2 2 a b 6 Ixiyid 1001 210 3 3213 431 1 5425 6521 15 Bresenham算法 基本思想过各行各列像素中心构造一组虚拟网格线 按直线从起点到终点的顺序计算直线与各垂直网格线的交点 然后根据误差项的符号确定该列像素中与此交点最近的像素 16 设直线方程为 其中k dy dx 因为直线的起始点在像素中心 所以误差项d的初值d0 0 X下标每增加1 d的值相应递增直线的斜率值k 即d d k 一旦d 1 就把它减去1 这样保证d在0 1之间 当d 0 5时 最接近于当前像素的右上方像素 xi 1 yi 1 而当d 0 5时 更接近于右方像素 xi 1 yi 为方便计算 令e d 0 5 e的初值为 0 5 增量为k 当e 0时 取当前像素 xi yi 的右上方像素 xi 1 yi 1 而当e 0时 更接近于右方像素 xi 1 yi Bresenham算法 17 算法步骤为 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算法 18 程序如下 BresenhamLine intx0 inty0 intx1 inty1 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 Bresenham算法 19 例 Line P0 0 0 P1 5 2 k dy dx 0 4 xye 00 0 5 10 0 1 21 0 7 31 0 3 42 0 9 52 0 5 缺点 在此算法中 计算直线斜率与误差项时用到了小数与除法 不利于硬件实现 可以改用整数以避免除法 20 Bresenham算法 改进 用2e x来替换ee初 x 每走一步有e e 2 y if e 0 thene e 2 x 21 算法步骤 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算法 22 程序如下 BresenhamLine intx0 inty0 intx1 inty1 intcolor intx y dx dy e dx x1 x0 dy y1 y0 e dx x x0 y y0 for i 0 i 0 y e e 2 dx 优点整数运算 速度快精度高乘2运算可用移位实现 适于硬件实现 23 斜率不同时 以上讨论的是0 k 1的情况 即0 y x的情况 若是0 x y的情况 则需将x和y的位置交换 方向不同时 若 y 0或 x 0时 要将算法中的y y 1换成y y 1 x x 1换成x x 1 思考讨论 24 几种画线算法的比较 DDA算法直观 易于实现 但是x y 和k必须用浮点数表示 而且每一步都需要对x和y进行舍入取整 不利于硬件实现 中点算法可以替换成整数运算 便于硬件实现 Bresenham算法不计算斜率 不用浮点数 只做整数的加减运算或乘2运算 而乘2运算可以用移位操作来实现 因此Bresenham算法是速度最快的 25 实验一直线的生成 在VisualC 6 0环境中设计MFC单文档程序 利用消息处理函数 搭建能运行图形算法程序的平台 实现直线段的3种生成算法 DDA算法 考虑k大于或小于等于1的情况 中点法和Bresenham算法 原算法和改进算法 26 第二章光栅图形学 2 1直线段的扫描转换算法2 2圆弧的扫描转换算法2 3多边形的扫描转换与区域填充2 4字符2 5裁剪2 6反走样2 7消隐 27 2 2圆弧的扫描转换算法 直接离散生成算法中点画圆法Bresenham画圆算法椭圆的中点画法 28 圆弧扫描算法 下面仅以圆心在原点 半径R为整数的圆为例 讨论圆的生成算法 假设圆的方程为 x2 y2 R2圆的八对称性可以用四条对称轴x 0 y 0 x y x y把圆分成8等份 只要绘制出第一象限内的1 8圆弧 根据对称性就可绘制出整圆 这称为八分法画圆算法 29 P y x P y x P x y P x y P y x P y x P x y 假定第一象限内的任意点为P x y 可以确定另外7个点 30 圆弧扫描算法 两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点 计算量大所画像素位置间的间距不一致 不均匀 31 圆弧扫描算法 SimpleCircle intr intcolor intx y for x 0 x r x y Round sqrt r r x x circlepoints x y color ParameterCircle intr intcolor intx y for floatt 0 t 2 t 0 05 x Round r cos t y Round r sin t circlepoints x y color 32 第二个8分圆P Xp Yp P为当前点亮像素 那么 下一个点亮的像素可能是P1 Xp 1 Yp 或P2 Xp 1 Yp 1 中点画圆法 33 中点画圆法 F X Y X2 Y2 R2 0中点M Xp 1 Yp 0 5 当F M 0时 M在圆内 P1距离圆弧近 取P1当F M 0时 M在圆外 P2距离圆弧近 取P2 34 中点画圆法 若d 0 取P1为下一像素 再下一像素的判别式为初始像素是 0 R 判别式d的初值为 P1 Xp 1 Yp P2 Xp 1 Yp 1 35 算法步骤 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 否则结束 中点画圆法 一般算法 36 MidpointCircle intr intcolor intx y floatd x 0 y r d 1 25 r circlepoints x y color while x y if d 0 d 2 x 3 x else d 2 x y 5 x y circlepoints x y color 中点画圆法 一般算法 思考题 如何将上面算法中的浮点数改写成整数 将乘法运算改成加法运算 即仅用整数实现中点画圆法 以进一步提高算法的效率 37 为了进一步提高算法的效率 可以将上面的算法中的浮点数改写成整数 将乘法运算改成加法运算 即仅用整数实现中点画圆法 因为中点画圆算法的半径是整数 而用于该算法符号判别的变量d采用浮点运算 会花费较多的时间 为了将其改造成整数计算 对d作如下变换 使用d d 0 25代替dd 1 R判别式d 0等价于d 0 25 在d 为整数的情况下 d 0 25与d 0等价 仍将d 写成d 可得到中点圆整数算法 中点画圆法 38 算法步骤 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 否则结束 程序 中点画圆法 整数算法 39 MidpointCircleInt intr intcolor intx y d x 0 y r d 1 r circlepoints x y color while x y if d 0 d 2 x 3 x else d 2 x y 5 x y circlepoints x y color 中点画圆法 整数算法 40 如图中点Pi 1是已选中的一个表示圆弧上的点 根据弧的走向 下一个点应该从Hi或者Li中选择 选择的原则是 考察精确值是靠近Hi还是Li 即精确值y是靠近yi还是yi 1假设圆的半径为R 计算式为y2 R2 xi 1 2令d1 d2分别为yi Hi 到y和yi 1 Li 到y的距离 可知 d1 yi2 y2 yi2 R2 xi 1 2d2 y2 yi 1 2 R2 xi 1 2 yi 1 2 Bresenham画圆算法 41 1 如果di 0 则y yi 即选择当前像素的正右方作为下一个像素 递推公式为 2 如果di 0 则y yi 1 即选择当前像素的右下方作为下一个像素 递推公式为 3 计算判别式的初值 初始点为 0 R 则 令判断式di d1 d2 并代入d1 d2 则有 42 Bresenham画圆算法 算法步骤 1 求误差初值d1 3 2r i 1 画点 0 r 2 求下一个光栅位置 其中xi 1 xi 1 如果di 0则yi 1 yi 否则 yi 1 yi 1 3 画点 xi 1 yi 1 4 计算下一个误差 如果di 0则di 1 di 4xi 6 否则di 1 di 4 xi yi 10 5 i i 1 如果x y则结束 否则返回步骤2 程序 43 b a x y 中心在原点 长半轴为a 短半轴为b的标准椭圆 x y x y x y x y 椭圆的扫描转换 44 椭圆的扫描转换 由于椭圆的对称性 只考虑第一象限椭圆弧的生成由于椭圆弧的弧度不一致 所以在处理时要把它分成上下两部分 以切线斜率为 1的点作为分界点 45 在上半部分 法向量的y分量大在下半部分 法向量的x分量大 上半部分 下半部分 法向量两分量相等 M1 M2 椭圆上某一点的法向量 若在当前中点 法向量的y分量比x分量大 即 而在下一个中点 不等号改变方向 则说明椭圆弧从上部分转入下部分 46 算法原理 P u y x P d P P l P r P 椭圆的中点画法 与圆弧中点算法类似 确定一个像素后 接着在两个候选像素的中点计算一个判别式的值 由判别式的符号确定更近的点 47 先推导上半部分的椭圆绘制公式 p x i y i p u x i 1 y i p d x i 1 y i 1 M x i 1 y i 0 5 上半部分椭圆弧的绘制原理 设椭圆当前点为pi xi yi 对应的下一候选像素是正右方的pu xi 1 yi 或右下方的pd xi 1 yi 1 48 判别式其中点是M xi 1 yi 0 5 若d1 0 中点在椭圆内 取正右方像素Pu xi 1 yi 若d1 0 中点在椭圆外 取右下方像素Pd xi 1 yi 1 p x i y i p u x i 1 y i p d x i 1 y i 1 M x i 1 y i 0 5 上半部分椭圆弧的绘制原理 49 判别式递推公式为 d1 0 50 d1 0 判别式递推公式为 判别式的初始值 51 p x i y i p l x i y i 1 p r x i 1 y i 1 M x i 1 y i 0 5 下半部分椭圆弧的绘制原理 再来推导椭圆弧下半部分的绘制公式原理 设椭圆当前点为pi xi yi 对应的下一候选像素是正下方的pl xi yi 1 或右下方的pr xi 1 yi 1 52 判别式其中点是M xi 0 5 yi 1 若d2 0 中点在椭圆外 取正下方像素Pl xi yi 1 若d2 0 中点在椭圆内 取右下方像素Pr