计算机图形学：第二章 图形基元的显示

1、第二章 图形基元的显示 扫描转换 将图形描述转换成用象素矩阵表示的过程图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、椭圆、多边形 第一节 直线扫描转换算法 第二节 圆的扫描转换算法第三节 椭圆扫描转换算法第四节 线宽与线型的处理第五节 区域填充第一节 直线扫描转换算法DDA直线扫描转换算法 中点画线法 Bresenham画线算法 端点 (x1,y1)和(x2,y2)， 假定 x1fabs(dy)?fabs(dx):fabs(dy);dx/=e; dy/=e; x=x1;y=y1;for(int i=1;i0 ；直线下方的点，F(x，y)0。 将M代入F(x，y) d = F(M

2、) = F( xi+1，yi+0.5 ) =a ( xi+1 ) + b ( yi+0.5 ) + c当 d 0，则取正右方的P1。当d=0时，二者一样合适，取P1。 对每一个象素计算判别式d，根据它的符号确定下一象素。 d0 时，取正右方象素P1 ，判断再下一个象素应取哪个，应计算d1 = F ( xi+2 ，yi+0.5 ) = a ( xi+2 ) + b ( yi+0.5 ) +c = d + a故d的增量为a。 而若d0，则取右上方象素P2。要判断再下一个象素，则要计算d2 = F ( xi+2，yi+1.5 )= a ( xi+2 ) +b ( yi+1.5 ) + c= d+a+

3、b 故在第二种情况,d的增量为a+b 再看d的初始值。显然，第一个象素应取左端点(x0,y0)，相应的判别式值为 d0 = F (x0 +1，y0 +0.5 ) =a(x0+1)+b( y0 +0.5 )+c= ax0+by0 +c+a+0.5b=F (x0,y0) + a + 0.5b 由于(x0，y0)在直线上， 故F(x0，y0)=0。因此,d的初始值为d0 = a+0.5b 考虑用2d来代替d的计算void MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ; a = y0 - y1;b = x1

4、 - x0; d = 2 * a + b ;delta1 = 2 * a ; delta2 = 2 *( a + b); x = x0 ; y = y0 ;SetPixel(x,y,color);while( xx1 )if( d0 ) x +;y +; d+= delta2;else x +; d+= delta1; SetPixel(x,y,color); /* while */* MidpointLine */ xyd001(-4)10-3(+6)213(-4)31-1(+6)425(-4)521(x=x1=5)(0，0)、(5，2) a = y0 -y1 = -2，b = x1 - x

5、0 = 5 d0 = 2 * a + b = 1 Bresenham算法 2-122-132-142-152-16确定P1 ,将其代入式 2-12，令i=1，可计算求出 2-172-18void BresenhamLine(int x1,int y1,int x2,int y2)int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1; dy=y2-y1;p=2*dy-dx;for(;x=0) y+;p+=2*(dy-dx);elsep+=2*dy;第二节 圆的扫描转换算法 x2+y2=R2 x=Rcos() y=Rsin()中点画圆法 点(0,R)至( ， )的八分之一圆弧构造函

6、数：F(x,y)=x2+y2-R2圆上的点，F(x,y)=0圆外的点，F(x,y)0圆内的点，F(x,y)0 P1和P2的中点为 M=( xi+1,yi-0.5) F(M)0时，M在圆外，取P2F(M)=0时，P1或P2随取一个即可，取P2 构造判别式 若d0，取P1作为下一个象素，而且再下一个象素的判别式为 而若d0，应取P2作为下一个象素，而且再下一个象素的判别式 第一个象素是(0,R)，判别式d的初始值为 d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R。void MidpointCircle(int R) int x,y;double d;x=0;y=R;d=1.2

7、5-R;SetPixel(x,y,color);while(xy)if(d0) d+=2*x+3;x+; elsed+=2*(x-y)+5;x+;y-;SetPixel(x,y,color); 在上述算法中，使用了浮点数来表示判别式d。 简化算法，在算法中全部使用整数，使用e=d-0.25代替d。 显然，初始化运算d=1.25-R对应于e=1-R。 判别式d0对应于e-0.25。 算法中可把d直接换成e。又由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e-0.25等价于e0。 增量计算技术若d0，P1为下一个像素，d的增量为若d0，P2为下一个像素，d的增量为 x和y的

8、变化都将影响2的值。 每当x递增1，1递增2，2递增2。 每当y递减1，2递增2。 若d0，P1为下一个像素，x递增1， 1递增2，2递增2； 若d0，P2为下一个像素，x递增1， y递减1，1递增2，2递增4。初始像素为(0,R)，所以1的初值为3，2的初值为-2R+5。 void MidpointCircle2(int R) int x,y,deltax,deltay,d;x=0;y=R;d=1-R;deltax=3;deltay=5-R-R;SetPixel(x,y,color);while(xy) if(d0和dD0若pi0，即dH 0，必有pi0，dD0，必有pi0。 得出结论： p

9、i做判别量， pi0选H点为下一个象素点，当pi0 0时，选D点为下一个象素点。从 计算 当pi0时，应选D点，即选 当pi0时，应选H，即选 画圆的起始点是(0，R)，即x1=0，y1=R，代入前式，令i=1，就得到： void BresenhamCircle(int R) int x,y,p;x=0; y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6; 修改语句SetPixel(x,y,color)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。第三节 椭圆扫描转换算法 椭圆上椭圆外椭圆内椭圆上部分曲

10、线选下一个待选像素从 、二者挑选其一。其像素中点为选下一对候选像素就是和其中点为 确定上部分的初始判别式为开始画点，所以则第一点的中点坐标为相应判别式为 对于下部分，当前点下一对候选像素的是中点是判别式为选下一对候选像素就是和其中点为 中点的判别式为 选的下一对候选像素就是和中点为判别式为 下部分中点判别式初始值的处理如下 当前点（上部分）：当前点（下部分）：void MidpointEllipse(int a,int b)int x,y;double d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);SetPixel(x,y,color);while(b*b*(x+1)a

11、*a*(y-0.5) if(d10)if(d20)d2+=b*b*(2*x+2)+a*a*(-2*y+3);x+;y-;elsed2+=a*a*(-2*y+3);y-;SetPixel(x,y,color);第四节 线型与线宽的处理 线型处理:实线段长度、间距线型：实线、虚线和点线等虚线：实线段(画线)与空白段相间点线：短画线与空白段像素模板(Pixel Mask) 数字0和1组成的串直线线宽的处理 （依赖输出设备） 线刷子和方刷子（光栅设备）垂直刷子 水平刷子线段端点：线帽(Line Cap) ：方帽、凸方帽和圆帽等。 缺点：斜线、水平线线宽不同；线宽为偶数时，中心偏移；端点只能水平或竖直。

12、斜角连接(Miter Join)通过延伸两条线的外边界直到它们相交；圆连接(Round Join)通过用直径等于线宽的圆弧边界将两线段连接而成；斜切连接(Bevel Join)则是通过用方帽和在两线段相交处的三角形间隙中填充来生成。 方刷其它线宽处理方式区域填充或像素模板(a)像素模版 (b)用该模版进行线宽处理曲线的线型和线宽 像素模板 线刷、方刷 第五节 区域填充 种子填充算法 区域是指光栅网格上的一组象素。 区域填充是把某确定的象素值送入 到区域内部的所有象素中。 区域填充方法分为两大类。 区域由多边形围成，区域由多边形的顶点序列来定义;另一类方法是通过象素的值来定义区域的内部，相应的技

13、术称为是以象素为基础的. 内定义区域，定义方法是指出区域内部所具有的象素值,此时区域内部所有象素有某个原值oldvalue; 边界定义区域，定义方法是指出区域边界所具有的象素值。此时区域边界上所有象素具有某个边界boundaryvalue。区域的边界应该是封闭的，并且应该指明区域的内部。 以象素为基础的区域填充主要是依据区域的连通性进行。 四连通:从区域中的一个象素出发，经连续地向上下左右四个相邻象素的移动，就可以到达区域内的任意另一个象素. 八连通:如果除了要经上下左右的移动，还要经左上、右上、左下和右下的移动，才能由一个象素走到区域中另外任意一个象素. 利用区域的连通性进行区域填充，除了需

14、要区域应该明确定义外，还需要事先给定一个区域内部象素，这个象素称为种子。 做区域填充时，要进行对光栅网格的遍历，找出由种子出发能达到而又不穿过边界的所有象素。 这种利用连通性的填充，其主要优点是不受区域不规则性的影响，主要缺点是需要事先知道一个内部象素。 void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue)/*(x，y)为种子 oldvalue是原值 newvalue是新值，应不等于原值。*/ if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/赋新值 Floodf

15、ill(x,y-1,oldvalue,newvalue); /四向扩散 Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue); /四连通内定义区域填充算法void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)/*(x,y) 为种子位置boundaryvalue是边界象素值newvalue是区域内象素新值，未填充前区域内不应有值为newvalue的象素。*

16、/ if( GetPixel(x,y)!=boundaryvalue & GetPixel(x,y)!=newvalue) / 未达边界且未访问过 SetPixel(x,y,newvalue);/赋以新值Boundaryfill(x,y-1,boundaryvalue,newvalue); /向四个方向扩散。Boundaryfill(x,y+1,boundaryvalue,newvalue);Boundaryfill(x-1,y,boundaryvalue,newvalue);Boundaryfill(x+1,y,boundaryvalue,newvalue);/四连通边界定义区域填充算法 扫

17、描线种子填充算法 将区域内由边界点限定的同一行内相连接的不具有新值newvalue的一组象素称为一个象素段，象素段用它最右边的象素来标识。 算法的步骤如下： 1对种子所在象素段进行填充。 2从右至左检查种子所在行的上一横行，将查得的象素段依次编号存入堆栈。接着对种子所在行的下一横行同样处理。 3若堆栈为空则算法结束，否则从堆栈顶部取出一个象素段。就以这个象素为新的种子，返回到1。void ScanlineSeedfill(CDC* pDC,int x,int y,COLORREF boundaryvalue,COLORREF newvalue)using namespace std; int

18、x0,xl,xr,y0,xid,count=0;bool flag;stack s; CPoint p;s.push(CPoint(x,y);/种子入栈while(!s.isempty()p=s.pop(); /读栈顶元素 s.top(); /栈顶象素出栈 x=p.x; y=p.y; pDC-SetPixel(x ,y ,newvalue); x0= x+1;while(pDC-GetPixel(x0,y) !=boundaryvalue &pDC-GetPixel(x0,y)!=newvalue) pDC-SetPixel(x0,y ,newvalue);x0+;xr=x0-1;/最右象素x

19、0= x-1;while(pDC-GetPixel(x0,y)!=boundaryvalue &pDC-GetPixel(x0,y)!=newvalue)pDC-SetPixel(x0,y,newvalue); x0-;xl=x0+1;/最左象素/检查上一条扫描线和下一条扫描线/若存在非边界且未填充的象素，/则选取代表各连续区间的种子象素入栈。y0=y;for(int i=1;i=-1;i-=2) x0=xr; y=y0+i; while(x0=xl) flag=false;while(pDC-GetPixel(x0,y)!=boundaryvalue) & (pDC-GetPixel(x0,

20、y)!=newvalue)& (x0 xl)if(!flag) flag=ture; xid=x0;x0-;/将最右侧可填充象素压入栈中if(flag)s.push(CPoint(xid,y) ); flag=false;/检查当前填充行是否被中断，若被中断，寻找左方第一个可填充象素while(pDC- GetPixel(x0,y)=boundaryvalue) )/是否为边界点|(pDC-GetPixel(x0,y)=newvalue) /是否为已填充点x0-;/若当前点为边界点或已填充点，根据前面的判断，当前点必然未超出左边界，则当前点向左移动/while(x0=xl) /for(int

21、i=1;i=-1;i-=2)/while(!s.isempty() 多边形的扫描转换算法“奇偶性：“相切” 可以分如下三个步骤来做： 1找出扫描线与多边形边界线的所有交点；2按x坐标增加顺序对交点排序；3在交点对之间进行填充。 相切点的解决方法：当顶点表现为是局部极大或局部极小时，就看做是二个，否则看做一个。局部极大，如果这个顶点的前面和后面各有一些相邻顶点的y坐标，都小于该顶点的y坐标。局部极小可类似地确定。 实际处理这个问题可以有一个简便办法，那就是对应该看做是一个的顶点，将其上面的边缩短两条相邻扫描线对应的一个单位。 计算扫描线与多边形边界线的交点： 若扫描线yi与多边形边界线交点x的坐

22、标是xi，则对下一条扫描线yi+l，它与那条边界线的交点的x坐标xi+1，可如下求出： 活跃边表AET(ActiveEdgeTable)，用这个表存贮与当前扫描线相交的各边。每次离开一条扫描线进入下一条之前，将表中有但与下一条扫描线不相交的边清除出表，将与下一条扫描线相交而表中没有的边加入表中。 边表ET(EdgeTable)，ET中各登记项按y坐标递增排序，每一登记项下的“吊桶”按所记x坐标递增排序，“吊桶”中各项的内容依次是： 1.边的上端点y坐标ymax。2. 边的下端点的x坐标xmin。3.斜率的倒数，即1/m。Void Polygonfill(EdgeTable ET, COLORR

23、EF color) 1. y=边表ET中各登记项对应的y坐 标中最小的值; 2.活跃边表AET初始化为空表; 3.while(ET表中仍有扫描线未被处 理) /处理ET表中的每一条扫描线 3.1 将ET中登记项y对应的各“ 吊桶”合并到表AET中，将 AET中各吊桶按x坐标递增排序；3.2 在扫描线y上,按照AET表提供 的x 坐标对，用color实施填充；3.3 将AET表中有y=ymax的各项 清除出表；3.4 对AET中留下的各项,分别将 x换为x+1/m.3.5 由于前一步可能破坏了AET表中 各项x坐标的递增次序，故按x坐 标重新排序； 3.6 y=y+1，去处理下一条扫描线。边填充

24、算法(正负相消法) 基本思想：对于每一条扫描线和每条多边形边的交点 ，都将该扫描线上交点右方的所有像素取补，并对多边形的每条边按一定顺序(逆时针、顺时针均可)做此处理 待填充区域 D对区域的每一条边与扫描线的每一个交点当 做沿D的边界经历一周后，只要则否则Dvoid EdgeFill(PointArray& ptArray,COLORREF color) for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) MASKyx=false; for(区域D内的每一条边PiPi+1) xs=xi; dxs=( xi+1- xi)/( yi+1- yi); for(ys=yi; ys=

25、 yi+1;ys+) xs= xs +dxs; Ixs =int(xs +0.5); for(x= Ixs;x=x2;x+) MASKysx =!MASKysx; for(y=y1;y=y2;y+)for(x=x1;x=x2;x+)if(MASKyx)SetPixel(x,y,color);栅栏(一条与扫描线垂直的直线) 栅栏填充基本思想： 对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补边标志算法(轮廓填充算法) 对每个像素访问一次边标志算法分为两个步骤： 第一步:边界像素打标志； 第二步:填充内部像素。边标志算法的程序如下：void EdgeMarkFill(PointArray& ptArray,COLORREF color) for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) MASKyx=false; /形成轮廓线for(区域D内的每一条边PiPi+1) xs=xi; dxs=(xi+1-xi)/(yi+