矢量转换为栅格(面状)

1、多边形扫描转换与区域填充在计算机图形学中，多边形有两种重要的表示方法：顶点顶点表示和点阵点阵表示。顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换多边形的扫描转换。 逐点判断算法逐点判断算法 算法原理：逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部。 问题：如何判别点

2、(x,y)关于多边形区域P的内外关系？射线法 逐点判断法简单，但效率不高 扫描线算法 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。经过观察，可以发现，对于一条扫描线，它与多边形的交点总是偶数。 对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间， （4）填色：把相交区间内的象素置成多边形颜色

3、，把相交区间外的象素置成背景色。 减少求交计算量，采用活性边表。 对于一根扫描线而言，与之相交的边只占多边形全部边的一部分,每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改进。活性边表(Active List of Side)的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前扫描线不相交的边的集合。对后者不必进行求交运算，这样就提高了算法的效率。改进的有效边表算法改进的有效边表算法1）活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中；该链表称作活性边表（边表（AEL)。算法所涉及的数据结构：AEL 与与ET的结点信息:lYmax: 所交边的最高扫描线

4、号lX：当前扫描线与边的交点的x坐标lX：边的斜率的倒数lNextage: 下一条边的指针typedef struct int ymax; float x,deltax; Edge *nextEdge; Edge; 扫描线填充算法2）边的分类表）边的分类表（ET）按照边的下端点按照边的下端点y坐标对非水平边进行分类的指针数组坐标对非水平边进行分类的指针数组,下端点下端点y坐标值等于坐标值等于i的边属于第的边属于第i类类typedef struct int ymax; float x,deltax; Edge *nextEdge; Edge; 边的分类表的作用是避免盲目求交。当处理一条扫描线时，

5、为了求出它与多边形边的所有交点，必须将它与所有的边进行求交测试。而实际上只有某几条边与该扫描线有交点。边的分类表正是用来排除不必要的求求交测试的。0123456789101145-157 5/410 2011 12 010 7 -5/311 7 5/4ET表扫描线填充算法 具体算法具体算法1、建立、建立ET；2、将扫描线纵坐标、将扫描线纵坐标y的初值置为的初值置为ET中非空元素的最小序号；中非空元素的最小序号；3、置、置AEL为空；为空；4、执行下列步骤直至、执行下列步骤直至ET和和AEL都为空都为空4.1、如、如ET中的第中的第y类非空，则将其中的所有边取出并插入类非空，则将其中的所有边取出

6、并插入AEL中；中；4.2、如果有新边插入、如果有新边插入AEL，则对，则对AEL中各边排序；中各边排序；4.3、对、对AEL中的边两两配对，（中的边两两配对，（1和和2为一对，为一对，3和和4为一对，为一对，），将每），将每对边中对边中x坐标按规则取整，获得有效的填充区段，再填充坐标按规则取整，获得有效的填充区段，再填充4.4、将当前扫描线纵坐标、将当前扫描线纵坐标y值递值值递值1；4.5、将、将AEL中满足中满足y=ymax边删去（因为每条边被看作下闭上开的）；边删去（因为每条边被看作下闭上开的）；4.6、对、对AEL中剩下的每一条边的中剩下的每一条边的x递增递增deltax，即，即x =

7、 x+deltax#include stdio.h#includestdlib.h#include math.h#define pi 3.14159265#include Conio.h#include graphics.h#include malloc.h#define closegr closegraph#define max 400/*建立结构体类型数据Edge*/typedef struct Edge int ymax; float x,deltax; struct Edge *nextEdge;Edge;struct Edge *ETmax;void initgr(void) /*

8、BGI初始化 */int gd=DETECT,gm; /* 和gd=VGA,gm=VGAHI是同样效果 */ /* 注册BGI后可以驱动不需要.BGI文件的支持运行 */ initgraph(&gd,&gm,E:TC);/*得到多边形顶点*/void GetST(float x5,float y5,float radius)int i; float r; setcolor(BLUE); x0=300; y0=100; x1=100; y1=200; x2=200; y2=300; x3=400; y3=400; x4=500; y4=200; for(i=0;iymax=y4;

9、e-x=x0;e-deltax=(x4-x0)/(y4-y0); h=(Edge*)malloc(sizeof(Edge); h-ymax=y1;h-x=x0;h-deltax=(x1-x0)/(y4-y0); e-nextEdge=h;h-nextEdge=NULL; ETn=e;n=y1; e=(Edge*)malloc(sizeof(Edge); e-ymax=y2;e-x=x1;e-deltax=(x2-x1)/(y2-y1); h=(Edge*)malloc(sizeof(Edge); h-ymax=y3;h-x=x4;h-deltax=(x3-x4)/(y3-y4); e-next

10、Edge=h;h-nextEdge=NULL; ETn=e; n=y2; e=(Edge*)malloc(sizeof(Edge); e-ymax=y3;e-x=x2;e-deltax=(x3-x2)/(y3-y2); e-nextEdge=NULL; ETn=e; void Fillin(Edge *AEL,int bottom,int top ) char *s; Edge *e; Edge *p,*q; int n,m,i=0,j=0,a8; AEL=(Edge*)malloc(sizeof(Edge);AEL-x=-1; AEL-nextEdge=NULL; for(n=bottom;

11、nnextEdge; while(q) if(p-xx)break; q=q-nextEdge; e=e-nextEdge; q=p-nextEdge; p-nextEdge=e-nextEdge; e-nextEdge=p; p=q; p=AEL;q=AEL-nextEdge; m=1; getch(); while(q) if(q-ymax=n) p-nextEdge=q-nextEdge; e=q; q=q-nextEdge;free(e); else if(p!=AEL&m%2=0) setcolor(RED); line(int)(p-x+0.5),n,(int)(q-x+0

12、.5),n); p-x+=p-deltax; q-x+=q-deltax; p=p-nextEdge; q=q-nextEdge; m+; main() int n,m ,i; float x5,y5,a5,b5,r; Edge *AEL;initgr();/* BGI初始化 */GetST(x,y,100); /*得到五角星的顶点*/setcolor(9);for(i=0;i4;i+) getch(); line(xi,yi,xi+1,yi+1);getch();getch(); line(x4,y4,x0,y0); getch(); n=y0; m=y3; getch(); CreatET

13、(x,y); Fillin(AEL,n,m); /*填充*/ outtextxy(200,400,Fillin Finished!); getch(); /* 暂停一下，看看前面绘图代码的运行结果 */ closegr(); /* 恢复TEXT屏幕模式 */问题：如何处理多边形的水平边？如何修改扫描线算法，使它能处理边自交的多边形？边填充算法（适用与帧缓存图形系统，利于硬件的实现） 简单的边填充算法 栅栏填充算法 简单的边填充算法：复杂图形中每一像素可能被访问多次，输入、输出工作量大 栅栏边填充算法：减少像素被重复访问的次数1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个

14、边界标志。2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。边界标志算法边界标志算法:算法过程void edgemark_fill(polydef, color)多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形polydef

15、相交的扫描线y ) for (扫描线上每个象素x ) if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) putpixel (x, y, color); else putpixel (x, y, background); 边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。多边形扫描转换区域填充种子填充算法种子填充算法思想：从区域内的一个点（种子）开始，由内向外将填充色扩展到整个区域

16、内的过程。条件： 要求给出边界颜色特征及区域内的一个点，并并要求区域是连通的 区域：分为4连通区域连通区域和8连通区域连通区域 表示内点表示边界点 四个方向运动 八个方向运动 四连通区域 八连通区域6754S9328区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果 常见的种子填充算法由边界表示的四连通区域种子填充算法、内点表示的四连通区域种子填充算法、边界表示的八连通区域种子填充算法、内点表示的八连通区域种子填充算法。（1）边界表示的四连通区域种子填充算法基本思想：从多边形内部任一点（像素）出发，按照“右上左下”的顺序判断

17、相邻像素，若不是边界像素且没被填充过，则对其填充，并重复上述过程，直至所有像素填充完毕。可以使用栈结构来实现该算法，种子像素入栈，当栈非空，重复执行下面操作：1）栈顶像素出栈；2）将出栈像素置成多边形填充的颜色；3）按“右上左下”的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。边界表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法（2）内点表示的四连通区域种子填充算法基本思想：从多边形内部任一点（像素）出发，按照“右上左下”的顺序判断相邻像素，若是区域内的像素，则对其填充，并重复上述过程，直至所有像素填充完毕。可以使用栈结构来实现该算法，

18、种子像素入栈，当栈非空，重复执行下面操作：1）栈顶像素出栈；2）将出栈像素置成多边形填充的颜色；3）按“右上左下”的顺序检查与出栈像素相邻的四个像素，若其中某个像素是区域内的像素，则把该像素入栈。6754S9328S247938479484795684796847978479847994794796754S9328S799填充算法演示填充算法演示种子填充算法内点表示的区域递归算法可实现如下内点表示的区域递归算法可实现如下void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) PutP

19、ixel(x,y,newColor); 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 4连通区域连通区域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color = G

20、etPixel(x,y);if(color != boundaryColor) & (color != newColor)PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/ 对边界和内点表示的八连通区域的填充，只要将上述算法的对四个

21、像素点填充改为八个像素点即可。四连通区域种子填充算法的缺点是有时不能通过狭窄区域区域，因而不能填满多边形。八连通算法的缺点是有时会填出多边形的边界。由于填不满比涂出更容易补救，因此四连通算法比八连通算法用得更多。 该算法也可以填充有孔区域。该算法也可以填充有孔区域。 缺点缺点：(1) 有些象素会入栈多次，降低算法效率；栈结构占空间。(2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。 改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法种子填充算法扫描线算法目标：减少递归层次目标：减少递归层次适用于边界表示的适用于边界表示的4 4连通区域连通区域算法思想算法思想：在任意不间断区间中只