《计算机图形学教学资料》第5讲.ppt

Interactive Computer Graphics-交互式计算机图形学2024/8/251本章内容v直线的扫描转换v圆与椭圆的扫描转换v区域填充v二维裁剪v字符生成v反走样Interactive Computer Graphics-交互式计算机图形学2024/8/252三种绘制直线的算法v数值微分法v原理简单，实现方便，但在效率上低于后者v用到了浮点数运算，不方便硬件实现v中点画线法vBresenham画线法 后两种算法都是较为常见的画线算法对于直线段来说，两种方法是等同的和最有效的di-eiInteractive Computer Graphics-交互式计算机图形学2024/8/253第二节 圆与椭圆的扫描转换v圆的扫描转换v中点画圆算法vBresenham画圆算法v内接正多边形迫近法v椭圆的扫描转换v中点画法v若干相关问题Interactive Computer Graphics-交互式计算机图形学2024/8/254圆的表示 原始定义： 等价定义 v v v Interactive Computer Graphics-交互式计算机图形学2024/8/255代数离散法效率低Interactive Computer Graphics-交互式计算机图形学2024/8/256圆的属性分析对称性(y,x)(y,-x)(x,-y)(-x,-y)(-y,-x)(-y,x)(-x,y)(x,y)正负划分性Interactive Computer Graphics-交互式计算机图形学2024/8/257圆的扫描转换的数学模型v找到逼近如下圆弧线的像素点集合: 切线斜率范围: 取x为自变量Interactive Computer Graphics-交互式计算机图形学2024/8/258中点画圆算法的原理判别量定义:下一象素的3位置选项当前象素的2位置选项P=(xk,yk)MSEMEMSEE前一个象素位置 ?: 提高dk计算效率?增量运算Interactive Computer Graphics-交互式计算机图形学2024/8/259续：浮点数浮点数!Interactive Computer Graphics-交互式计算机图形学2024/8/2510续：设:可替代的高效算法:则判别量的初值为： Interactive Computer Graphics-交互式计算机图形学2024/8/2511结论 Interactive Computer Graphics-交互式计算机图形学2024/8/2512二阶差分方法任意多项式均可使用该方法实现增量计算类似地:Interactive Computer Graphics-交互式计算机图形学2024/8/2513中点画圆算法伪代码Void MidPointCircle(int r, int color){ int x,y,d; x=0;y=r;d=1-r; delta1=3;delta2=5-2r; drawpiexl(x,y,color); while(y>x){ if(d<0){ d+=delta1; delta2+=2; } else{ d+=delta2; delta2+=4; y--} delta1+=2; x++; drawpiexl(x,y,color); drawotherpiexl(x,y,color); }//while}//endInteractive Computer Graphics-交互式计算机图形学2024/8/2514Bresenham画圆算法（1）v原理：选择与圆心距离与半径之差较小的一点。

 圆弧上可选点情况Interactive Computer Graphics-交互式计算机图形学2024/8/2515Bresenham画圆算法(2)Interactive Computer Graphics-交互式计算机图形学2024/8/2516Bresenham画圆算法（3）•以最高点为初始点，计算判别量初值•再根据判别量的正负确定递推关系•递推关系的确定需根据右图分别不同情况进行讨论（去掉绝对值符号，并进行化简） 圆弧上可选点情况Interactive Computer Graphics-交互式计算机图形学2024/8/2517Bresenham画圆算法（4）v初始值的计算n利用增量计算方法加速判别参数的计算注：比较其与中点画圆算法的判别参数圆的内接正多边形迫近法Interactive Computer Graphics-交互式计算机图形学2024/8/2519基础知识（1）--三角函数Interactive Computer Graphics-交互式计算机图形学2024/8/2520基础知识（2）--矩阵表示表达式：可写成矩阵形式：Interactive Computer Graphics-交互式计算机图形学2024/8/2521基础知识（3）--矢量及其运算Interactive Computer Graphics-交互式计算机图形学2024/8/2522圆的内接正多边形迫近法(1)内接正n边形顶点圆的多边形迫近Interactive Computer Graphics-交互式计算机图形学2024/8/2523圆的内接正多边形迫近法(2)v使用增量计算确定多边形顶点：同理:Interactive Computer Graphics-交互式计算机图形学2024/8/2524圆的内接正多边形迫近法(3)上述递推公式可用矩阵形式表示为： 该递推公式关于误差稳定。

Interactive Computer Graphics-交互式计算机图形学2024/8/2525圆的内接正多边形迫近法(4)Interactive Computer Graphics-交互式计算机图形学2024/8/2526圆的内接正多边形迫近法(5)n改进的增量计算：使用两个初始点该递推公式关于误差稳定Interactive Computer Graphics-交互式计算机图形学2024/8/2527圆的等面积正多边形迫近法v原理： 圆的等面积正多边形迫近法示意图Interactive Computer Graphics-交互式计算机图形学2024/8/2528内容回顾v圆的扫描转换v中点扫描转换算法vBresenham扫描转换算法v圆的内接正多边形迫近法v圆的等面积正多边形逼近法椭圆的扫描转换算法 Interactive Computer Graphics-交互式计算机图形学2024/8/2530椭圆弧的几何特点（1）v定义：到两个定点的距离之和为定长的点的集合v假设：椭圆中心在坐标原点ryrx-ry-rxXYInteractive Computer Graphics-交互式计算机图形学2024/8/2531椭圆弧的几何特点（2）v椭圆弧上一点处的切线切线斜率Interactive Computer Graphics-交互式计算机图形学2024/8/2532椭圆弧的几何特点（3）n具有与圆弧类似的属性：n对称性n空间的正负划分性ryrx-ry-rxXYInteractive Computer Graphics-交互式计算机图形学2024/8/2533椭圆的扫描转换n问题：绘制第一象限内椭圆弧对应的像素点 n 解决方案:中点扫描转换算法n 算法原理与圆弧的中点扫描转换算法相同n 注意：第一象限内椭圆弧切线斜率跨2范围：（-1，0]以及（-∞，-1]切线斜率k=-1的点为扫描转换分割点Interactive Computer Graphics-交互式计算机图形学2024/8/2534第一象限内椭圆弧的划分v割点位置计算:v 切线斜率为–1的点v梯度的定义：区域 1区域 2切 线 斜率= -1法矢量v 等价于计算梯度矢量斜率为1的点j  i梯度矢量x,y方向分量相等Interactive Computer Graphics-交互式计算机图形学2024/8/2535椭圆的中点扫描转换算法区域 1->2条件：下一点满足 ES区域 1区域 2切线斜率= -1梯度矢量区域2内?Interactive Computer Graphics-交互式计算机图形学2024/8/2536椭圆弧上部的扫描转换（1）n椭圆弧上部对应的决策参数：v根据决策参数的取值，成立：Interactive Computer Graphics-交互式计算机图形学2024/8/2537椭圆弧上部的扫描转换（2）n决策参数的递推计算初始条件：Interactive Computer Graphics-交互式计算机图形学2024/8/2538椭圆弧上部的扫描转换（3）Interactive Computer Graphics-交互式计算机图形学2024/8/2539椭圆弧上部的扫描转换（4）Interactive Computer Graphics-交互式计算机图形学2024/8/2540椭圆弧上部的扫描转换（5）递推计算过程：Interactive Computer Graphics-交互式计算机图形学2024/8/2541椭圆弧下部的扫描转换（1）v同理对椭圆弧的下部进行扫描转换。

Interactive Computer Graphics-交互式计算机图形学2024/8/2542椭圆弧下部的扫描转换（2）判别参数的递推计算:Interactive Computer Graphics-交互式计算机图形学2024/8/2543椭圆弧的扫描转换1.从(0,ry)开始,绘制椭圆弧的上部,采用判别参数为d1i;2.当绘制当前点满足切线斜率大于-1时,椭圆弧上部绘制完成;3.从(rx,0)开始,绘制椭圆弧的下部,采用判别参数为d2i;4.当绘制当前点的坐标与椭圆弧上部的最后一点交叉时,椭圆弧下部绘制完成;5.根据椭圆的对称性完成整个椭圆的绘制.Interactive Computer Graphics-交互式计算机图形学2024/8/2544若干相关问题(1)v曲线的扫描转换：v一般方法：直线段逼近 注意象素点的等距为此可使用曲线的参数表示，或按照曲线斜率选择自变量，而从显式表示中生成等距位置点n正负法：尤其适合易画曲线：具有正负划分性、平坦性、连续性•初始定向：起始点切线方向；•前进规则：正负划分性确定；Interactive Computer Graphics-交互式计算机图形学2024/8/2545若干相关问题(2)v直线绘制算法的并行实现：v任何线生成算法都可以通过线段分割而适用于并行实现。

v有足够多的处理器时，按照屏幕的不同区域分配处理器Interactive Computer Graphics-交互式计算机图形学2024/8/2546若干相关问题(3)v图元几何尺寸的保留：v在扫描转换过程中注意象素集合的实际尺寸，如线段的始末点坐标的定义v不同图元的尺寸变化不同Interactive Computer Graphics-交互式计算机图形学2024/8/2547若干相关问题（4） 线宽控制v标准线宽的直线被扫描转换为一个象素宽的直线段v其它线宽的实现可以采用笔或刷的方式•通过沿相邻平行线路径画额外的象素可以定义标准线宽的正整数倍的其它线宽v线刷子方法实现的线宽控制：分水平和垂直两种•垂直线刷子：一般地，对于任意线段，当某点切矢斜率在[-1，1]之间时，扫描转换过程是：给定x以固定步长，确定y方向的增量，所以可用垂直线刷子扫过象素，即得到所要求的线段•水平线刷子：对于其切矢斜率在[-1，1]之外的线段，可用水平线刷子扫过即可Interactive Computer Graphics-交互式计算机图形学2024/8/2548 线刷子的设计简单高效但它存在如图所示的缺陷。

线刷子方案的缺陷Interactive Computer Graphics-交互式计算机图形学2024/8/2549v采用矩形刷子可以避免第一个缺陷 需设计新的数据结构以避免象素的重复绘制v采用画轮廓线再填充的方法可以避免上述三种缺陷解决方案Interactive Computer Graphics-交互式计算机图形学2024/8/2550线型控制v线型属性：实线、虚线和点划线等v线型的实现方式：通过设置沿线路径显示的实线段的长度和间距来修改画线算法得到不同类型的线v例如：用布尔数组定义出指定的类型，如间距为5的虚线：1111100000（1表示绘制点，0表示不绘制点），并使其在直线段的有效定义范围内不断重复，即扫描转换后得到的象素点依序与线型定义数组一一对应，并根据线型定义数组决定该象素点的绘制与否若干相关问题（5）Interactive Computer Graphics-交互式计算机图形学2024/8/2551线型的精确控制v采用上述固定划线长度的实现方法会在直线方向定义不同时产生出不等长的划线段原因在于相同个数的象素沿不同方向将生成不同长度的线段v为实现精确的线型定义，应按照线的斜率调整线型定义数组中实线段和空白段的象素数目。

Interactive Computer Graphics-交互式计算机图形学2024/8/2552v另一种精确定义线型的方法是：将线上的每一段实划线作为一段单独的线段，定位其始末端点坐标，再调用直线的扫描转换算法实现绘制线型的精确控制Interactive Computer Graphics-交互式计算机图形学2024/8/2553小结v圆的扫描转换v中点画圆算法、Bresenham画圆算法v圆的内接正多边形迫近法v椭圆的扫描转换—中点转换算法v曲线的扫描转换—直线近似法、正负法v属性控制—线宽、线型的实现Interactive Computer Graphics-交互式计算机图形学2024/8/2554作业1.请写出中点算法绘制椭圆弧下部时使用的判别参数的递推计算公式2.请用伪代码的方式写出椭圆的中点绘制算法。