计算机图形学课件：第5讲 直线的扫描转换

1、2020/10/8,1,本章内容,直线的扫描转换 圆与椭圆的扫描转换 区域填充 二维裁剪 字符生成 反走样,2020/10/8,2,三种绘制直线的算法,数值微分法 原理简单，实现方便，但在效率上低于后者。 用到了浮点数运算，不方便硬件实现。 中点画线法 Bresenham画线法 后两种算法都是较为常见的画线算法。对于直线段来说，两种方法是等同的和最有效的。,di-ei,2020/10/8,3,第二节 圆与椭圆的扫描转换,圆的扫描转换 中点画圆算法 Bresenham画圆算法 内接正多边形迫近法 椭圆的扫描转换 中点画法 若干相关问题,2020/10/8,4,圆的表示,原始定义：,等价定义,20

2、20/10/8,5,代数离散法,效率低,2020/10/8,6,圆的属性分析,对称性,正负划分性,2020/10/8,7,圆的扫描转换的数学模型,找到逼近如下圆弧线的像素点集合:,切线斜率范围: 取x为自变量,2020/10/8,8,中点画圆算法的原理,判别量定义:,?: 提高dk计算效率?,增量运算,2020/10/8,9,续：,浮点数!,2020/10/8,10,续：,设:,可替代的高效算法:,则判别量的初值为：,2020/10/8,11,结论,2020/10/8,12,二阶差分方法,任意多项式均可使用该方法实现增量计算,类似地:,2020/10/8,13,中点画圆算法伪代码,Void M

3、idPointCircle(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(yx) if(d0) d+=delta1; delta2+=2; else d+=delta2; delta2+=4; y- delta1+=2; x+; drawpiexl(x,y,color); drawotherpiexl(x,y,color); /while /end,2020/10/8,14,Bresenham画圆算法（1）,原理：选择与圆心距离与半径之差较小的一点。,2

4、020/10/8,15,Bresenham画圆算法(2),2020/10/8,16,Bresenham画圆算法（3）,以最高点为初始点，计算判别量初值 再根据判别量的正负确定递推关系 递推关系的确定需根据右图分别不同情况进行讨论（去掉绝对值符号，并进行化简）,2020/10/8,17,Bresenham画圆算法（4）,初始值的计算,利用增量计算方法加速判别参数的计算,注：比较其与中点画圆算法的判别参数。,圆的内接正多边形迫近法,2020/10/8,19,基础知识（1）-三角函数,2020/10/8,20,基础知识（2）-矩阵表示,表达式：,可写成矩阵形式：,2020/10/8,21,基础知识（

5、3）-矢量及其运算,2020/10/8,22,圆的内接正多边形迫近法(1),内接正n边形顶点,圆的多边形迫近,2020/10/8,23,圆的内接正多边形迫近法(2),使用增量计算确定多边形顶点：,同理:,2020/10/8,24,圆的内接正多边形迫近法(3),上述递推公式可用矩阵形式表示为：,该递推公式关于误差稳定。,2020/10/8,25,圆的内接正多边形迫近法(4),2020/10/8,26,圆的内接正多边形迫近法(5),改进的增量计算：使用两个初始点,该递推公式关于误差稳定,2020/10/8,27,圆的等面积正多边形迫近法,原理：,圆的等面积正多边形迫近法示意图,2020/10/8,

6、28,内容回顾,圆的扫描转换 中点扫描转换算法 Bresenham扫描转换算法 圆的内接正多边形迫近法 圆的等面积正多边形逼近法,椭圆的扫描转换算法,2020/10/8,30,椭圆弧的几何特点（1）,定义：到两个定点的距离之和为定长的点的集合。 假设：椭圆中心在坐标原点。,2020/10/8,31,椭圆弧的几何特点（2）,椭圆弧上一点处的切线,切线斜率,2020/10/8,32,椭圆弧的几何特点（3）,具有与圆弧类似的属性： 对称性 空间的正负划分性,2020/10/8,33,椭圆的扫描转换,问题：绘制第一象限内椭圆弧对应的像素点,解决方案:中点扫描转换算法 算法原理与圆弧的中点扫描转换算法相

7、同 注意：第一象限内椭圆弧切线斜率跨2范围： （-1，0以及（-，-1 切线斜率k=-1的点为扫描转换分割点,2020/10/8,34,第一象限内椭圆弧的划分,割点位置计算: 切线斜率为1的点 梯度的定义：,等价于计算梯度矢量斜率为1的点,2020/10/8,35,椭圆的中点扫描转换算法,区域 1-2条件：下一点满足,2020/10/8,36,椭圆弧上部的扫描转换（1）,椭圆弧上部对应的决策参数：,根据决策参数的取值，成立：,2020/10/8,37,椭圆弧上部的扫描转换（2）,决策参数的递推计算,初始条件：,2020/10/8,38,椭圆弧上部的扫描转换（3）,2020/10/8,39,椭圆

8、弧上部的扫描转换（4）,2020/10/8,40,椭圆弧上部的扫描转换（5）,递推计算过程：,2020/10/8,41,椭圆弧下部的扫描转换（1）,同理对椭圆弧的下部进行扫描转换。,2020/10/8,42,椭圆弧下部的扫描转换（2）,判别参数的递推计算:,2020/10/8,43,椭圆弧的扫描转换,从(0,ry)开始,绘制椭圆弧的上部,采用判别参数为d1i; 当绘制当前点满足切线斜率大于-1时,椭圆弧上部绘制完成; 从(rx,0)开始,绘制椭圆弧的下部,采用判别参数为d2i; 当绘制当前点的坐标与椭圆弧上部的最后一点交叉时,椭圆弧下部绘制完成; 根据椭圆的对称性完成整个椭圆的绘制.,2020

9、/10/8,44,若干相关问题(1),曲线的扫描转换： 一般方法：直线段逼近 注意象素点的等距。为此可使用曲线的参数表示，或按照曲线斜率选择自变量，而从显式表示中生成等距位置点。,正负法： 尤其适合易画曲线： 具有正负划分性、平坦性、连续性 初始定向：起始点切线方向； 前进规则：正负划分性确定；,2020/10/8,45,若干相关问题(2),直线绘制算法的并行实现： 任何线生成算法都可以通过线段分割而适用于并行实现。 有足够多的处理器时，按照屏幕的不同区域分配处理器。,2020/10/8,46,若干相关问题(3),图元几何尺寸的保留： 在扫描转换过程中注意象素集合的实际尺寸，如线段的始末点坐标

10、的定义。 不同图元的尺寸变化不同。,2020/10/8,47,若干相关问题（4）,线宽控制 标准线宽的直线被扫描转换为一个象素宽的直线段。 其它线宽的实现可以采用笔或刷的方式。 通过沿相邻平行线路径画额外的象素可以定义标准线宽的正整数倍的其它线宽。 线刷子方法实现的线宽控制：分水平和垂直两种。 垂直线刷子：一般地，对于任意线段，当某点切矢斜率在-1，1之间时，扫描转换过程是：给定x以固定步长，确定y方向的增量，所以可用垂直线刷子扫过象素，即得到所要求的线段。,水平线刷子：对于其切矢斜率在-1，1之外的线段，可用水平线刷子扫过即可。,2020/10/8,48,线刷子的设计简单高效。但它存在如图所

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