《《计算机图形学教学资料》》由会员分享，可在线阅读，更多相关《《计算机图形学教学资料》（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
