图形学-光栅化算法

1、1.整体介绍2.建模（图形描述）3.绘制(光栅化算法)4.光照模型内容提要直线光栅化算法 圆光栅化算法 多边形的填充9.1 直线光栅化算法假设整型坐标系，直线段斜率0m1对m1，x、y互换基本原理确定最佳逼近于该直线的一组象素按扫描线顺序，对这些象素进行写操作9.1 直线光栅化算法已知线段端点：P0(x0,y0), P1(x1,y1)直线方程 y=k(x-x0)+y0浮点数取整 : yi=round(yi)=(int)(yi+0.5)用到浮点数的乘法、加法和取整运算9.1.1 DDA算法 数值微分分析（Digital Differential Analyzer，DDA）是一种增量算法。其实质是

2、用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。9.1.1 DDA算法已知一条直线段L（P1, P2）,其端点坐标分别为：P1 (x1, y1), P2(x2, y2)。直线段所在的直线的斜率为：直线方程为则9.1.1 DDA算法因光栅单位为1， 可以采用每次x方向增加1， y方向增加k的办法得到下一个直线点。9.1.1 DDA算法void Line ( /设0k1,xsxe int xs,ys;/左端点 int xe,ye; /右端点 int value) /赋给线上的像素属性值 int x; /x以步长为单位从xs增长到xe double dx =xe-xs;

3、 double dy =ye-ys; double k =dy/dx; / 直线之斜率k double y =ys; for (x=xs; x=xe; x+) WritePixel(x,Round(y),value); /像素属性值value y+=k; / y移动步长是斜率k /9.1.1 DDA算法例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。x round(y) y(yi+k)0 0 01 0 0.42 1 0.83 1 1.24 2 1.65 2 2.09.1.2 中点画线法基本原理 假定直线斜率k在0-1之间，当前象素点为（xp,yp），则下一个象素点有两种

4、可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。M9.1.2 中点画线法问题：判断距离理想直线最近的下一个象素点已知：线段两端点(x0,y0)，(x1,y1)直线方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判断M点在Q点上方还是在Q点下方？9.1.2 中点画线法构造判别式： d=F(M)=F(Xp+1,Yp+0.5)由d0，d0可判定下一个象素当d0时，M在L

5、(Q点)上方，取P1为下一个象素；当d=0时，选P1或P2均可，约定取P1为下一个象素；M9.1.2 中点画线法MP1P2P(Xp+1,Yp+0.5)d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c9.1.2 中点画线法若d0，中点M在直线上方，取正右方象素P1 (Xp+1,Yp)下一个象素的判别式为： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d + a 增量为a若d0，中点M在直线下方，取右上方象素P2 (Xp+1,Yp+1)再下一个象素的判别式为： d2=F(Xp+1)+1,(Yp+1)+0.5) =a(Xp

6、+2)+b(Yp+1.5)+c =d + a+b 增量为a+bMP1P2MP1P29.1.2 中点画线法d的初始值d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5b =a+0.5bd的增量都是整数用2d代替d：d0=2a+b=a+a+b d1=2a d2=2(a+b)因(X0,Y0)在直线上，所以F(X0,Y0)=09.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；d

7、2=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 */9.1.2 中点画线法举例：用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 x y d 0 0 1 1 0 -32 1 3 3 1 -1 2 5 2 19.

8、1.3 Bresenham算法使用最广泛与中点画线法的思想类似由误差项符号决定下一个象素取正右方像素还是右上方像素9.1.3 Bresenham算法基本思想比较从理想直线到位于直线上方的像素的距离d2和相邻的位于直线下方的像素的距离d1根据距离误差项的符号确定与理想直线最近的象素9.1.3 Bresenham算法x方向递增一个单位y方向走步与否取决于d1-d2的值取决于误差e值的大小误差判断当e0.5时，最接近P2(xi+1,yi+1), y方向走一步当e0.5时，最接近 P1(xi+1,yi),y方向不走步初值：e0= y/ xeP1P2PeeP1P2Pe9.1.3 Bresenham算法为

9、方便与0比较，设e=e-0.5当e0时，最接近P2(xi+1,yi+1), y方向走一步当e0时，最接近P1(xi+1,yi), y 方向不走步e0=y/ x-0.5eP1P2PeeP1P2Pe9.1.3 Bresenham算法设e=e2x，不影响判断的准确性当e0时，最接近P2(xi+1,yi+1), y方向走一步当e0时，最接近P1(xi+1,yi), y 方向不走步e0=2y - xeP1P2PeeP1P2Pe9.1.3 Bresenham算法下一步误差的计算当e0时，y方向走一步 e=2y/ x - 1 e=e + 2y - 2x当e0时，y方向不走步 e=2y/ x e=e + 2y

10、eP1P2PeeP1P2Pe9.1.3 Bresenham算法9.1.3 Bresenham算法例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。 xye00-1031-3112-52-19.1.3 Bresenham算法优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现9.1.3 Bresenham算法 已知直线段起点(0, 0)，终点(8,6)，利用Bresenham算法和中点画线算法生成此直线段，写出生成过程中坐标点及误差e的变化情况,并在下面的方格中，标出直线上各点 9.2 圆的光栅化算法圆的八对称性 圆心位于原点的圆有四条对称轴x=0,y=

11、0,x=y和x=-y。若已知圆弧上一点(x,y),可以得到其关于四条对称轴的其它7个点，这种性质称为圆的八对称性。 yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR9.2.1 简单画圆法假设圆心在原点 x2+y2=R2 圆的八对称性只考虑第二个八分圆For(x=0;x=R/ )yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR9.2.1 简单画圆法void CirclePoints(int x,int y,int color) drawpixel(x,y,color); drawpix

12、el(y,x,color); drawpixel(-x,y,color); drawpixel(y,-x,color); drawpixel(x,-y,color); drawpixel(-y,x,color); drawpixel(-x,-y,color); drawpixel(-y,-x,color); 9.2.1 简单画圆法两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点：计算量大所画像素位置间的间距不一致 9.2.2 中点画圆法F(X,Y)=X2+Y2-R2=0中点 M=(Xp+1,Yp-0.5)当d0时，M在圆内，P1距离圆弧近，取P1当d0时，M在圆外，P2距离圆弧近，取

13、P29.2.2 中点画圆法 若 d=0, 取P2为下一象素，再下一象素的判别式为 初始象素是（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-R9.2.2 中点画圆法输入圆的半径R和圆心(xc,yc),先计算以原点为圆心，R为半径的圆周上的点，令初始点为(x0,y0)=(0,R)设置初始决策参数d0=1-R在每一个xn（从n=0开始）的位置，进行下列检测：如果 dn=y为止9.2.2 中点画圆法MidPointCircle(int r int color) int x,y; float

14、 d; x=0; y=r; d=1-r; circlepoints (x,y,color); while(x=y) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color); R=5xyd05-415-1254343436MidPointCircle(int r int color) int x,y; float d; x=0; y=r; d=1-r; circlepoints (x,y,color); while(xy) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; ci

15、rclepoints (x,y,color); 9.2.3 Bresenham画圆法顺时针画第一四分圆，下一步选择哪个点？基本思想：通过比较像素与圆的距离平方来避免开方运算下一像素有3种可能的选择mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2 +(yi-1)2-R2 |选择像素的原则使其与实际圆弧的距离平方 达到最小(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham画圆法圆弧与点(xi,yi)附近光栅网格的相交关系有5种右下角像素D (xi+1,yi-1)与实际圆弧的近似程度i=(

16、xi+1)2+(yi-1)2-R2当i0时，D在圆外，当i=0时，D在圆上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham画圆法当i0时，D在圆内， 情形，选mH ，mD 中最小者d=mH - mD =|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2| =(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2 =2 (i+yi)-1若d0，则选D若d=0，则选H情形也适用9.2.3 Bresenham画圆法当i0时，D在圆外， 情形，选mv ，mD 中最小者d=mD - mV =|(x

17、i+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)-1若d0，则选V若d=0，则选D情形也适用9.2.3 Bresenham画圆法当i=0时，D在圆上，按d判别，有d0，应选D按d判别，有d0，应选D9.2.3 Bresenham画圆法当i0，选D当i0时,若d 0，选D 若d0，选V当i=0时，选D9.2.3 Bresenham画圆法判别式的递推关系当取H(xi+1,yi)时i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1当取V(xi,yi-1)时i

18、+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1当取D(xi+1,yi-1)时i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+29.2.3 Bresenham画圆法9.3 多边形填充算法 所谓填充算法就是如何用颜色或图案来填充一个任意多边形。 扫描线填充算法 边填充算法 种子填充算法 求出一根扫描线与多边形各边的交点： 对求得的交点进行排序： 奇偶配对求出扫描线与多边形的相交区间： 对这些相交区间填色。扫描线的连贯性图形的空间连贯性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.

19、3.1 扫描线填充算法 求出一根扫描线与多边形各边的交点： 对求得的交点进行排序： 奇偶配对求出扫描线与多边形的相交区间： 对这些相交区间填色。012345671234567yx88910扫描线5P4P1P2P3P5扫描线2I1I2I3I4扫描线的连贯性图形的空间连贯性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.3.1 扫描线填充算法9.3.1 扫描线填充算法-填充扩大化解决方法：取中心扫描线y+0.5检查交点右方像素的中心是否落在区间内 xlx+0.5xr9.3.1 扫描线填充算法-顶点交点计数 检查顶点的两条边的另外两个端点的y值，按这两

20、个y值中大于顶点y值的个数是0、1、2来决定交点是计0次、1次还是2次。543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6计数0次计数1次计数2次9.3.1 有序边表填充算法活性边表的建立结点信息x：当前扫描线与边的交点x：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线号x =1/k活性边表的更新节点更新新边插入旧边删除9.3.1有序边表填充算法结点信息x0：扫描线与边的初始交点x：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线号对每条扫描线建立一个新边表9.3.1有序边表填充算法结点信息x0：扫描线与边的初

21、始交点x：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线号对每条扫描线建立一个新边表9.3.1有序边表填充算法新边表8.57.56.55.54.53.52.51.50.5528.5-1.5711082072-32.533P4P5P5P6P3P4P6P1P1P2P2P3yx0123456789101112345678P6P4P1P5P2P32-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5

22、-1.57P5P6207.P6P1y=6.59.3.1有序边表填充算法活动边表的建立5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5从新边表中取出与扫描线y=1.5相交的初始边排序放入活性边表中，填充交点之间的区域更新边表，删除P1P2，插入新边P6P1，填充交点之间的区域更新边表，删除P2P3，插入新边P3P4，填充交点之间的区域9.3.1有序边表填充算法528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.57P5P6207.P6P1y=6.592

23、8.P4P51108P3P4y=7.5更新边表，插入新边P5P6和P4P5，填充两对交点之间的区域更新边表，填充两对交点之间的区域更新边表，删除P6P1和P5P6，填充交点之间的区域更新边表，删除P4P5和P3P4，活动边表为空，没有新边，填充算法结束9.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

24、、将当前扫描线纵坐标y值递增1；4.5、将AEL中满足yymax边删去4.6、对AEL中剩下的每一条边的x递增 x，即x = x+ x9.3.1有序边表填充算法优点：对每个像素只访问一次与设备无关缺点：数据结构复杂只适合软件实现9.3.2 边填充算法9.3.2 边填充算法优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印9.3.3 种子填充算法假设多边形区域内至少有一个像素已知区域定义法Interior-definedBoundary-d

25、efinedFlood-fill algorithmBoundary-fill algorithm区域连通方式：4-connected8-connected9.3.3 种子填充算法区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果9.3.3 种子填充算法简单的种子填充算法（4连通边界）种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈 填充算法演示6754S9328S2479384794847956847968479784798479

26、94794796754S9328S799缺点？9.3.3 种子填充算法4-connected boundary-fill void BoundaryFill4(int x,int y,int fill,int boundary) int current; current = getpixel(x, y); if (current != boundary) & (current != fill) putpixel(x, y, fill); BoundaryFill4(x+1, y, fill, boundary); BoundaryFill4(x-1, y, fill, boundary); BoundaryFill4