计算机图形学Chapter3-1

1、第3章 二维基本图形生成算法,显示器是由离散像素组成的矩阵，在绘制具有连续性质的直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。当光栅化按照扫描线的顺序进行时，它被称为扫描转换。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示之，即区域填充。光栅化和扫描转换是光栅图形学的基本问题，其算法的好坏对系统的效率有直接的关系。,VC提供了一个显示像素函数： SetPixel(x,y, color); 而在Turbo C中显示像素函数为： putpixel (x,y,color); 其中，x和

2、y为像素的位置坐标，color为像素的颜色。,安徽师范大学数学计算机科学学院 计算机图形学,本章的主要内容,基本二维图形的生成算法 直线段、圆（弧）、椭圆（弧）的光栅化算法。 区域填充 多边形扫描线填充算法、简单的种子填充算法、改进的种子填充算法、区域图案填充算法等。 线宽和线型 字符技术 点阵字符、矢量字符 反走样技术,安徽师范大学数学计算机科学学院 计算机图形学,直线（段）的光栅化,安徽师范大学数学计算机科学学院 计算机图形学,区域填充,安徽师范大学数学计算机科学学院 计算机图形学,具有一定宽度的直线,安徽师范大学数学计算机科学学院 计算机图形学,图案填充,安徽师范大学数学计算机科学学院

3、计算机图形学,点阵字符 点阵字库中的位图表示,安徽师范大学数学计算机科学学院 计算机图形学,线条属性,安徽师范大学数学计算机科学学院 计算机图形学,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 三个常用算法： 数值微分法（DDA） Bresenham算法 中点画线法,3.2 直线的生成算法,安徽师范大学数学计算机科学学院 计算机图形学,1 数值微分(DDA)法 Digital Differential Analyzer,基本思想 已知过端点 的直线段L： 直线斜率为 例如当k 1时从 的起点 开始，向 终点前进。步长=1或-1(个象素)，计算相应的

4、y坐标 ；取象素点(x, round(y)作为当前点的坐标。,安徽师范大学数学计算机科学学院 计算机图形学,作为最底层的光栅图形算法，在通常的CAD图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想。,这种方法非常直观、容易理解，但是效率较低。这是因为每步运算中都有一个浮点乘法与一个舍入运算。,考虑到 即y每次递增k(即直线斜率)；,分如下两种情况,（1）当从线段的左端点向右端点处理时，让x每次递增1,首先考虑k 1的情形。,例：画直线段 x floor(y+0.5) y 000 100.4 210.8 311.2 421.6 522.

5、0 注：网格点表示象素中心,K=0.4,例：用DDA算法光栅化直线段 x floor(y+0.5) y 111 221+4/7 321+8/7 4 31+12/7 531+16/7 641+20/7 741+24/7 851+28/7,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; for (x=x0, y=y0; xx1;x+) Setpixel (x, floor(y+0.5), color); y=y+k; ,安徽师范

6、大学数学计算机学院 杭后俊,考虑到 即y每次减少k(即直线斜率)；,（2）当从线段的右端点向左端点处理时,让x每次递减1,即x每次递增1/k.,其次考虑k 1的情形,分如下两种情况,（1）当从线段的下端点向上端点处理时， y每次递增1,即x每次递减1/k.,（2）当从线段的上端点向下端点处理时， y每次递减1,void ddaline(int x1,int y1,int x2,int y2,int color) int i; float dx, dy, length,x,y; if (fabs(x2-x1)=fabs(y2-y1) length=fabs(x2-x1); else length

7、=fabs(y2-y1); dx = (x2-x1)/length; dy=(y2-y1)/length; i=1;x= x1;y= y1; while(i=length) putpixel (floor(x+0.5), floor(y+0.5), color); x=x+dx; y=y+dy; i+; ,适用于任意方向直线段的DDA算法。,DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。,2 Bresenham算法,假设当前直线上的像素坐标为p(xi, yi)，那么下一个最佳像素要么是p

8、1，要么是p2。y值要么不变，要么递增1，可通过比较d1和d2来决定。,先考虑直线斜率k在01之间，从左到右绘制情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。,根据误差项d的值来决定是否增1的过程如下：,设y=y1y0, x=x1x0，则k=y/x，代入上式，得；,是常量，与像素位置无关,则ei的符号与(d1-d2)的符号相同。 当ei0时，像素p2(xi1，yi1)与直线上理想位置更接近； 当ei=0时，两个像素与直线上理想位置一样接近，可约定取p2(xi1，yi1)。,如果ei=0，选择右上方像素，即： ，则：,如

9、果ei0，选择右方像素，即： ，则：,在起始像素(x0，y0)的第一个参数d0为：,这样，我们已经得到斜率在0、1之间的直线（从左到右绘制）的Bresenham画线算法： 1）初始化。 dy=y1-y0,dx=x1-x0,e=2*dy-dx,delta1=2*dy,delta2= 2*(dy-dx) 。 2）画点（x0,y0）。 3）根据当前最佳像素的判别式e的符号确定下一个象素。xi+1=xi+1,如果e=0， yi+1=yi+1，e=e+delta2。 3）画点（ xi+1， yi+1）。 4）如果xx1,则转步骤3）；否则转5）。 5）结束。,void Bresenham_Line (i

10、nt x0,int y0,int x1, int y1,int color) int dx,dy,e,i,x,y; dx = x1-x0, dy = y1- y0, e=2*dy-dx; delta1=2dy; delta2=2dy-2dx; x=x0, y=y0; for (i=0; i=0) y+; e=e+delta2; else e=e+delta1; ,例： ixiyie 100-1 2103 321-3 4311 42-5 52 -1,安徽师范大学数学计算机科学学院 计算机图形学,例：请仿照图3-4用Bresenham画线算法对直线段P1P2进行光栅化时的光栅点的位置。其中P1（2

11、，2），P2（7，4）。 ixiyie 122-1 2323 343-3 4531 64-5 74 -1,安徽师范大学数学计算机科学学院 计算机图形学,假设当前直线上的像素坐标为p(xi, yi)，那么下一个最佳像素要么是p1，要么是p2。y值要么不变，要么递减1，可通过比较d1和d2来决定。,再考虑直线斜率k在-10之间，从左到右绘制情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。,yi-1,根据误差项d的值来决定是否增1的过程如下：,设y=y1y0, x=x1x0，则k=y/x，代入上式，得；,是常量，与像素位置无关

12、,则ei的符号与(d1-d2)的符号相同。 当ei0时，像素p2(xi1，yi-1)与直线上理想位置更接近； 当ei=0时，两个像素与直线上理想位置一样接近，可约定取p2(xi1，yi-1)。,如果ei=0，选择右下方像素，即： ，则：,如果ei0，选择右方像素，即： ，则：,在起始像素(x0，y0)的第一个参数d0为：,这样，我们已经得到斜率在-1到0之间（从左到右绘制）的Bresenham画线算法： 1）初始化。 dy=y1-y0,dx=x1-x0,e=-2*dy-dx,delta1=-2*dy,delta2= 2*(-dy-dx) 。 2）画点（x0,y0）。 3）根据当前最佳像素的判别

13、式e的符号确定下一个象素。xi+1=xi+1,如果e=0， yi+1=yi-1，e=e+delta2。 3）画点（ xi+1， yi+1）。 4）如果xx1,则转步骤3）；否则转5）。 5）结束。,void Bresenham_Line (int x0,int y0,int x1, int y1,int color) int dx,dy,e,i,x,y; dx = x1-x0, dy = y1- y0, e=-2*dy-dx; delta1=-2dy; delta2=-2dy-2dx; x=x0, y=y0; for (i=0; i=0) y-; e=e+delta2; else e=e+de

14、lta1; ,例： ixiyie 102-1 2123 321-3 4311 40-5 50 -1,安徽师范大学数学计算机科学学院 计算机图形学,例：请用Bresenham画线算法对直线段P1P2进行光栅化,时的光栅点的位置。其中P1（1，3），P2（6，1）。 ixiyie 113-1 2233 332-3 4421 51-5 61 -1,安徽师范大学数学计算机科学学院 计算机图形学,同理，可以得到得到斜率在-1到1之间，从右到左绘制的直线段的Bresenham画线算法。,安徽师范大学数学计算机科学学院 计算机图形学,综合上述讨论，我们得到斜率在-1到1之间的直线段的Bresenham画线算

15、法： 1）初始化。 dy=abs(y1-y0),dx=abs(x1-x0),e=2*dy-dx,delta1=2*dy,delta2= 2*(dy-dx) 。 2）int tx=(x2-x1) 0 ? 1:-1; int ty=(y2-y1)0 ? 1: -1; 3）画点（x0,y0）。 4）根据当前最佳像素的判别式e的符号确定下一个象素。xi+1=xi+tx,如果e=0， yi+1=yi+ty，e=e+delta2。 5）画点（ xi+1， yi+1）。 6）如果xx1,则转步骤4）；否则转7）。 7）结束。,斜率在-1到1之间的直线段的Bresenham画线程序段。 void Bresen

16、ham_Line01 (int x0,int y0,int x1, int y1,int color) int dx,dy,e,i,x,y; dx = abs(x1-x0), dy = abs(y1- y0), e=2*dy-dx; delta1=2dy; delta2=2dy-2dx; int tx=(x2-x1) 0 ? 1:-1; int ty=(y2-y1)0 ? 1: -1; x=x0, y=y0; for (i=0; i=0) y+=ty; e=e+delta2; else e=e+delta1; ,思考:如何将Bresenham画线算法推广到|k|1的情形？,安徽师范大学数学计算

17、机科学学院 计算机图形学,利用对称性,将Bresenham画线算法推广到|k|1的情形。,安徽师范大学数学计算机科学学院 计算机图形学,void bresenhamLine02 (int x0,int y0,int x1, int y1,int color) int dx,dy,e,i,x,y; dx = abs(y1-y0), dy =abs(x1- x0), e=2*dy-dx; delta1=2dy; delta2=2dy-2dx; int tx=(x2-x1) 0 ? 1:-1; int ty=(y2-y1)0 ? 1: -1; x=y0, y=x0; for (i=0; i=0) y

18、+=ty; e=e+delta2; else e=e+delta1; ,综合以上讨论，我们得到Bresenham画线算法绘制任意方向直线段的程序段。 见教材P47,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,首先讨论假设直线的斜率在0、1之间，从左到右绘制的情况。 当前象素点为(xp, yp) 。下一个象素点为P1 或P2 。 设M=(xp+1, yp+0.5)，为p1与p2 之中点，Q为理想直线与x=xp+1 垂线的交点。将Q与M的y坐标进 行比较。 当M在Q的下方，则P2 应为 下一个象素点； M在Q的上方，应取P1为下一点。,3 中点画线法

19、 Midpoint Line Algorithm,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 当d0，M在Q点上方，取右方P1为下一个象素； 当d=0，选P1或P2均可，约定取P1为下一个象素；,安徽师范大学数学计算机科学学院 计算机图形学,但这样做，每一个象素的计算量是4个加法，两个乘法。运算效率不高，需要进一步改进。,安徽师范大学数学计算机科学学院 计算机图形学,因为d是xp, yp

20、的线性函数， 因此可采用增量计算，提高运算效率。 （1）若d0，则取正右方象素P1 (xp+1, yp), 要判断下一个象素位置，应计算像素P1的判别式： d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a； 增量为a， （2）若d0时，则取右上方象素P2 (xp+1, yp+1)。要判断再下一象素，则要计算像素P2的判别式： d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为ab。,安徽师范大学数学计算机科学学院 计算机图形学,可以用2d代替d来摆脱小数，提高效率。 因此，在具体的实现时，我们令 d0=2a+

21、b 同样，对于每一个象素的判别式d都要乘2。判别式的增量变为2a或2（a+b)。,画线从(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。,这样，我们已经得到斜率在0、1之间，自左至右绘制的直线的中点画线算法： 1）初始化。 a=y0-y1,b=x1-x0,d=2*a+b,delta1=2*a,delta2=2*(a+b)。 2）画点（x0,y0）。 3）计算当前象素Pi的判别式d，根据d的符号确定下一个象素。xi+1=xi+1,如果d=0,yi+1=yi,。d=d+delta1。

22、如果d0， yi+1=yi+1，d=d+delta2。 3）画点（ xi+1， yi+1）。 4）如果xx1,则转步骤3）；否则转5）。 5）结束。,安徽师范大学数学计算机科学学院 计算机图形学,例：用中点画线法 ixiyid 1001 210-3 3213 431-1 425 52 1,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,void midpointline (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

23、+b; d1=2*a, d2=2* (a+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); /* while */ /* mid PointLine */,/*midpointline.c*/,安徽师范大学数学计算机科学学院 计算机图形学,其它斜率情形 （1）用同样的推导过程，不难得出当直线斜率-11时，将x,y坐标互换以完成递推过程。在画点时再将x,y坐标互换。 见教材P49-50程序段,例：用中点画线法光栅化直线段

24、 先光栅化直线段 ixiyid 1001 210-3 3213 431-1 425 52 1,安徽师范大学数学计算机科学学院 计算机图形学,再利用对称性： ixiyi 100 201 312 413 24 25,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,3.2 圆（弧）的扫描转换算法,直角坐标法、参数方程法、中点画圆算法和Bresenham画圆算法等。,1、直角坐标法,直角坐标法的缺点：1）效率太低。2）在圆的左右两侧象素太稀疏。,让x从xc-r到xc+r变化，每次递增1，就可以求出对应的y坐标。,安徽师范大学数学计算机科学学院 计算机图形学,

25、安徽师范大学数学计算机科学学院 计算机图形学,2、参数方程法,给出圆的极坐标方程：,让从0到2变化，每次递增/180，可以求出圆周上的离散象素点。,该算法生成的象素均匀。但含有三角函数运算，效率太低。,安徽师范大学数学计算机科学学院 计算机图形学,draw_circle02(x1,y1,r,c) int x1,y1,r,c; float x,y,theta; for(theta=0; theta =2*PI;theta+=PI/180) x=x1+r*cos(theta); y=y1+r*sin(theta); putpixel(x,y,c); ,#include #include #defi

26、ne PI 3.14 main() int gdriver=DETECT,gmode; initgraph( ,/*circle02.c*/,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,考虑中心在原点，半径为R 的第二个8分圆。 构造函数： 构造判别式（圆方程）,安徽师范大学数学计算机科学学院 计算机图形学,若 d=0, 则应取P2为下一象素，而且下一象素的判别式为 第 一个象素是（0,R）， 判别式d的初始值为,安徽师范大学数学计算机科学学院 计算机图形学,MidPointCircle(int r, int color) int x,y; fl

27、oat d; x=0; y=r; d=1.25-r; putpixel (x,y,color); while(xy) if(d0) d+=2*x+3; x+; else d+=2*(x-y)+5; x+;y-; putpixel (x,y,color); ,为了进一步提高算法的效率，可以将上面算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d,则e为整数。 容易看出， e0=d0-0.25=1-R 因此有：,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,若 e=0, 则应取P2为下一象素，而且下

28、一象素的判别式为 第 一个象素是（0,R）， 判别式d的初始值为,1）初始化。 x=0;y=r;e=1-r； 2）画点（x,y）。 3）根据当前最佳像素的判别式e的符号确定下一个象素。如果e=0，e=e+ 2*(x-y)+5，y=y-1。 4）x+。 5）画点（x，y）。 6）如果xy,则转步骤3）；否则转7）。 7）结束。,安徽师范大学数学计算机科学学院 计算机图形学,MidPointCircle(int r, int color) int x,y,e; x=0; y=r; e=1-r; putpixel (x,y,color); while(xy) if(e0) e+=2*x+3; x+;

29、 else e+=2*(x-y)+5; x+;y-; putpixel (x,y,color); ,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,思考：如何生成圆心在（xc,yc),半径为r的圆？,可以看作圆心在原点的等圆的平移。,安徽师范大学数学计算机科学学院 计算机图形学,3.3 椭圆的扫描转换算法,讨论的方法与中点画圆类似。 我们首先讨论中心在坐标原点的标准椭圆。 即 令 下面讨论第一象限的四分之一椭圆弧。,安徽师范大学数学计算机科学学院 计算机图形学,由微积分的知识，在该椭圆上点（x,y）处的法向量为： 当椭圆弧上的点从（0，b ）向（a，

30、0）变化过程中，b2xa2y，也就是说，在该椭圆弧上一定存在点P，在该点处 b2x=a2y。,安徽师范大学数学计算机科学学院 计算机图形学,先讨论上半椭圆弧：假设当前象素为（xp,yp），那么下一对侯选象素的中点为（xp+1,yp-0.5）。因此，判别式 如果 ,应取正右方的 象素（xp+1,yp）；如果 , 应取右下方的象素（xp+1,yp-1）。 与圆的中点扫描算法类似， 我们也可以采用增量算法计算判别式以提高计算效率。,安徽师范大学数学计算机科学学院 计算机图形学,如果 ,应取正右方的象素（xp+1,yp）；该象素的判别式为 如果 ,应取右下方的象素（xp+1,yp-1）。该象素的判别式

31、为 初始时，,安徽师范大学数学计算机科学学院 计算机图形学,现在讨论下半椭圆弧：假设当前象素为（xp,yp），那么下一对侯选象素的中点为（xp+0.5,yp-1）。因此，判别式 如果 ,应取右下方的 象素（xp+1,yp-1）；如果 , 应取正下方的象素（xp,yp-1）。 类似，我们来计算增量。,安徽师范大学数学计算机科学学院 计算机图形学,如果 ,应取右下方的象素（xp+1,yp-1）；该象素的判别式为 如果 ,应取正下方的象素（xp,yp-1）。该象素的判别式为,安徽师范大学数学计算机科学学院 计算机图形学,下面来求d2的初值。显然， d2的初值出现在由上半椭圆弧转入下半椭圆弧的 时候。

32、下半椭圆弧的第一个象素就是上半椭圆弧的最后一个象素。 设在上半椭圆弧的最后一个象素是（xp,yp），那么d2的初值为,midpointellipse(a,b,c) int a,b,c; int x,y;float d1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); putpixel(x,y,c); while(b*b*xa*a*y) if(d10) d1+=b*b*(2*x+3); x+; else d1+=b*b*(2*x+3)+a*a*(-2*y+2); x+;y-; putpixel(x,y,c); /*上半椭圆结束*/,d2=floor(b*b*(x+0.5)*

33、(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b+0.5); while(y0) if(d20) d1+=b*b*(2*x+2)+a*a*(-2*y+3); x+;y-; else d2+=a*a*(-2*y+3); y-; putpixel(x,y,c); ,midpointellipse(a,b,c) int a,b,c; int x,y;float d1,d2; x=0;y=b; d1=floor(b*b+a*a*(-b+0.25)+0.5); putpixel(x,y,c); putpixel(x,-y,c); putpixel(-x,y,c); putpixel(-x,

34、-y,c); while(b*b*xa*a*y) if(d10) d1+=b*b*(2*x+3); x+; else d1+=b*b*(2*x+3)+a*a*(-2*y+2); x+;y-; putpixel(x,y,c); putpixel(x,-y,c); putpixel(-x,y,c); putpixel(-x,-y,c); /*上半椭圆结束*/,有对称性，不难得出中心在原点的整个椭圆的算法。,d2=floor(b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b+0.5); while(y0) if(d20) d1+=b*b*(2*x+2)+a*a*

35、(-2*y+3); x+;y-; else d2+=a*a*(-2*y+3); y-; putpixel(x,y,c); putpixel(x,-y,c); putpixel(-x,y,c); putpixel(-x,-y,c); ,midpointellipse(xr,yr,a,b,c) int xr,yr,a,b,c; int x,y;float d1,d2; x=0;y=b; d1=floor(b*b+a*a*(-b+0.25)+0.5); putpixel(x+xr,y+yr,c); putpixel(x+xr,-y+yr,c); putpixel(-x+xr,y+yr,c); put

36、pixel(-x+xr,-y+yr,c); while(b*b*xa*a*y) if(d10) d1+=b*b*(2*x+3); x+; else d1+=b*b*(2*x+3)+a*a*(-2*y+2); x+;y-; putpixel(x+xr,y+yr,c); putpixel(x+xr,-y+yr,c); putpixel(-x+xr,y+yr,c); putpixel(-x+xr,-y+yr,c); /*上半椭圆结束*/,由平移变换，立即得到中心在任意位置（xr,yr)的椭圆的算法。,d2=floor(b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b

37、*b+0.5); while(y0) if(d20) d2+=b*b*(2*x+2)+a*a*(-2*y+3); x+;y-; else d2+=a*a*(-2*y+3); y-; putpixel(x+xr,y+yr,c); putpixel(x+xr,-y+yr,c); putpixel(-x+xr,y+yr,c); putpixel(-x+xr,-y+yr,c); ,安徽师范大学数学计算机科学学院 计算机图形学,主函数如下：,#include #include main() int gdriver=DETECT,gmode; initgraph( ,安徽师范大学数学计算机科学学院 计算机

38、图形学,本节思考题,1、请写出能够光栅化任意方向直线段的DDA算法（程序） 2、用DDA算法光栅化直线段 3、请仿照图3-4用Bresenham画线算法对直线段P1P2进行光栅化时的光栅点的位置。其中P1（2，2），P2（7，4）。 4、将Bresenham画线算法推广到k1情形。 5、用直角坐标法对圆（弧）进行扫描转换有哪些缺陷？ 4、试编写算法，对圆心在任意位置的圆进行扫描转换。 6、在对第一象限八分之一椭圆弧进行光栅扫描转换时，由上半椭圆弧向下半椭圆弧过渡的条件是什么？,安徽师范大学数学计算机科学学院 计算机图形学,7、下面是光栅化第二象限八分之一圆弧的中点算法，请完成填空。 1）初始化

39、。 x=0;y=r;e= ； 2）画点 。 3）根据当前最佳像素的判别式e的符号确定下一个象素。如果e=0，e= ，y=y-1。 4）x+。 5）画点（x，y）。 6）如果 ,则转步骤3）；否则转7）。 7）结束。,安徽师范大学数学计算机科学学院 计算机图形学,3.3 区域填充,安徽师范大学数学计算机科学学院 计算机图形学,填充二值位图,安徽师范大学数学计算机科学学院 计算机图形学,填充RGB图象,多边形区域有两种重要的表示方法 顶点表示和点阵表示。 顶点表示，即是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不

40、能直接用于区域填充。 点阵表示，则是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于进行填充。,安徽师范大学数学计算机科学学院 计算机图形学,区域填充的方法主要有： （多边形域的）扫描线填充算法、区域的递归填充算法 （简单的种子填充算法） 、区域的扫描线填充算法（改进的种子填充算法）、边界标志算法等。 扫描线类算法适应于顶点表示，种子填充类算法、边界标志算法等适应于点阵表示。,安徽师范大学数学计算机科学学院 计算机图形学,3.3.1 区域的递归填充算法 （简单的种子填充算法）,内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另外的颜色； 边界表示：区域边界上

41、的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能具有与边界相同的颜色。,和递归填充算法相关的两种区域的表示,安徽师范大学数学计算机科学学院 计算机图形学,边界表示的区域的递归填充算法的思想,在给出区域光栅化后的边界位置及边界颜色代码boundary_color后，现在要从多边形内部某一象素（x,y）开始按一定的填充方法对多边形进行填充。该象素称为种子点。要求填充的颜色为fill_color。,安徽师范大学数学计算机科学学院 计算机图形学,内点表示的区域的递归填充算法的思想,在给出区域光栅化后的内点的颜色代码oldcolor后，现在要从多边

42、形内部某一象素（x,y）开始按某一种填充方法对多边形进行填充。该象素称为种子点。要求填充的颜色为newcolor。,安徽师范大学数学计算机科学学院 计算机图形学,两种填充方式,四邻法：已知象素是区域内的一点，据此向上、下、左、右4个方向测试、填色、扩散。,八邻法：已知象素是区域内的一点，据此周围8个方向测试、填色、扩散。,安徽师范大学数学计算机科学学院 计算机图形学,四连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。,区域按连通情况又可分为四连通区域和八连通区域。,区域的递归填充算法要求区域是连通的，因为只有在连通区域中，

43、才可能将种子点的颜色扩展到区域内的其它点。,区域的连通性,安徽师范大学数学计算机科学学院 计算机图形学,八连通区域指的是从区域内每一像素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下移动的组合，在不越出区域的前提下，到达区域内的任意像素。,安徽师范大学数学计算机科学学院 计算机图形学,四邻法的缺点：当用四邻法填充一个八连通区域时，由于它无法填充对角线上的连通象素，因而可能造成某些区域没有被填上。 但是，如果希望两个区域填不同的颜色，用四邻法就比较合适。,安徽师范大学数学计算机科学学院 计算机图形学,八邻法的缺点：当用八邻法填充一个四连通区域时，由于它填充是按8个方向进行的，因而

44、可能造成从对角线方向越界，造成意想不到的后果。,一般来说，四邻法比八邻法用得更普遍。因为，填不满比涂出界更容易补救。,安徽师范大学数学计算机科学学院 计算机图形学,边界表示的四连通区域的递归填充算法 。 内点表示的四连通区域的递归填充算法 。 边界表示的八连通区域的递归填充算法 。 边界表示的八连通区域的递归填充算法 。,四邻法,八邻法,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,安徽师范大学数学计算机科学学院 计算机图形学,1、试写出和递归填充算法相关的两种区域的表示。 顶点表示，用多边形的顶点序列来表示多边形。 点阵表示，用位于多边形内的像素

45、集合来刻画多边形。 2、解释下列名词： 四邻法、八邻法，四连通区域、八连通区域。 3、写出边界表示的4连通区域的递归填充算法。 4、写出内点表示的4连通区域的递归填充算法。,本节思考题（作业）,安徽师范大学数学计算机科学学院 计算机图形学,5、如图所示的区域是 八连通区域 （四连通区域，八连通区域），它可以用 八邻法 （四邻法，八邻法）一次性正确填充。,安徽师范大学数学计算机科学学院 计算机图形学,6、如图所示的区域是是 四连通区域 （四连通区域，八连通区域），它可以用用 四邻法 （四邻法，八邻法）一次性正确填充。,安徽师范大学数学计算机科学学院 计算机图形学,简单的种子填充算法中含有4条递归

46、语句，效率太低。并且当区域过大时会造成堆栈溢出。 解决上述问题的办法是引入扫描线算法，得到了各种改进的算法，即区域的扫描线填充算法。主要有多边形区域的扫描线填充算法、和扫描线种子填充算法等。,3.3.2 扫描线种子填充算法(改进的种子填充算法),简单种子填充算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用扫描线种子填充算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。,区域填充的扫描

47、线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点(x，y)入栈。 (2)出栈：若栈空则结束。否则取栈顶元素(x，y)，以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点(x，y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回第(2)步。,y=pt.y; x=pt.x; while(pdc-GetPixel(x,y)=oldcolor) pdc-SetPixe

48、l(x,y,newcolor); x+; xr=x-1;/标记区间右端点,向扫描线右方填充：,x=pt.x-1; while(pdc-GetPixel(x,y)= oldcolor) pdc-SetPixel(x,y,newcolor); x-; xl=x+1; ;/标记区间左端点,向扫描线左方填充：,x=xl; y=y+1; while(xGetPixel(x,y)=oldcolor) flag=1;x+; if(flag) pt.x=x-1;pt.y=y; push(pt);/将区间最右像素入栈 flag=0; while(pdc-GetPixel(x,y)!=oldcolor ,处理上一

49、条扫描线：,处理下一条扫描线：,x=xl; y=y-2; while(xGetPixel(x,y)=oldcolor) flag=1;x+; if(flag) pt.x=x-1;pt.y=y; push(pt); );/将区间最右像素入栈 flag=0; while(pdc-GetPixel(x,y)!=oldcolor ,1、扫描线种子填充算法(改进的种子填充算法)适用于任何封闭区域的填充。2、思考：圆域的填充问题。,安徽师范大学数学计算机科学学院 计算机图形学,基本思想： 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 对于一条扫描线填充过程

50、可以分为四个步骤： 求交（点） （交点）排序 交点配对 （区间）填色,3.3.3多边形扫描线填充算法,安徽师范大学数学计算机科学学院 计算机图形学,一个多边形与若干扫描线,以扫描线6为例进行分析,安徽师范大学数学计算机科学学院 计算机图形学,情况1 分析扫描线2与多边形的相交情况。,两个特殊情况的考虑,安徽师范大学数学计算机科学学院 计算机图形学,通过以上的分析，我们作出第一次修正。,当扫描线通过多边形的左右顶点时，交点计数为1。 （可以通过舍弃每条边的最高顶点来实现）,注： 上述修正还不能保证填充的正确，因为对边界上象素的取舍不当会出现所谓的“过填”问题。,安徽师范大学数学计算机科学学院 计

51、算机图形学,情况2 分析扫描线1、7与多边形的相交情况。,安徽师范大学数学计算机科学学院 计算机图形学,“过填”造成边长为2个单位的正方形变为边长为3个单位。,安徽师范大学数学计算机科学学院 计算机图形学,避免出现上述“过填”现象，必须要对多边形的边界象素进行取舍。 1）对扫描线与多边形的相交区间取“左闭右开”。 2）对扫描线与多边形的上下顶点相交时，交点的取舍方法为“下闭上开”，即丢弃上方水平边或上顶点。即当扫描线与多边形交于上顶点时，交点计数为0。当扫描线通过多边形的下顶点时，交点计数为2。,安徽师范大学数学计算机科学学院 计算机图形学,将多边形的顶点进行上述处理之后，用（水平）扫描线由下

52、到上扫描多边形，求出每条扫描线与多边形的交点，将这些交点按x 坐标进行排序，将排序后的交点成对取出，按照左闭右开的方式以给定的颜色画线。多边形被扫描后，填色也就完成了。,多边形扫描线填充算法的思想,安徽师范大学数学计算机科学学院 计算机图形学,如何去求扫描线与多边形的交点？ 直接法 将每根扫描线与多边形的所有边求交点。这种方法的效率太低，因为事实情况往往是扫描线只与多边形的少数边有交点。,安徽师范大学数学计算机科学学院 计算机图形学,活性边表法,把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表（或数组）中，称为活性边表(AET)。 结点内容 x：当前扫描线

53、与边交点的x坐标 x：从当前扫描线到下一条扫描线间x的增量，为1/k，其中k为斜率。 ymax：该边所交的最高扫描线号ymax,安徽师范大学数学计算机科学学院 计算机图形学,扫描线6的AET。,安徽师范大学数学计算机科学学院 计算机图形学,活性边表中的x（从当前扫描线到下一条扫描线间x的增量，为1/k，其中k为斜率）和ymax（该边所相交的最高扫描线号）在求交点过程中是非常有用的。这表现在如下两个方面：,安徽师范大学数学计算机科学学院 计算机图形学,1) 假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。 事实上，设该边的直线方程为：ax

54、+by+c=0； 若yyi，x=x i；则当y = y i+1时， 其中 =1/k为常数,安徽师范大学数学计算机科学学院 计算机图形学,2)当求完当前扫描线与多边形的交点后，应将与下一条扫描线不相交的边从活性边表中删除。这可以通过比较边的最高顶点的y值ymax和下一条扫描线的y值得到。,安徽师范大学数学计算机科学学院 计算机图形学,对于那些与下一条扫描线有交点的新边，应及时插入到活性边表中（按x递增排序）。为了能快速找出与当前扫描线第一次有交点的新边，我们为每一条扫描线建立一个新边表（NET） 新边表的建立：先按低端点的y坐标值对所有的边进行分组，若某边的低端点y值为ymin，则该边就放在扫描

55、线y=ymin所对应的表中；然后用排序方法，按低端点的x坐标值递增的顺序将同一组中的边排列成行。该表就是该扫描线的新边表。,NET中的基本元素、结点的构成和AEL 相同，每个边结点由以下四个域组成： 其中，各符号的含义为： ymax： 边的上端点的y坐标 x：在NET中表示边的下端点的x坐标，在AEL中表示边与扫描线的交点的x坐标 1/k：边的斜率的倒数 next：指向下一条边的指针,安徽师范大学数学计算机科学学院 计算机图形学,当建立了边表NET后，扫描线多边形填充算法可按如下步骤进行： （1）初始化AET，使之为空，取扫描线纵坐标y的初始值为多边形所有顶点中最小的y值。 （2）将NET中与

56、当前y有关的结点加入至AET，同时保存AEL中按x值从小到大实现的排序序列 。 （3） 对于AET中的扫描线y，在一对交点之间填充所需要的像素值 。 （4 ）从AET中删掉y=ymax的结点。 （5） 对于留在AET中的每个结点，执行xi+1=xi + 1/k。 （6） 对AET中的各结点按x值从小到大排序 。 （7）y =y+1，成为下一条扫描线的坐标。 （8）若AET非空 ，转（2），否则，停止。,安徽师范大学数学计算机科学学院 计算机图形学,void polyfill (polygon, color) for (各条扫描线，标识为i) 初始化新边表头指针NET i； 把ymin = i

57、的边放进边表NET i； y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i) 把新边表NETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间上的像素(x, y)，用drawpixel (x, y, color)改写像素颜色值； 遍历AET表，把y max= i的结点从AET表中删除，并把y max i结点的x值递增x； ,多边形扫描线填充的算法,边界标志算法,基本思想 在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的像素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的像素。 使用一个布尔量inside来指示当前点是否在多边形内的状态。Inside的初值为假，每当当前访问的像素为被打上边标志的点，就把inside取反。对未打标志的像素，inside不变。若访问当前像素时，inside为真，说明该像素在多边形内，则把该像素置为填充颜色。,void edgemark_fill(polydef, color) 多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转