《计算机图形学第三章》由会员分享，可在线阅读，更多相关《计算机图形学第三章（112页珍藏版）》请在金锄头文库上搜索。
1、第三章 光栅图形学,什么是光栅图形学？光栅显示器 图形光栅化、光栅化图形的处理 光栅显示器上显示的图形,称之为光栅图形。光栅显 示器可以看作是一个象素矩阵,在光栅显示器上显示 的任何一个图形,实际上.如何使光栅图形最完美地 逼近实际图形,便是光栅图形学要研究的内容。,光栅图形学的研究内容 直线段的扫描转换算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充 字符 裁剪 反走样 消隐,3.1 二维线画图元的生成 3.2 二维填充图元的生成 3.3 反混淆算法,所谓 图元的生成，是指完成图元的参数表示形式 （由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也
2、称扫描转换图元。,3.1 二维线画图元的生成,1. 扫描转换直线段DDA算法中点画线法Bresenham画线算法2. 圆弧、椭圆弧扫描转换中点算法内接多边形迫近法等面积多边形逼近法3. 生成圆弧的正负法4. 线画图元的属性控制,图形显示的几种方式,图形显示前需要：扫描转换+裁剪 裁剪-扫描转换：最常用，节约计算时间。 扫描转换-裁剪：算法简单； 扫描转换到画布-位块拷贝：算法简单，但耗时耗内存。常用于字符显示。设备级显示算法，考虑运算方式、时间、次数等细节。,扫描转换直线段,直线的绘制要求： 1.直线要直； 2.直线上的点要准确，即无不定向性和断裂情况； 3.直线的亮度、色泽要均匀； 4.画线
3、的速度要快； 5.要求不同直线可具有不同的色泽、亮度、线型等。,扫描转换直线段,直线基础我们知道：直线的笛卡儿斜率截距方程为：y=mx+bm-直线的斜率 b -直线于y轴的截距给定线段的两个端点（x0,y0), (x1,y1)，可以计算斜率m 和截距b： m=(y1-y0)/(x1-x0) b=y1mx1= (x0y1-x1y0)/ (x1-x0),在x方向上，给定任意增量x，那么对应的y 的增量为y, 即y = mx图形学直线的算法是以上面的直线方程、斜 率方程、截距方程和增量方程为基础,扫描转换直线段,扫描转换直线段 求与直线段充分接近的像素集两点假设 直线段的宽度为1 直线段的斜率:,像
4、素间均匀网格 整型坐标系,数值微分法（DDA-digital differential analyzer）,DDA算法是一种线段扫描转换算法，它是在 一个坐标轴上以单位间隔对线条取样，从而 确定另一个轴上最靠近线段路径的对应整数 值。 首先考虑斜率值m在（0，1）之间的直线。,扫描转换直线段,DDA（ digital differential analyzer）算法 条件： 待扫描转换的直线段： 斜率：直线方程： 直接求交算法： 划分区间x0,xn:计算纵坐标： 取整：,批注：y=mx+b m=0.4 int取整,例：画直线段 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+
5、0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 注：网格点表示象素,扫描转换直线段,复杂度：乘法+加法+取整 DDA算法（增量算法）复杂度：加法+取整,增量算法：在一个迭代算法中，如果每一步 的x、y值是用前一步的值加上一个增量来获 得，则称为增量算法。 DDA算法就是一个增量算法。 问题：当 k 1时，会如何？,扫描转换直线段,中点画线算法 目标：消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现； DDA算法，效率低） 条件： 同DDA算法 斜 率： 直线段的隐式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+b
6、y+c=0式中 a=y0-y1,b=x1-x0,c=X0Y1-X1Y0,扫描转换直线段,直线的正负划分性,直线上方的点：F(X，Y)0 直线下方的点：F(X，Y)0,扫描转换直线段,问题：判断距直线最近的下一个象素点构造判别式：d=F(M)=F(Xp+1,Yp+0.5)由d0，d0可判定下一个象素，,P,P2,P1,要判定再下一个象素，分两种情形考虑：1）若d0，取正右方象素P1，再下一个象素判定，由：d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a，d的增量是a2）若d0，取右上方象素P2，再下一个象素，由：d2=F(Xp+2,Yp+1.5)=d+a+b
7、d的增量为a+b,P2,P,P1,扫描转换直线段,d的初始值 d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5 因(X0,Y0)在直线上，F(X0，Y0)=0,所以，d0=a+0.5bd的增量都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。 算法中只有整数变量，不含乘除法，可用硬件实现。,扫描转换直线段,程序Midpointline(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int a,b,d1,d2,2,x,y;a = y0-y1; b = x1 x0; d = 2 * a +b;d1 = 2*a; d2 = 2*(a
8、+b);x = x0; y = y0;PutPixel(x,y,color);while (xx1) if (d0) x+; y+; d +=d2;else x+; d +=d1;PutPixel(x,y,color);,例：用中点画线法P0(0,0) P1(5,2),例：用中点画线法P0(0,0) P1(5,2)a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 d3= 2a=-4 d4= 2(a+b)=6d0=2(a+0.5b) 若d0, 增量为2a 若d0，增量为2(ab)Xi yi d 0 0 1 1 0 -3 (1 -4) 2 1
9、3 (-3 +6) 3 1 -1 (3 -4) 4 2 5 (-1 +6）,Bresenham画线算法（构思巧妙，使得每次只需检 测误差项的符号就能决定直线上的下一个像素的位 置）Bresenham算法是Bresenham提出的一种精确且有效的 光栅生成算法。 它用于显示线、圆和其它曲线的整数运算 它是目前最有效的线段生成算法,扫描转换直线段,过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。,设直线方程为： ，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。 X下标每增
10、加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。 当d0.5时，最接近于当前象素的右上方象素（ ） 而当d0.5时，更接近于右方象素（ ）。 为方便计算，令ed-0.5， e的初值为-0.5，增量为k。 当e0时，取当前象素（xi，yi）的右上方象素（ ）； 而当e0时，更接近于右方象素（ ）。,可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.4x y e0 0 -0.51 0 -0.12 1 0.33 1 -0.34 2 0.1 5 2 -0.5 大
11、于零，y加一，小于零，不变,void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0;for (i=0; idx; i+) drawpixel (x, y, color);x=x+1，e=e+k;if (e0) y+, e=e-1;,最终，Bresenham算法也是每个象素，需一个整数算法，其优点是可以用于其他二次曲线。,扫描转换圆弧,处理对象：圆心在原点的圆弧 假设圆的方
12、程为：X2+ Y2= R2 圆的八对称性,两种直接离散方法：离散点:离散角度:开根，三角函数运算，计算量大，不可取。,方法1X2+ Y2= R2 Y = Sqrt(R2-X2) 在一定范围内，每给定一 X值，可得一Y值。当X取整数时，Y须取整。 缺点：浮点运算，开方， 取整，不均匀。,方法2:采用极坐标x = Rcos y = Rsin dx=-Rsind dy=Rcosd xn+1 =xn+dx yn+1 =yn+dy xn+1 = xn+dx= xn-Rsin d=xn-ynd yn+1 = yn+dy= yn+Rcosd=yn+ xnd显然，确定x,y的初值及d值后，即可以增量方式获得圆
13、周 上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘 法运算、取整运算。,方法3：利用圆的对称性采用中点法（常 用方法）只须讨论1/8圆，一般采用第二个8 分圆,扫描转换圆弧,圆弧的正负划分性,圆弧外的点：F(X，Y)0 圆弧内的点：F(X，Y)0,扫描转换圆弧,生成圆弧的中点算法 考虑对象：第二个八分圆，第一象限的八分之一圆弧,P,P1,P2,扫描转换圆弧,问题：与直线情形类似 圆弧的隐函数：F(X,Y)=X2+Y2-R2=0中点 M=(Xp+1,Yp-0.5), 当F(M)0时，M在圆内，说明P1距离圆弧更 近，取P1； 当F(M)=0时，M在圆上； 当F(M)0时，M在圆外，说明P2
14、距离圆弧更近，取P2。,P2,P1,P,构造判别式d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R21）若d0，取P1，再下一个象素的判别式为： d1=F(Xp+2,Yp-0.5)=d+2Xp+3，沿正右方向，d的增量为2Xp+3；2）若d0，取P2，再下一个象素的判别式为：d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2)沿右下方向，d的增量为2(Xp-Yp)+5 d的初始值(在第一个象素(0,R)处),d0=F(1, R-0.5)=1.25-R 算法中有浮点数，用e=d-0.25代替,扫描转换圆弧,所以：初始化运算d0 = 1.25
15、R 对应于 e 0= 1- R判别式 d 0 对应于 e -0.25 又因为：e的初值e0为整数，运算过程中的分量也为整数，故e始终为整数 所以： e -0.25 等价于 e 0,算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称 点。 4.判断d的符号。若d0，则先将d更新为 d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更 新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。,程序如下（完全用整数实现）：,MidpointCircle(r,color) Int r, color; int x,y,d;x = 0; y = r; d = 1-r;putpixcel(x,y,color);,while( x y) if (d 0) d += 2*x+3; x+; else d += 2*(x-y)+5;x+ ; y-; putpixcel(x,y,color); ,为了进一步提高算法的效率，可以将上面的 算法中的浮点数改写成整数，将乘法运算改 成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替d，(d = 1.25 R) e0=1-R,
