*Computer GraphicsComputer Graphicsn1.整体介绍n2.建模（图形描述）n3.绘制(光栅化算法)n4.光照模型*Computer GraphicsComputer Graphics内容提要内容提要r直线光栅化算法 r圆光栅化算法 r多边形的填充*Computer GraphicsComputer Graphics9.1 9.1 直直线线线线光光栅栅栅栅化算法化算法n假设n整型坐标系，直线段斜率00时，M在L(Q点)上方，取P1为下一个象素；n当d=0时，选P1或P2均可，约定取P1为下一个象素；M*Computer GraphicsComputer Graphics9.1.2 9.1.2 中点画中点画线线线线法法MP1P2P(Xp+1,Yp+0.5)d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c*Computer GraphicsComputer Graphics9.1.2 9.1.2 中点画中点画线线线线法法n若d0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp)n下一个象素的判别式为：d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d + a 增量为an若d0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1)n再下一个象素的判别式为：d2=F(Xp+1)+1,(Yp+1)+0.5)=a(Xp+2)+b(Yp+1.5)+c=d + a+b 增量为a+bMP1P2MP1P2*Computer GraphicsComputer Graphics9.1.2 9.1.2 中点画中点画线线线线法法nd的初始值 d0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b=a+0.5b d的增量都是整数 用2d代替d：d0=2a+b=a+a+bd1=2ad2=2(a+b)因(X0,Y0)在直线 上，所以 F(X0,Y0)=0*Computer GraphicsComputer Graphics9.1.2 9.1.2 中点画中点画线线线线法法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=2* (a+b)；x=x0；y=y0；drawpixel(x, y, color);while (x=0, 取P2为下一象素，再下一象素的判别式为n 初始象素是（0,R），判别式d的初值为:d0=F(1,R-0.5)=1.25-RP1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替d, e0=1-R*Computer GraphicsComputer Graphics9.2.2 9.2.2 中点画中点画圆圆圆圆法法n输入圆的半径R和圆心(xc,yc),先计算以原点为圆心，R为 半径的圆周上的点，令初始点为(x0,y0)=(0,R)n设置初始决策参数d0=1-Rn在每一个xn（从n=0开始）的位置，进行下列检测：如果 dn=y为止*Computer GraphicsComputer Graphics9.2.2 9.2.2 中点画中点画圆圆圆圆法法MidPointCircle(int r int color) int x,y;float d;x=0; y=r; d=1-r;circlepoints (x,y,color);while(x0时，D在圆外，n当i=0时，D在圆上，(xi,yi)HPi VD(xi+1,yi )(xi,yi-1)(xi+1,yi-1)*Computer GraphicsComputer Graphics9.2.3 Bresenham9.2.3 Bresenham画画圆圆圆圆法法n当i0，则选Dn若d=0，则选H 情形也 适用*Computer GraphicsComputer Graphics9.2.3 Bresenham9.2.3 Bresenham画画圆圆圆圆法法n当i0时，D在圆外，情形，选mv ，mD 中最小者nd=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2|=(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2=2 (i-xi)-1n若d0，则选Vn若d=0，则选D情形也 适用*Computer GraphicsComputer Graphics9.2.3 Bresenham9.2.3 Bresenham画画圆圆圆圆法法n当i=0时，D在圆上，n按d判别，有d0，应选Dn按d判别，有d0，选Dn当i0时,n若d 0，选D n若d0，选Vn当i=0时，选D*Computer GraphicsComputer Graphics9.2.3 Bresenham9.2.3 Bresenham画画圆圆圆圆法法n判别式的递推关系n当取H(xi+1,yi)时ni+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1n当取V(xi,yi-1)时ni+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1n当取D(xi+1,yi-1)时ni+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+2*Computer GraphicsComputer Graphics9.2.3 Bresenham9.2.3 Bresenham画画圆圆圆圆法法*Computer GraphicsComputer Graphics9.3 9.3 多多边边边边形填充算法形填充算法所谓填充算法就是如何用颜色或图案来填充一个任 意多边形。n 扫描线填充算法n 边填充算法n 种子填充算法 *Computer GraphicsComputer Graphics 求出一根扫描线与多边形各边的交点： 对求得的交点进行排序： 奇偶配对求出扫描线与多边形的相交区间 ： 对这些相交区间填色。扫描线的连贯性 图形的空间连贯性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.3.1 9.3.1 扫扫扫扫描描线线线线填充算法填充算法*Computer GraphicsComputer Graphics 求出一根扫描线与多边形各边的交点： 对求得的交点进行排序： 奇偶配对求出扫描线与多边形的相交区间 ： 对这些相交区间填色。01 2 3 4 5 6 71234567yx88 9 10扫描线5P4P1P2P3P5扫描线2I1I2I3I4扫描线的连贯性 图形的空间连贯性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.3.1 9.3.1 扫扫扫扫描描线线线线填充算法填充算法*Computer GraphicsComputer Graphics9.3.1 9.3.1 扫扫扫扫描描线线线线填充算法填充算法- -填充填充扩扩扩扩大化大化n解决方法：n取中心扫描线y+0.5n检查交点右方像素的中心是否落在区间内xlx+0.5xr*Computer GraphicsComputer Graphics9.3.1 9.3.1 扫扫扫扫描描线线线线填充算法填充算法- -顶顶顶顶点交点点交点计计计计 数数检查顶点的两条边的另外两个端点的y值，按这 两个y值中大于顶点y值的个数是0、1、2来决定交点 是计0次、1次还是2次。543210 P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6计数0次计数1次计数2次*Computer GraphicsComputer Graphics9.3.1 9.3.1 有序有序边边边边表填充算法表填充算法n活性边表的建立n结点信息 x：当前扫描线与边的交点 x：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线号 x =1/kn活性边表的更新节点更新 新边插入 旧边删除*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法表填充算法n结点信息 x0：扫描线与边的初始交点 x：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线号n对每条扫描线建立一个新边表*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法表填充算法n结点信息 x0：扫描线与边的初始交点 x：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线号n对每条扫描线建立一个新边表*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法表填充算法新 边 表8.5 7.5 6.5 5.5 4.5 3.5 2.5 1.5 0.5 528.5 -1.5 711082072-32.533P4P5P5P6P3P4P6P1P1P2P2P3yx0 1 2 3 4 5 6 7 8 9 101112345678P6P4P1P5P2P32-32.533P1P2P2P3 y=1.5207.833P6P1P2P3 y=2.5207.1108P6P1P3P4 y=3.5528.P4P5 1108P3P4 5 -1.5 7P5P6 207.P6P1 y=5.5728.P4P5 1108P3P4 3.5 -1.5 7P5P6 207.P6P1 y=6.5*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法表填充算法活动边表的建立5-32.533P1P2P2P3 y=1.5207.833P6P1P2P3 y=2.5207.1108P6P1P3P4 y=3.5从新边表中取出与扫描线y=1.5相 交的初始边排序放入活性边表中 ，填充交点之间的区域更新边表，删除P1P2，插入新边 P6P1，填充交点之间的区域更新边表，删除P2P3，插入新边 P3P4，填充交点之间的区域*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法表填充算法528.P4P5 1108P3P4 5 -1.5 7P5P6 207.P6P1 y=5.5728.P4P5 1108P3P4 3.5 -1.5 7P5P6 207.P6P1 y=6.5928.P4P5 1108P3P4 y=7.5更新边表，插入新边P5P6和P4P5，填充两对交点之间的区域更新边表，填充两对交点之间的区域更新边表，删除P6P1和P5P6，填充交点之间的区域更新边表，删除P4P5和P3P4，活动边表为空，没有新边，填充算法结束*Computer GraphicsComputer Graphics9.3.19.3.1有序有序边边边边表填充算法步表填充算法步骤骤骤骤1、 建立NET表；2、将扫描线纵坐标y的初值置为NET中非空元素的最小序号 3、置AET为空； 4、执行下列步骤直至NET和AEL都为空 4.1、如NET中的第y类非空，则将其中的所有边取出并插入AEL中； 4.2、如果有新边插入AEL，则对AEL中各边排序； 4.3、对AEL中的边两两配对，获得有效填充区段，再填充 4.4、将当前扫描线纵坐标y值递增1； 4.5、将AEL中满足yymax边删去 4.6、对AEL中剩下的每一条边的