扫描线多边形填充算法

A. 怎么用opengl扫描线算法填充多边形

扫描线算法是光栅图形学的内容，底层硬件实现。opengl是不会关注这种细节的。你写这样的代码
glBegin(GL_POLYGON);
glVertex3f(...);
...
glVertex3f(...);
glEnd();
画一个多边形，但底层的光栅化到底是怎么实现的，是否使用扫描线算法，你是不可以控制的。

B. 扫描算法增加方向和减少方向算出来的值一样吗.

一样
要实现区域的扫描线填充必须先确定填充区边界与屏幕扫描线的交点位置。然后，将填充色应用于扫描线上位于填充区域内部的每一段。扫描线填充算法利用奇偶规则识别同一内部区域（参见）。最简单的填充区域是多边形，因为每一扫描线和多边形的交点可通过求解一对联立的线性方程来获得，其中扫描线的方程是y = 常数。
给出了多边形区域的实心填充的扫描线过程。对每一条与多边形相交的扫描线，与边的交点从左向右排序，且将每一对交点之间的像素位置包括这对交点在内，设定为指定颜色。在图4.20的例子中，与边界的四个交点像素位置定义了两组内部像素。这样，填充色应用于从x=10到x = 14的5个像素和从x = 18到x = 24的7个像素。如果图案填充应用于多边形，则沿一条扫描线的每一像素颜色由与填充图案重叠的位置来确定。

C. 如何修改扫描线算法，使它能处理边自交的多边形

1. 对多边形的每一条边进行扫描转换，即对 多边形边界所经过的象素作一个边界标志。 2.填充。对每条与多边形相交的扫描线，按 从左到右的顺序，逐个访问该扫描线上的象 素。 取一个布尔变量inside来指示当前点的状态， 若点在多边形内，则inside为真。若点在多 边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为 被打上标志的点，就把inside取反。对未打 标志的点，inside不变。

D. 急求用C语言编写的扫描线填充多边形的算法

可惜，分少了。
去投票或回答问题弄50+分，问题加到50分+就可以办了。能给我投几票就更好了。( ⊙ o ⊙ )

E. 区域填充的主要思想和方法

扫描线种子填充算法思想
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
扫描线种子填充算法步骤 1、初始化堆栈。 2、种子压入堆栈。 3、While（堆栈非空）从堆栈弹出种子象素。
(1)如果种子象素尚未填充,则： ① 求出种子区段：xleft、xright。
② 填充整个区段。 (2)检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 (3)检查相邻的下扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 }
有关堆栈操作的辅助代码
1、定义栈结构： # define MAX 100 /*定义最大栈空间*/
struct stack
{
int top; /*指向栈顶的计数器*/
int xy[MAX][2]; /*种子点（二维）*/
}s; 2、初始化堆栈 s.top=－1; 3、进栈操作 pushxy(int x,int y)
{
if(s.top= =MAX－1)
{
printf(“Overflow!”);
exit(1);
}
else
{
s.top=s.top+1;
s.xy[s.top][0]=x;
s.xy[s.top][1]=y;
}
} 4、出栈操作 popxy(int *x,int *y)
{
if(s.top<0)
{
printf(“underflow!”);
exit(1);
}
else
{
*x=s.xy[s.top][0];
*y=s.xy[s.top][1];
s.top=s.top－1;
}
} 5、堆栈非空 s.top!=－1 或者 s.top>=0 扫描线种子填充算法伪代码 scanline_seed_fill(int x,int y,int boundarycolor,int newcolor)
{
int savex,xleft,xright,pflag,xenter;
//初始化堆栈；
pushxy(x,y); /*种子压入堆栈*/
while(堆栈非空)
{
popxy(&x,&y); /*栈顶象素出栈*/
savex=x; /*保存种子坐标x分量的值*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子右侧的象素*/
x++;
}
xright=x－1; /*得到种子区段的右端点*/
x=savex－1; /*准备向种子左侧填充*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子左侧的象素*/
x--;
}
xleft=x+1; /*得到种子区段的左端点*/
x=xleft;
y=y+1; /*考虑种子相邻的上扫描线*/
while(x<=xright)
{
pflag=0; /*找到新种子的标志：0为假；1为真*/
while(getpixel(x,y)!=boundarycolor && getpixel(x,y)!=newcolor&& x<xright)
{
if(pflag= =0)
pflag=1;
x++;
}
if(pflag= =1)
{
if((x= =xright)&&(getpixel(x,y)!=boundarycolor)&&(getpixel(x,y)!=newcolor))
pushxy(x,y); /*新区间超过xright,将代表该区段的象素进栈*/
else
pushxy(x－1,y); /*新区段右端点作为种子进栈*/
pflag=0;
}
xenter=x;
while((getpixel(x,y)==boundarycolor||getpixel(x,y)==newcolor)&&x<xright)
{
x++;/*向右跳过分隔带*/
}
if(xenter==x) x++;/*处理特殊情况,以退出while(x<=xright)循环*/
}
x=xleft; /*为下扫描线的处理作准备*/
y=y－2;
/*检查相邻的下扫描线,找新区段,并将每个新区段右端的象素作为种子
入栈,其方法与上扫描线的处理一样,这里省略。要求同学补充完整。*/
}
} 边相关多边形扫描线填充思想
边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。
ET用来对除水平边外的所有边进行登记,即建立边的记录。
AET则是在ET建立的基础上进行扫描转换。对不同的扫描线,与之相交的边线也是不同的,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,为此AET建立了只与当前扫描线相交的边记录链表,以提供对当前扫描线上的区段进行填充。
边相关多边形扫描线填充算法步骤
1、根据给出的顶点坐标建ET表；并求出顶点坐标中最大y值ymax和最小y值ymin。
2、定义AET指针,并使它为空。
3、使用扫描线的yj值作为循环变量,使其初值为ymin。
4、对于循环变量yj的每一整数值,重复作以下事情,直到yj大于ymax,或ET与AET表都为空为止：
① 如果ET中yj桶非空,则将yj桶中的全部记录合并到AET中。
② 对AET链中的记录按x的大小从小到大排序。
③ 依次取出AET各记录中的xi坐标值,两两配对,对每对xi之间的象素填上所要求的颜色。
④ 如果AET中某记录的ymax=yj,则删除该记录。
⑤ 对于仍留在AET中的每个记录,用xi+1/m代替xi,这就是该记录边线与下一条扫描线yj+1的交点。
⑥ 使yj加1,以便进入下一轮循环。
边相关多边形扫描线填充为伪代码 #include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5)) /*求舍入的宏*/
struct edge{ /*边记录结构*/
int ymax;
float xi;
float m;
struct edge *next;
};
void poly_fill(int,int *,int);
void main()
{
int polypoints[]={ /*多边形顶点坐标: x0,y0,x1,y1,... */
100,300, 200,200, 300,200, 300,350,
400,250, 450,300, 300,50, 100,150};
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,);
poly_fill(8,polypoints,4); /*用红色填充*/
getch();
closegraph();
}
/*将一条边记录插入边记录构成的链表的表头*/
void insert_et(struct edge *anedge,struct edge **p_edges)
{
struct edge *p;
p=*p_edges;
*p_edges=anedge;
anedge->next=p;
}
/*复制一条边记录插入有效边表,维持有效边表的有序性*/
short insert_aet(struct edge *p,struct edge **p_aet)
{
struct edge *q,*k,*l;
if(!(q=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN INSERTING EDGE RECORD TO AET );
return(0);
}
q->ymax=p->ymax; q->xi=p->xi;
q->m=p->m; q->next=NULL;
if(!(*p_aet)||((*p_aet)->xi>q->xi)||(((*p_aet)->xi==q->xi)&&((*p_aet)->m>q->m)))
{
l=*p_aet; *p_aet=q; q->next=l;
}
else
{
l=*p_aet;
k=l->next;
while(k&&(k->xi<q->xi))
{
l=k;
k=k->next;
}
if(k&&(k->xi==q->xi)&&(k->m<q->m))
{
l=k;
k=k->next;
}
l->next=q;
q->next=k;
}
return(1);
}
/*从（x1,y）到（x2,y）用color色绘水平直线*/
void draw_line(int x1,int x2,int y,int color)
{
int i;
y=getmaxy()-y; /*进行坐标变换*/
for(i=x1;i<=x2;i++)putpixel(i,y,color);
}
/*多边形扫描线填充:
numpoint是多边形顶点个数；
points存放多边形顶点坐标（x0,y0,x1,y1,...);
color是填充色*/
void poly_fill(int numpoint,int *points,int color)
{
struct edge **et=NULL,*aet,*anedge,*p,*q;
int i,j,maxy,miny,x1,y1,x2,y2,yi,znum;
maxy=miny=points[1];
znum=2*numpoint;
for(i=3;i<znum;i++)
{
if(maxy<points[i]) maxy=points[i];
else if(miny>points[i])miny=points[i];
i++;
}
if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *))))
{ /*建立边表ET */
printf( OUT MEMORY IN CONSTRUCTING ET );
return;
}
for(i=0;i<maxy-miny+1;i++) et[i]=NULL;
x1=points[znum-2]; y1=points[znum-1];
for(i=0;i<znum;i+=2)
{ /*处理多边形所有边,为每条非水平边建立一个边记录,并将其插到ET表中的合适位置 */
x2=points[i]; y2=points[i+1];
if(y1!=y2) /*只考虑非水平边*/
{
if(!(anedge=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN CONSTRUCTING EDGE RECORD. );
goto quit;
}
anedge->m=(float)(x2-x1)/(y2-y1);
anedge->next=NULL;
if(y2>y1) /*处理奇异点*/
{
j=i+1;
do{ /*向后划过所有水平边*/
if((j+=2)>=znum)j-=znum;
}while(points[j]==y2);
if(points[j]>y2) anedge->ymax=y2-1;
/*若(x2,y2)不是局部极值点,边记录的ymax域为y2-1,这样处理
扫描线y=y2时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y2; /*若(x2,y2)是局部极值点,边记录的ymax域为y2,
这样处理扫描线y=y2时此边记录将在AET中,从而会产生一个交点 */
anedge->xi=x1;
insert_et(anedge,&et[y1-miny]);
}
else
{
j=i+1; /*向前划过所有水平边*/
do{
if((j-=2)<0)j+=znum;
}while(points[j]==y1);
if(points[j]>y1) anedge->ymax=y1-1;
/*若(x1,y1)不是局部极值点,边记录的ymax域为y1-1,这样处理
扫描线y=y1时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y1; /*若(x1,y1)是局部极值点,边记录的ymax
域为y1,这样处理扫描线y=y1时此边记
录将在AET中,从而会产生一个交点 */
anedge->xi=x2;
insert_et(anedge,&et[y2-miny]);
}
}
x1=x2;
y1=y2;
}
aet=NULL; /*初始化有效边表AET*/
for(yi=miny;yi<=maxy;yi++) /*从低到高逐条处理扫描线*/
{ /*将ET表中与yi对应的边记录链表中的全部边记录
p=et[yi-miny]; 都按序并入AET中*/
while(p)
{
if(!insert_aet(p,&aet)) goto quit;
p=p->next;
}
p=aet;
while(p) /*依次取出AET各记录中的xi坐标值,两两配对,*/
{/*对每对xi之间的象素填上所要求的颜色*/
draw_line(round(p->xi),round(p->next->xi),yi,color);
p=p->next->next;
}
p=aet;
while(p&&(p->ymax==yi)) /*对AET中的每个记录,若它的ymax==yi, */
{/*则删除该记录,否则用xi+1/m代替xi,这就是该记录所对应的*/
aet=p->next; /*边线与下一条扫描线y=yi+1的交点 */
free(p);
p=aet;
}
while(p)
{
if(p->ymax==yi)
{
q->next=p->next;
free(p);
p=q->next;
}
else
{
p->xi+=p->m;
q=p;
p=p->next;
}
}
}
quit:
if(et) /*释放动态申请的内存*/
{
for(yi=miny;yi<=maxy;yi++)
{
q=p=et[yi-miny];
while(p)
{
q=p->next;
free(p);
p=q;
}
}
free(et);
}
} 边标志填充算法思想
扫描线具有连贯性,这种连贯性只有在扫描线与多边形相交处才会发生变化,而每次的变化结果：无非是在前景色和背景色之间相互“切换”。
边标志填充算法正是基于这一发现,先在屏幕上生成多边形轮廓线,然后逐条扫描线处理。处理中：逐点读取象素值,若为边界色,则对该象素值进行颜色切换。
边标志填充算法步骤 1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。
2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。
3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。
边标志填充算法伪代码 EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor)
{
int i,x,y,flag,xmin,xmax,ymin,ymax;
setcolor(boundarycolor); /*设置画笔色*/
for(i=0 ;i<n;i++)/*画出多边形的n条边*/
line(p[i][0], p[i][1], p[(i+1)%n][0], p[(i+1)%n][1]);
/*用求极值的算法,从多边形顶点数组p中,求出xmin,xmax,ymin,ymax*/
for(y=ymin;y<=ymax;y++)
{
flag=－1;
for(x=xmin;x<=xmax;x++)
{
if(getpixel(x,y)= = boundarycolor) flag=－flag;
if(flag= =1)putpixel(x,y, newcolor);
}
}
}