第四章基本图形生成算法.ppt

1、计算机图形学,第四章 直线、圆、椭圆生成算法,图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下： 1、确定有关像素 2、用图形的颜色或其它属性，对像素进行写操作。 对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。 任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。,计算机图形学,图形显示前需要：扫描转换+裁剪 裁剪-扫描转换：最常用，节约计算时间。 扫描转换-裁剪：算法简单；,计算机图形学,本章内容,扫描转换直线段 DDA算法 中点画线法 Br

2、esenham画线算法 圆弧、椭圆弧扫描转换 中点算法,计算机图形学,直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 三个常用算法： 数值微分法（DDA） 中点画线法 Bresenham算法。,计算机图形学,数值微分法（）,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),栅格交点表示象素点位置,。,。,。,。,计算机图形学,数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1

3、)的直线段L y=kx+b 直线斜率为 这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,计算机图形学,数值微分(DDA)法,计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1;yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)； 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。 当 k 1时，必须把x，y地位互换,计算机图形学,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,计算机图形学,数值微

4、分(DDA)法,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; ,计算机图形学,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2) x int(y+0.5) y+0.5 000+0.5 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0+

5、0.5,计算机图形学,数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,计算机图形学,中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点 现需确定下一个点亮的象素。,计算机图形学,中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。 M在Q的上方- P1离直线更近更近-取P1 M与Q重合， P1、P2任取一点。 问题：如何判断M与Q点的关系？,计算机图形学,中点画线法,假设直线方程为：ax+by+c=0 其中a=y0-y1,

6、 b=x1-x0, c=x0y1-x1y0 由常识知： 欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,计算机图形学,中点画线法,构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？,计算机图形学,中点画线法,若d0-M在直线上方-取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；

7、增量为a,计算机图形学,中点画线法,若dM在直线下方-取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,计算机图形学,中点画线法,画线从(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来摆脱小数，提高效率。,计算机图形学,中点画线法,void Midpo

8、int 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 (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,计算机图形学,中点画线法,例：用中点画线法P0(0,0) P1

9、(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 ixiyid 1001 210-3 3213 431-1 5425,计算机图形学,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情况来说明Bresenham算法。由DDA算法可知： yi+1=yi+k (1) 由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。,计算机图形学,Bresenham画线算法,D=d+k k=y/x

10、令d的值始终在0,1之间，当d=1就把它减掉， 当d0.5的时候就选择(x+1,y+1)否则取下个像素点为(x+1,y),计算机图形学,程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy; float k,e; int e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; e = -dx; for( i=0; i=0) y+; e=e-1; /; e = e - 2*dx; ,Bresenham画线算法,计算机图形学,圆的扫描转换

11、算法,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： X2 + Y2 = R2,计算机图形学,圆弧扫描算法,X2 + Y2 = R2 Y = Sqrt(R2 - X2) 在一定范围内，每给定一 X值，可得一Y值。 当X取整数时，Y须取整。 缺点：浮点运算，开方， 取整，不均匀。,计算机图形学,角度DDA法,x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 = x n + dx = x n - Rsind =x n - (y n - y 0

12、)d y n+1 = y n + dy = y n + Rcosd =y n + (x n - x 0 )d 显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,计算机图形学,中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆 P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。,M,P1,P2,P（Xp ，Yp ）,计算机图形学,中点画圆法,构造函数：F（X，Y）=X2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y

13、）在圆外。 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,计算机图形学,中点画圆法,有如下结论： F（M）M在圆内- 取P1 F（M）= 0 -M在圆外- 取P2 为此，可采用如下判别式：,M,P1,P2,计算机图形学,中点画圆法,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2 = d + 2xp +3 即d 的增量为

14、 2xp +3.,M,P1,P2,计算机图形学,中点画圆法,若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - R,M,P1,P2,计算机图形学,中点画圆法,MidpointCircle(int r, int color) int x,y; float d; x=0

15、; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; ,计算机图形学,中点画圆法,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-R,计算机图形学,中点画圆法,上述算法能否再改进呢？ 注意到d的增量是x,y的线性函数， 每当x递增1，则d的增量递增x=2 每当y递减1，则d的增量递增y=2 x初始值=3；y初始值=-2r+2 见173页算法。,计

16、算机图形学,Bresenham画圆算法,如果已经知道圆弧上的一点(x,y)，下一像素的选取有三种可能：正右方像素，右下角像素和正下方像素，分别用H,D和V表示，如下图所示。这三个像素的偏差的平方为：,计算机图形学,Bresenham画圆算法,计算机图形学,Bresenham画圆算法,计算机图形学,生成圆弧的正负法,原理：,设圆的方程为F(x,y)=X2 + Y2 - R2=0; 假设求得Pi的坐标为(xi,yi)； 则当Pi在圆内时- F(xi,yi) 向右- 向圆外 Pi在圆外时- F(xi,yi)0 - 向下- 向圆内,计算机图形学,生成圆弧的正负法,即求得Pi点后选择下一个象素点Pi+1

17、的规则为： 当F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi; 当F(xi,yi) 0 取xi+1 = xi， yi+1 = yi - 1; 这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，故称正负法。 快速计算的关键是F(xi,yi) 的计算，能否采用增量算法？,计算机图形学,生成圆弧的正负法,若F(xi,yi) 已知，计算F(xi+1,yi+1) 可分两种情况： 1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = (xi+1)2+ yi2 -R2

18、= F(xi,yi) +2xi +1 2、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1 3、初始值：略,计算机图形学,生成圆弧的多边形逼近法,圆的内接正多边形迫近法 圆的等面积正多边形迫近法,计算机图形学,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即 因此，在允许的误差范围内，可以用正多边形代替圆。 设内接正n边形的顶点为Pi(xi,yi), Pi的幅角为i ,每一条边对

19、应的圆心角为a，则有 xi =Rcos i yi =Rsin i,计算机图形学,圆的内接正多边形逼近法,内接正n边形代替圆 计算多边形各顶点的递推公式 Xi+1 Rcos( a+ i) = Yi +1 Rsin (a+ i) Xi+1 cos a- sin a Xi = Yi +1 sin a cosa Yi 因为: a是常数， sin a， cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,计算机图形学,圆的等面积正多边形逼近法,当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似

20、代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。,计算机图形学,圆的等面积正多边形逼近法,步骤： 求多边形径长，从而求所有顶点坐标值 由逼近误差值，确定边所对应的圆心角,计算机图形学,椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b2=0 椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。 椭圆上一点处的法向： N(x,y) = (F) x i + (F) y j = 2b2 x i + 2a2 y j,计算机图形学,在上半部分,法向量的y分量大 在下半部分,法向量的x分量大,上半部分,下半部分,法向量 两

21、分量相等,M1,M2,在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分量比x分 量大, 即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中点，不等式改变方 向，则说明椭圆弧从上部分转入下部分,计算机图形学,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点 先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2,计算机图形学,根据d1的符号来决定下一像

22、素是取正右方的那个，还是右上方的那个。 若d10，中点在椭圆内，取正右方象素，判别式更新为： d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为b2(2Xp+3) 当d10，中点在椭圆外，取右下方象素，更新判别式： d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量为b2(2Xp+3)+a2(-2Yp+2),计算机图形学,d1的初始条件：椭圆弧起点为(0，b)； 第一个中点为(1,b-0.5) 初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25) 转入下一部分，下一象素可能是正下方或右下方，此时判别式要初

23、始化。 d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2 = F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3) 下半部分弧的终止条件为 y = 0,计算机图形学,区域填充算法,区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的,计算机图形学,区域填充,表示方法：内点表示、边界表示 内点表示 枚举处区域内部的所有像素 内部的所有像素着同一个颜色 边界像素着与内部像素不同的 颜色 边界表示 枚举出

24、边界上所有的像素 边界上的所有像素着同一颜色 内部像素着与边界像素不同的颜色,计算机图形学,边界填充算法,2.3 多边形的扫描转换与区域填充,多边形有两种重要的表示方法：顶点表示和点阵表示。 多边形的扫描转换:把多边形的顶点表示转换为点阵表示。 区域可采用内点表示和边界表示两种表示形式。 区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。,多边形类型,多边形分为凸多边形、凹多边形、含内环的多边形。,2.3.1多边形的扫描转换,扫描线算法 基本思想： 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 对于一条扫描线填充过程可

25、以分为四个步骤： （1）求交（2）排序 （3）配对（4）填色,一个多边形与若干扫描线,数据结构,活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中 结点内容 x：当前扫描线与边的交点坐标 x：从当前扫描线到下一条扫描线间x的增量 ymax：该边所交的最高扫描线号ymax,新边表（NET）,存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中 上图所示各条扫描线的新边表NET,假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。 设该边的直线方

26、程为：ax+by+c=0； 若yyi，x=x i；则当y = y i+1时， 其中 为常数,交点问题,扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。,算法过程,void polyfill (polygon, color) int color; 多边形 polygon; for (各条扫描线i ) 初始化新边表头指针NET i； 把y min = i 的边放进边表NET i; y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i ) ,把新边表NET i 中的边结点用插入

27、排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值； 遍历AET表，把y max= i 的结点从AET表中删除，并把y max i 结点的x值递增x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； /* polyfill */,计算机图形学,边界标志算法,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,计算机图形学

28、,区域填充,区域填充要求区域是连通的 连通性 4连通、8连通 4连通： 8连通,计算机图形学,区域填充,4连通与8连通区域的区别 连通性： 4连通可看作8连通区域，但对边界有要求 对边界的要求,计算机图形学,计算机图形学,A：适合于内点表示区域的填充算法 设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。 步骤如下： 种子象素入栈，当栈非空时，执行如下三步操作： （1）栈顶象素出栈； （2）将出栈象素置成多边形色； （3）按上、下、左、右的顺

29、序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,种子填充算法,计算机图形学,种子填充算法,例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) 设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示,计算机图形学,种子填充算法,递归算法可实现如下,void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) PutPixel(x,y,newCol

30、or); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); /*end of FloodFill4()*/,计算机图形学,种子填充算法,边界表示的4连通区域,void BoundaryFill4(int x,int y,int boundaryColor,int newColor) int color; color = GetPixel(x,y); i

31、f(color != boundaryColor) /*end of BoundaryFill4()*/,计算机图形学,该算法也可以填充有孔区域。 缺点： (1) 有些象素会入栈多次，降低算法效率；栈结构占空间。 (2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。 改进算法，减少递归次数，提高效率。 解决方法是用扫描线填充算法,种子填充算法,计算机图形学,二维裁剪,直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割算法 参数化裁剪算法 Liang-Barskey算法 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法,计算机图形学,裁剪,裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 图形裁剪算法，直接影响图形系统的效率。,计算机图形学,点的裁剪,图形裁剪中最基本的问题。 假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,y