《《计算机图形学教学资料》》由会员分享,可在线阅读,更多相关《《计算机图形学教学资料》(35页珍藏版)》请在金锄头文库上搜索。
1、Chapter 3 Basic Raster Graphics Algorithms for Drawing 2D Primitives基本二维图元的生成算法1Scan-conversion(扫描转换): 确定图形对应的象素集合及其颜色,用于显示一个图形的过程,也称为图形的光栅化光栅化。2本章内容(outline)n直线的扫描转换(SCAN CONVERTING LINES)n圆与椭圆的扫描转换(SCAN CONVERTING CIRCLE AND ELLIPSE)n区域填充(FILLING REGION)n字符生成(GENERATING CHARACTERS)n反走样(ANTIALIASIN
2、G)n二维裁剪(2D CLIPPING)3图形扫描转换(scan-conversion)Scan-conversion: 确定图形对应的象素集合及其颜色,用于显示一个图形的过程,称为图形的扫描转扫描转换换或光栅化光栅化。图形扫描转换分为两步:1、确定有关(组成图形的)象素;2、用图形的颜色或其他属性对象素进行写操作。 第2步通常是通过调用设备驱动程序完成的,不属于计算机图形学的研究范围。计算机图形学研究前者,即如何确定最佳逼近于最佳逼近于图形的象素集。4n问题 给定直线段的两个端点P0(x0,y0)和P1(x1,y1), 把其在光栅扫描显示器上显示出来.n描述 理想的直线段:没有线宽,由无数个
3、点构成 光栅扫描显示器上:有限个不重叠象素组成SCAN CONVERTING LINES(直线的扫描转换)5p0p1最佳表示最佳表示:用最靠近理想直线的一些网格点(象素)来代表直线(即确定最佳的最近点最近点和最大似点最大似点的集合)。直线的表示直线的表示(the representation of lines)6数值微分法(1)(DDA-Digital Differential Analyzer) X的变化大于y的变化方法:最简单方法:最简单方法:利用直线方程直接计算象素集。但方法用到了浮点数的乘法,加法和取整运算,影响效率。7数值微分法(2)8令yir= round(yi)其中,round(
4、)表示对yi进行四舍五入。则所求点坐标为(xi+1, round(yi+1)其中, xi+1 = xi +1, yi+1 = yi +m;数值微分法(3)9数值微分法(4)n待解决问题 若|m|1,则x向每变化1个单位,y向有可能超出1个步长。p1p0解决方法:此时应令yi 为自变量。10数值微分法(5)在算法中若能保证在一个方向上增量为1,在另一个方向的增量 1,就能保证产生最大似点集,从而克服前述问题。最大步长(步距)步进方向: 的方向11数值微分法(6)void Line ( /* Assumes -1ml,x0x1 */ int x0, int y0, /* Left endpoint
5、 */ int x1, int y1, /* Right endpoint */ int value) /* Color value to place in lines pixels */ int x; /* x runs from x0 to x1 in unit increments*/ double dy = y1 y0: double dx = x1 - x0; double m = dy / dx; double y = y0; for (x = x0; x = x1; x+) PutPixel (x, Round (y), value); /* Set pixel to value
6、 */ y += m; /* Step y by slope m */ /* Line */ The incremental line scan-conversion algorithm.12n算法优点:算法优点:简单、自然,消除了最简单方法中的浮点数的乘法。n算法缺点:算法缺点:用到了浮点加法运算和取整运算,计算效率低。n自变量的选择可根据斜率确定,以得到最佳的直线效果:数值微分法(7)13中点画线法 (Midpoint Line Algorithm) (1)n问题引出问题引出 为解决DDA算法中需要浮点数进行加运算,且输出时需取整的不利条件,可以用中点画线法。 假假设设直直线线的的斜斜率率
7、m0,1m0,1,两两个个端端点点分分别别是(是(x0,y0x0,y0), ,(x1,y1x1,y1)。)。14P(xp,yp)P1(xp+1,yp)中点判别方法示意图QP2(xp+1,yp+1)MMidpoint Line Algorithm(2)思想思想当 前 一 点 已 确 定 ,用P(xp,yp)来代表时,下一点仅可能在P1和P2中选用M表示P1,P2的中点,M(xp+1,yp+0.5)。Q是理想直线上x=xp+1处的点.比较M和Q的位置关系,可以确定下一点的走向.15比较比较M和和Q:若M位于Q的下方,即yM yQ ,则应取p1点;原则原则: 当两侯选点的中点落在直线下方时,选较高点
8、,否则选较低点。Midpoint Line Algorithm (3)P(xp,yp)P1(xp+1,yp)中点判别方法示意图QP2(xp+1,yp+1)M16Midpoint Line Algorithm (4)n定义直线函数:n特点:由于Q点的 f(xQ, yQ)=0,若能计算出中点M的f(xM, yM)的正负,则可判定出Q点和M点的位置关系。其中:ay0y1,bx1x0,cx0y1x1y017Midpoint Line Algorithm (5)nDefine decision function(构造判别函数):nDefine decision variable(引入判别参数):其中:a
9、y0y1,bx1x0,cx0y1x1y018Midpoint Line Algorithm (6)n算法描述: 斜率m0,1时n问题:如何快速计算判别参数的值?采用增量计算方法优化判别参数的计算P(xp,yp)P1(xp+1,yp)QP2(xp+1,yp+1)M19图4-2 中点绘线法原理示意图如黄色线所示情形Midpoint Line Algorithm (7)20Midpoint Line Algorithm (8)如蓝色线所示情形21Midpoint Line Algorithm (9)q第一个决策变量 dstart 为q第1个中点在 (x0+ 1, y0+0.5), 因为(x0,y0)
10、点在直线上,ax0by0c0,则22算法的递推公式是:Midpoint Line Algorithm (10)递推公式:d的初值中存在小数。由于判别时只考虑d的符号,且d的增量都是整数,为消除浮点数计算,可在d的计算公式两侧同乘2。并仍用d表示2d。23算法公式是:Midpoint Line Algorithm (11)问题:以上分析过程只考虑了直线斜率m0,1的情况。递推公式:24Midpoint Line Algorithm (12)25此时,可利用两候选点的中点与直线的位置关系,选出更接近直线的候选点Midpoint Line Algorithm (13)26点/线位置关系的判别计算采用
11、增量计算方法优化判别公式的计算Midpoint Line Algorithm (14)27例:用中点画线法光栅化一条连接两点(0,0)和(5,2)的直 线段,写出计算过程。Example(1) 斜率 28xydOut pixel初始124450123450011221-33-151(0,0)(1,0)(2,1)(3,1)(4,2)(5,2)递推如下:Example(2)2945632100 1 2 33 4 5 6 7The midpoint line from point (0, 0) to point (5, 2).Example(3)30P(xi,yir)P1(xi+1,yir)Bres
12、enham 判别方法示意图QP2(xi+1,yir+1)Bresenham Line Algorithm(1)MP(xi,yi)(xi+1,yi+1)构造判别参数: i+1i+1= yi+1 - yir31Bresenham Line Algorithm(2)判别参数:i+1i+1= yi+1 - yir 当i+1i+10 时, 选择P2(xi+1,yir+1)点 当i+1 i+1 0时, 选择P1(xi+1,yir)点采用增量计算方法优化判别参数的计算第i+2次的i+2 i+2 yi+2 yi+1r 32Bresenham Line Algorithm(3)第i+1次的i+1i+1= yi+
13、1 - yir 第i+2次的i+2 i+2 yi+2 yi+1r (a)若在 i+1次时,i+1 i+1 0, 则选择P1(xi+1,yir)点i+2 i+2 =yi+2 yi+1r = yi+1 + m yir = i+1 i+1 + m33Bresenham Line Algorithm(3)第i+2次的i+2 i+2 yi+2 yi+1r (b) 若在 i+1次时,i+1 i+1 0,则选择P2(xi+1,yir+1)点i+2 i+2 = yi+1 + m (yir= i+1 i+1 + m 1由此可得如下递推公式初值: x = x0 , y = y0 = = y1 y0r 第i+1步:当 0时, , 选择P2(xi+1,yir+1)点,=+m-1=+m-1 当 0时,选择P1(xi+1,yir)点,=+m=+m34Bresenham Line Algorithm(4)存在问题:的初值中有浮点数 m 由于判别时只关心的符号,两边同乘 2x,得 2x = 2y - x令 = 2x,可得如下递推公式:初值: x = x0 , y = y0 ,= = 2y - x第i+1步:当 0 时, , 选择P2(xi+1,yir+1)点,=+ =+ 2y - 2x当 0 时,选择P1(xi+1,yir)点,=+ =+ 2y35