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