《计算机图形学基础第2章光栅图形学》由会员分享，可在线阅读，更多相关《计算机图形学基础第2章光栅图形学（212页珍藏版）》请在金锄头文库上搜索。
1、第2章 光栅图形学,第2章 光栅图形学,图形的扫描转换（光栅化）：确定一个最佳逼近图形的像素集合，并用指定属性写像素的过程。步骤如下： （1）确定有关像素 （2）用图形的颜色或其它属性，对像素进行写操作。 对一维图形，若不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。 裁剪通常在扫描转换之前进行,第2章 光栅图形学,反走样（antialiasing）,走样（aliasing）,非水平、垂直、 45的直线等,畸变（台阶、锯齿）,产生,
2、减少或消除,提高显示器空间分辨率,像素的多亮度显示,显示器空间分辨率有限,第2章 光栅图形学,消隐 当不透光的物体阻挡了某些来自物体部分的光线，使其无法到达观察者时，这些物体部分是隐藏部分。 隐藏部分是不可见的，如果不删除隐藏的线或面，就可能发生对图形的错误理解。 为了使计算机图形能够真实地反映这一现象，必须把隐藏的部分从图形中删除，称为消除隐藏线和隐藏面，简称消隐。,本章主要内容,直线 圆弧 多边形 字符 裁剪 反走样 消隐,基本图形的扫描转换算法,基本方法的实现,2.1 直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 直线段
3、扫描转换算法： 数值微分法DDA算法 中点画线法 Bresenham画线算法,2.1 直线段的扫描转换算法 直接计算法,假定直线的起点、终点分别为:P0(x0,y0), P1(x1,y1)，且都为整数。 计算出斜率k=(y1-y0)/(x1-x0) , 在Y轴的截距b=y0-k*x0,(X i+1, kX i+1+b),(X i , Yi),栅格交点表示象素点位置,。,。,。,。,2.1 直线段的扫描转换算法 直接计算法,这样一来，只要给定 x的值，根据解析式立即可以计算出对应的y值，然后输出(x,round(y). 特点：这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次浮点加法和一
4、次舍入运算。,(X i+1, kX i+1+b),(X i , Yi),(X i , Yi),。,。,。,。,2.1 直线段的扫描转换算法 数值微分法,假定直线的起点、终点分别为: (x0, y0), (x1, y1)，且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),。,。,。,。,2.1 直线段的扫描转换算法 数值微分法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L: y=kx+b 直线斜率为 考虑当x从xixi+1时y的变化规律：设x=xi+1-xi , xi+1= xi+ x 计算yi+1= kx
5、i+1+b= k(xi+ x)+b= kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k，即:当x每递增1, y递增k(即直线斜率),2.1 直线段的扫描转换算法 数值微分法,注意上述分析的算法仅适用于k 1的情形。在这种情况下, x每增加1, y最多增加1。 当 k 1时, 必须把x, y地位互换 增量算法: 在一个迭代算法中, 如果每一步的x, y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,当斜率大于1时。让Y增长值为1，X的增量为1/K。 这样做的目的是让每次变化的值不能大于1。这样可以让像素点更加整齐。,2.1 直线段的扫描转
6、换算法 数值微分法,void DDALine(int x0,int y0,int x1,int y1,int color) int x； float dx, dy, y, k; dx = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; ,2.1 直线段的扫描转换算法 数值微分法,例：画直线段P0(0,0)-P1(5,2), k=0.4 x y int(y+0.5) 0 0 0 1 0.4 0 2 0.8 1 3 1.2 1 4 1.6 2 5 2.0 2,缺
7、点：在此算法中，y, k必须是float, 且每一步都必须对y进行舍入取整，不利于硬件实现。,2.1 直线段的扫描转换算法 中点画线法,原理 假定直线斜率0k1，且已确定点亮象素点P(xp, yp), 则下一个与直线最接近的像素只能是 P1(xp+1, yp)点 或 P2(xp+1, yp+1)点。 设M(xp+1, yp+0.5)为中点，Q为理想直线与x=xp+1的交点。 需确定下一个点亮的象素。,2.1 直线段的扫描转换算法 中点画线法,需确定下一个点亮的象素 (Q为实际点) M在Q的下方P2离直线更近更近取P2 M在Q的上方P1离直线更近更近取P1 M与Q重合， P1, P2任取一点。
8、问题：如何判断M与Q点的关系？ 由常识知: 若y=kx+b, 设 F(x,y) = y kx - b, 则有,2.1 直线段的扫描转换算法 中点画线法,假设直线方程为: F(x, y)=ax+by+c=0 ( y=(-a/b)x-c/b ) 通过两点不能唯一确定a, b, c, 取 a=y0-y1, b=x1-x0, c=x0y1-x1y0 F(x,y)=ax+by+c=b(y-(-a/b)x-c/b); 则有 欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,2.1 直线段的扫描转换算法 中点画线法,构造判别式 d=F(M)=F(xp+1,yp+0.5) =a
9、(xp+1)+b(yp+0.5)+c 当d0, M在直线(Q点)上方, 取右下方P1 当d=0, 选P1或P2均可，约定取P1 能否采用增量算法呢？,2.1 直线段的扫描转换算法 中点画线法,若d0M在直线上方取P1; d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a=d+a； 增量为a 若d0M在直线下方取P2; d2= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为ab,2.1 直线段的扫描转换算法
10、 中点画线法,画线从(x0, y0)开始，d的初值 d0=F(x0+ 1, y0 + 0.5)= a(x0 + 1) + b(y0 + 0.5) + c =F(x0, y0) + a + 0.5b = a + 0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。,2.1 直线段的扫描转换算法 中点画线法,void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=
11、2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,2.1 直线段的扫描转换算法 中点画线法,例：用中点画线法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 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3
12、 1 -1 5 4 2 5,2.1 直线段的扫描转换算法 斜率不在0,1的直线的处理,设起点和终点分别为(x0,y0)和(x1,y1) 若k1, 则(y0,x0)和(y1,x1)所确定的直线斜率k0,1， 适用于前面讨论的情形。 此时, 对(y0,x0)和(y1,x1)所确定的 直线进行扫描转换， 每确定一组(x,y)，输出(y,x)。,2.1 直线段的扫描转换算法 斜率不在0,1的直线的处理,若-1k0 先对(x0,-y0)和(x1,-y1)所确定的直线进行扫描转换， 每确定一组(x,y)，输出(x,-y)。,(x0,y0),(x1,-y1),(x1,y1),(x0,-y0),2.1 直线段
13、的扫描转换算法 斜率不在0,1的直线的处理,若k -1 对(-y0, x0)和(-y1, x1)所确定的直线进行扫描转换， 每确定一组(x, y), 输出(-y, x)。,(x0,y0),(x1,-y1),(x1,y1),(x,-y0),(-y0,x0),(-y1,x1),2.1 直线段的扫描转换算法 Bresenham算法,Jack E. Bresenham（布雷森汉姆）于1962年在IBM发明此算法。 据他本人表示，他于1963年在丹佛举行的美国计算机协会全国大会上发表了该算法，论文则登载于1965年的IBM系统期刊 (IBM Systems Journal) 之中。 Bresenham直
14、线算法其后被修改为能够画圆，修改后的算法有时被称为“Bresenham画圆算法”或中点画圆算法。,2.1 直线段的扫描转换算法 Bresenham算法,基本原理： 假定直线段的斜率k: 0k1,Bresenham算法原理,2.1 直线段的扫描转换算法 Bresenham算法,误差项d的计算 d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1,2.1 直线段的扫描转换算法 Bresenham算法,算法步骤： 1. 输入直线的两端点P0(x0, y0)和P1(x1, y1)。 2. 计算初始值x, y, d=0, x=x0, y=y0。 3. 绘制点(x, y)。 4. d更新为d
15、+k, 判断d的值。若d0.5, 则(x, y)更新为(x+1, y+1), 同时将d更新为d-1；否则(x, y)更新为(x+1, y)。 5. 当直线没有画完时，重复步骤3和4。否则结束。,2.1 直线段的扫描转换算法 Bresenham算法,改进1：令e=d-0.5 e初=-0.5， 每走一步有e=e+k。 if (e0) then e=e-1,2.1 直线段的扫描转换算法 Bresenham算法,算法步骤为 1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2. 计算初始值x、y、e=-0.5、x=x0、y=y0。 3. 绘制点(x,y)。 4. e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。 5. 当直线没有画完时，重复步骤3和4。否则结束。,2.1 直线段的扫描转换算法 Bresenham算法,BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy; float k,e; dx = x1-x0; dy = y1-y0; e = -0.5; x=x0; y=y0; for( i=0; i= 0) y+; e=e-1;
