扫描线填充算法基本步骤

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

扫描线种子填充算法思想
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
扫描线种子填充算法步骤 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);
}
}
}

B. 填充算法的概述

填充算法是计算机算法的一种分类，是一个将指定不规则区域内部像素填充为填充色的过程，在计算机辅助设计和图像处理等领域有广泛应用。包括了注入填充区域算法、种子填充算法、扫描线填充算法、边填充算法等。

C. 微软操作系统：自带的画图工具填充是用什么算法实现的

基于扫描线的洪水填充算法
洪水填充算法 慢在需要检查周边4个点，而如果带上方向，则刚处理过的点是不需要再判断的了
如果维持算法的一致，那么步长可以增加到 3

如果采用多线程处理，则每个线程只处理一根扫描线，且只检查前进方向的一个点

D. 栅格化的基本实现方法

最基础的栅格化算法将多边形表示的三维场景渲染到二维表面。多边形由三角形的集合表示，三角形由三维空间中的三个顶点表示。在最简单的实现形式中，栅格化工具将顶点数据映射到观察者显示器上对应的二维坐标点，然后对变换出的二维三角形进行合适的填充。 一旦三角形顶点转换到正确的二维位置之后，这些位置可能位于观察窗口之外，也可能位于屏幕之内。裁剪就是对三角形进行处理以适合显示区域的过程。
最常用的技术是Sutherland-Hodgeman裁剪算法。在这种方法中，每次测试每个图像平面的四条边，对于每个边测试每个待渲染的点。如果该点位于边界之外，就剔除该点。对于与图像平的面边相交的三角形边，即边的一个顶点位于图像内部一个位于外部，那么就在交叉点插入一个点并且移除外部的点。 传统的栅格化过程的最后一步就是填充图像平面中的二维三角形，这个过程就是扫描变换。
第一个需要考虑的问题就是是否需要绘制给定的像素。一个需要渲染的像素必须位于三角形内部、必须未被裁掉，并且必须未被其它像素遮挡。有许多算法可以用于在三角形内进行填充，其中最流行的方法是扫描线算法。
由于很难确定栅格化引擎是否会从前到后绘制所有像素，因此必须要有一些方法来确保离观察者较近的像素不会被较远的像素所覆盖。最为常用的一种方法是深度缓存，深度缓存是一个与图像平面对应的保存每个像素深度的二维数组。每个像素进行绘制的时候都要更新深度缓存中的深度值，每个新像素在绘制之前都要检查深度缓存中的深度值，距离观察者较近的像素就会绘制，而距离较远的都被舍弃。
为了确定像素颜色，需要进行纹理或者浓淡效果计算。纹理图是用于定义三角形显示外观的位图。每个三角形顶点除了位置坐标之外都与纹理以及二维纹理坐标 (u,v) 发生关联。每次渲染三角形中的像素的时候，都必须在纹理中找到对应的纹素，这是根据在屏幕上像素与顶点的距离在与纹理坐标相关联的三角形顶点之间插值完成的。在透视投影中，插值是在根据顶点深度分开的纹理坐标上进行的，这样做就可以避免透视缩减（perspective foreshortening）问题。
在确定像素最终颜色之前，必须根据场景中的所有光源计算像素上的光照。在场景中通常有三种类型的光源。定向光是在场景中按照一个固定方向传输并且强度保持不变的光。在现实生活中，由于太阳距离遥远所以在地球上的观察者看来是平行光线并且其衰减微乎其微，所以太阳光可以看作是定向光。点光源是从空间中明确位置向所有方向发射光线的光源。在远距离的物体上的入射光线会有衰减。最后一种是聚光灯，如同现实生活中的聚光灯一样，它有一个明确的空间位置、方向以及光锥的角度。另外，经常在光照计算完成之后添加一个环境光值以补偿光栅化无法正确计算的全局照明效果。
有许多可以用于光栅化的浓淡算法。所有的浓淡处理算法都必须考虑与光源的距离以及遮蔽物体法向量与光照入射角。最快的算法让三角形中的所有像素使用同样的亮度，但是这种方法无法生成平滑效果的表面。另外也可以单独计算顶点的亮度，然后绘制内部像素的时候对顶点亮度进行插值。速度最慢也最为真实的实现方法是单独计算每点的亮度。常用的浓淡模型有 Gouraud shading 和 Phong shading。

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

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

F. 简单扫描线性填充和与边相关扫描线填充算法的区别

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

G. 如何实现用计算机图形学的编码完成给一个矩形上色

您好，第一章
1. 计算机图形：用数学方法描述，通过计算机生成、处理、存储和显示的对象。
2. 图形和图像的主要区别是表示方法不同：图形是用矢量表示；图像是用点阵表示的。图形和图像也可以通过光栅显示器（或经过识别处理）可相互转化。
3. 于计算机图形学紧密相关的学科主要包括 图像处理、计算几何和计算机视觉模式识别。它们的共同点是 以图形/图像在计算机中的表示方法为基础。
4. 交互式计算机图形系统的发展可概括为以下4个阶段：字符、矢量、二维光栅图形、三维图形。
5. 图形学研究的主要内容有：①几何造型技术 ②图形生成技术 ③图形处理技术 ④图形信息的存储、检索与交换技术 ⑤人机交互技术 ⑥动画技术 ⑦图形输入输出技术 ⑧图形标准与图形软件包的研发。
6. 计算机辅助设计和计算机辅助制造 是计算机图形学最广泛最活跃的应用领域。
7. 计算机图形学的基本任务：一是如何利用计算机硬件来实现图形处理功能；二是如何利用好的图形软件；三是如何利用数学方法及算法解决实际应用中的图行处理问题。
8. 计算机图形系统是由硬件系统和软件系统组成的。
9. 计算机图形系统包括处理、存储、交互、输入和输出五种基本功能。
10. 键盘和鼠标是最常用的图形输入设备。鼠标根据测量位移部件的不同，分为光电式、光机式和机械式3种。
11. 数字化仪分为电子式、超声波式、磁伸缩式、电磁感应式等。小型的数字化仪也称为图形输入板。
12. 触摸屏是一种 定位设备，它是一种对于触摸能产生反应的屏幕。
13. 扫描仪由3部分组成：扫描头、控制电路和移动扫描机构。扫描头由光源发射和光鲜接收组成。按移动机构的不同，扫描仪可分为平板式和滚筒式2种。
14. 显示器是计算机的标准输出设备。彩色CRT的显示技术有2种：电子穿透法和荫罩法。
15. 随机扫描是指电子束的定位及偏转具有随意性，电子束根据需要可以在荧光屏任意方向上连续扫描，没有固定扫描线和扫描顺序限制。它具有局部修改性和动态性能。
16. 光栅扫描显示器是画点设备。
17. 点距是指相邻像素点间的距离，与分辨指标相关。
18. 等离子显示器一般有三层玻璃板组成，通常称为等离子显示器的三层结构。
19. 用以输出图形的计算机外部设备称为硬拷贝设备。
20. 打印机是廉价的硬拷贝设备，从机械动作上常为撞击式和非撞击式2种。
21. 常用的喷墨头有：压电式、气泡式、静电式、固体式。
22. 绘图仪分为静电绘图仪和笔式绘图仪。
23. 图形软件的分层。由下到上分别是：①图形设备指令、命令集、计算机操作系统 ②零级图形软件 ③一级图形软件 ④二级图形软件 ⑤三级图形软件。
24. 零级图形软件是面向系统的、最底层的软件，主要解决图形设备与主机的通信与接口问题，又称设备驱动程序。
25. 一级图形软件即面向系统又面向用户，又称基本子系统。
26. 图形应用软件是系统的核心部分。
27. 从物理学角度，颜色以主波长、色纯度和辉度来描述；从视觉角度来看，颜色以色彩、饱和度和亮度来描述。
28. 用适当比列的3种颜色混合，可以获得白色，而且这3种颜色中的任意2种的组合都不能生成第三种颜色，称为三原色理论。
29. RGB模型的匹配表达式是：c=rR+gG+bB。
30. 常用颜色模型
颜色模型名称 使用范围
RGB 图形显示设备（彩色CRT和光栅显示器）
CMY 图形打印、绘制设备
HSV 对应画家本色原理、直观的颜色描述
HSL 基于颜色参数的模型
用基色青、品红、黄定义的CMY颜色模型用来描述硬拷贝设备的输出颜色。它从白光中滤去某种颜色，故称为减色性原色系统。

第二章
31. 直线生成的3个常用算法：数值微分法（DDA）、中点划线法和Bresenham算法。
32. DDA算法的C语言实现：
DDA算法生成直线，起点（x0,y0）,终点（x1,y1）.
Void CMy View ::OnDdaline()
{
CDC *pDC=GetDC(); //获得设备指针
int x0=100,y0=100,x1=300,y1=200,c=RGB(250,0,0);//定义直线两端点和直线颜色
int x,y,i;
float dx,dy,k;
dx=(float)(x1-x0);
dy=(float)(y1-y0);
k=dy/dx;
x=x0;
y=y0;
if(abs(k)<1)
{ for(;x<=x1;x++)
{pDC—>SetPixel(x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{ for(;y<=y1;y++)
{pDC—>SetPixel(int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC); //释放设备指针
}
33. 任何影响图元显示方法的参数称为属性参数。图元的基本表现是线段，其基本属性包括线型、线宽和色彩。
34. 最常见的线型包括实线、虚线、细线和点划线等，通常默认的线型是实线。
35. 线宽控制的实线方法：垂直线刷子、水平线刷子、方形线刷子。生成具有宽度的线条还可以采用区域填充算法。
36. 用离散量表示连续量时引起的失真现象称为走样。为了提高图形显示质量，减少或消除走样现象的技术称为反走样。
37. 反走样技术有：提高分辨率（硬件方法和软件方法）、简单区域取样、加权区域取样。
38. 区域连通情况分为四连通区域和八连通区域。四连通区域是指从区域上某一点出发，可通过上下左右4个方向移动，在不越出区域的前提下到达区域内的任意像素；八连通区域是指从区域内某一像素出发，可通过上下左右、左上左下、右上右下8个方向的移动，在不越出区域的前提下到达区域内的任意像素。
39. 字符的图形表示可以分为点阵式和矢量式两种形式。
40. 在图形软件中，除了要求能生成直线、圆等基本图形元素外，还要求能生成其他曲线图元、多边形及符号等多种图元。
41. 在扫描线填充算法中，对水平边忽略而不予处理的原因是实际处理时不计其交点。
42. 关于直线生成算法的叙述中，正确的是：Bresenham算法是对中点画线算法的改进。
43. 在中点画圆算法中叙述错误的是：为了减轻画圆的工作量，中点画圆利用了圆的四对称性性质。
44. 多边形填充时，下列论述错误的是：在判断点是否在多边形内时，一般通过在多变形外找一点，然后根据该线段与多边形的交点数目为偶数即可认为在多边形内部，若为奇数则在多边形外部，且不考虑任何特殊情况。
第三章
1. Cohen-Sutherland算法，也称编码裁剪法。其基本思想是：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段，简称“取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；③若线段既不满足“取”的条件也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段 完全在窗口外，可舍弃之，然后对另一段重复上述处理。
2. Sutherland-Hodgman算法，又称逐边裁剪算法。其基本思想是用窗口的四条边所在的直线依次来裁剪多边形。多边形的每条边与裁剪线的位置关系有4种情况（假设当前处理的多边形的边为SP）：a>端点S在外侧，P在内侧，则从外到内输出P和I；b>端点S和P都在内侧，则从内到内输出P；c>端点S在内侧，而P在外侧，则从内到外输出I；d>端点S和P都在外侧，无输出。
3. 按裁剪精度的不同，字符裁剪可分为三种情况：字符串裁剪、字符裁剪和笔画裁剪。
4. 在线段AB的编码裁剪算法中，如A、B两点的码逻辑或运算全为0，则该线段位于窗口内；如AB两点的码逻辑与运算结果不为0，则该线段在窗口外。
5. n边多边形关于矩形窗口进行裁剪，结果多边形最多有2n个顶点，最少有n个顶点。
6. 对一条等长的直线段裁剪，编码裁剪算法的速度和中点分割算法的裁剪速度哪一个快，无法确定。（√）
7. 多边形裁剪可以看做是线段裁剪的组合。（X）
8. 对于线段来说，中点分割算法要比其他线段裁剪算法的裁剪速度快。（X）
9. 多边形的Weiler-Atherton裁剪算法可以实现对任意多边形的裁剪。（√）
第四章
1. 几何变换是指改变几何形状和位置，非几何变换是指改变图形的颜色、线型等属性。变换方法有对象变换（坐标系不动）和坐标变换（坐标系变化）两种。
2. 坐标系可以分为以下几种：世界坐标系（是对计算机图形场景中所有图形对象的空间定位和定义，是其他坐标系的参照）、模型坐标系（用于设计物体的局部坐标系）、用户坐标系(为了方便交互绘图操作，可以变换角度、方向)、设备坐标系（是绘制或输出图形的设备所用的坐标系，采用左手系统）。
3. 将用户坐标系中需要进行观察和处理的一个坐标区域称为窗口，将窗口映射到显示设备上的坐标区域称为视区。从窗口到视区的变换，称为规格化变换。（eg.4-1）
4. 所谓体素，是指可以用有限个尺寸参数定位和定形的体，如长方体、圆锥体。
5. 所谓齐次坐标表示，就是用n+1维向量表示n维的向量。
6. 二维点（x,y）的齐次坐标可以表示为：（hx hy h）,其中h≠0。当h=1时称为规范化的齐次坐标，它能保证点集表示的唯一性。
7. 旋转变换公式的推导、对称变换

第五章
1. 交互绘图技术是一种处理用户输入图形数据的技术，是设计交互绘图系统的基础。常见的交互绘图技术有：定位技术、橡皮筋技术、拖曳技术、定值技术、拾取技术、网格与吸附技术。
2. 常用的橡皮筋技术有：橡皮筋直线、橡皮筋矩形、橡皮筋圆。
3. 拖曳技术是将形体在空间移动的过程动态地、连续地表示出来，直到用户满意。
4. 定值技术有2种：一种是键入数值，另一种是改变电位计阻值产生要求的数量，可以用模拟的方式实现电位计功能。
5. 拾取一个基本的对象可以通过：指定名称法、特征点发、外界矩阵法、分类法、直接法。

第六章
1. 点、线、面是形成三维图形的基础，三维变换是从点开始。
2. 三维图形变换分类：三维图形变换包括三维几何变换和平面几何变换，三维几何变换包括基本几何变换和复合变换；平面几何变换包括平行投影和透视投影，平行投影包括正投影和轴测投影，透视投影包括一点透视、二点透视、三点透视。
3. 投影中心与投影面之间的距离是无限的投影叫做平行投影，它包括正投影和轴测投影。
4. 正投影形成的视图包括：主视图、俯视图和左视图。轴测投影形成的视图为轴测图。
5. 透视投影也称为中心投影，其投影中心与投影面之间的距离是有限的。其特点是产生近大远小的视觉效果
6. 对于透视投影，不平行于投影面的平行线的投影会汇聚到一个点，这个点称为灭点。透视投影的灭点有无限多个，与坐标轴平行的平行线在投影面上形成的灭点称为主灭点。主灭点最多有3个，其对应的透视投影分别称为一点透视、二点透视、三点透视。

第七章
1. 型值点是曲面或曲线上的点，而控制点不一定在曲线曲面上，控制点的主要目的是用来控制曲线曲面的形状。
2. 插值和逼近是曲线曲面设计中的两种不同方法。插值—生成的曲线曲面经过每一个型值点，逼近—生成的曲线曲面靠近每一个控制点。
3. 曲线曲面的表示要求：唯一性、统一性、几何不变性、几何直观、易于界定、易于光滑连接。
4. 曲线曲面有参数和非参数表示，但参数表示较好。非参数表示又分为显式和隐式两种。
5. 对于一个平面曲线，显式表示的一般形式是：y=f(x)。一个x与一个y对应，因此显式方程不能表示封闭或多值曲线。例不能用显式方程表示一个圆。
6. 如果一个曲线方程表示为f(x,y)=0的形式，我们称之为隐式表示。其优点是易于判断函数f(x,y)是否大于、小于或等于零，即易于判断是落在所表示曲线上还是在曲线的哪一侧。
7. 参数连续与几何连续的区别：参数连续性是传统意义上的、严格的连续，而几何连续性只需限定两个曲线段在交点处的参数导数成比例，不必完全相等，是一种更直观、易于交互控制的连续性。
8. 在曲线曲面造型中，一般只用到C1（1阶参数连续）、C2（2阶参数连续）、G1（1阶几何连续）、G2（2阶几何连续）。切矢量（一阶导数）反映了曲线对参数t的变化速递，曲率（二阶导数）反映了曲线对参数t变化的加速度。
9. 通常C1连续必能保证G1的连续，但G1的连续并不能保证C1连续。
10. 对于三次Hermite曲线，用于描述曲线的可供选择的条件有：端点坐标、切矢量和曲率。
11. 三次Hermite曲线特点：①可局部调整，因为每个曲线段仅依赖于端点约束；②基于Hermite样条的变化形式有Cardinal样条和Kochanek-Bartels样条；③具有几何不变性。
12. Bezier曲线的性质：①端点性质②端点切矢量③端点的曲率④对称性⑤几何不变性⑥凸包性⑦变差缩减性。
13. 一次Bezier曲线是连接起点P0和终点P1的直线段，二次Bezier曲线对应一条起点P0终点在P2处的抛物线。
14. B样条曲线的性质：①局部性②连续性或可微性③几何不变性④严格凸包性⑤近似性⑥变差缩减性。
15. NURRS曲线具有以下性质：①局部性②可微性③仿射不变性④严格保凸性⑤一般性⑥变差缩减性⑦端点性质。

第八章
1. 要把三维物体的信息显示在二维显示设备中，必须通过投影变换。由于投影变换失去了深度信息，往往会导致二义性，要消除二义性，就必须在绘制时消除实际不可见的线和面，称作消除隐藏线和隐藏面，简称消隐。
2. 面消隐常用算法有：深度缓冲区（Z-buffer）算法和深度排序算法（画家算法）。
3. 深度缓冲区算法和深度排序算法的区别：

H. web填充怎么设置

web填充设置：单击上面工具栏中的“设计”按钮。下一步点击“页面颜色”按钮。单击颜色下拉菜单中的填充效果按钮。点击填充效果屏幕上的“图片”按钮。点击屏幕上的”选择图像”按钮。

<Meta http-equiv="Page-Enter" Content="blendTrans(Duration=0.5)">，<Meta http-equiv="Page-Exit" Content="blendTrans(Duration=0.5)">。

blendTrans其实就是一种动态滤镜效果，当然还有其他的方法也可以产生这种动态滤镜效果，<Meta http-equiv="Page-Enter" Content="revealTrans(ration=x, transition=y)">。

边标志填充算法步骤：

1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。

2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。

3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。

I. 多边形扫描线填充算法

如果是用线填充，程序如下。如果是用点填充需要用到堆栈和系统底层库函数或者用画点函数putpixel()。
下面实例是用扫描线填充长方形，开始要输入长方形的左上顶点坐标和右下顶点坐标以及填充扫描线的间距(>=1)，如果间距等于1，就是完全填充(实填充)。
一个完整的c程序如下,程序在win-tc和tc2.0下都调试通过。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<graphics.h>

void draw(int x1,int y1,int x2,int y2,int delta)
{int nx1,ny1,nx2,ny2; <br/>nx1=x1,ny1=y2-delta,nx2=x1+delta,ny2=y2; <br/>while((ny1>=y1)&&(nx2<=x2)) <br/>{line(nx1,ny1,nx2,ny2); <br/>ny1-=delta; <br/>nx2+=delta; <br/>}
if(nx2>x2)
{ny2-=nx2-x2; <br/>nx2=x2; <br/>while(ny1>y1) <br/>{line(nx1,ny1,nx2,ny2); <br/>ny1-=delta; <br/>ny2-=delta; <br/>}
nx1+=y1-ny1;
ny1=y1;
while(nx1<x2)
{line(nx1,ny1,nx2,ny2); <br/>nx1+=delta; <br/>ny2-=delta; <br/>}
}
else
{nx1+=y1-ny1; <br/>ny1=y1; <br/>while(nx2<x2) <br/>{line(nx1,ny1,nx2,ny2); <br/>nx2+=delta; <br/>nx1+=delta; <br/>}
ny2-=nx2-x2;
nx2=x2;
while(ny2>y1)
{line(nx1,ny1,nx2,ny2); <br/>ny2-=delta; <br/>nx1+=delta; <br/>}
}
}

int main(void)
{int x1,y1,y2,x2,delta; <br/>int driver=DETECT,mode; <br/>printf("Please input lefttop(x1,y1) and rightbottom(x2,y2) of rectangle and delta:\n"); <br/>scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); <br/>initgraph (&driver,&mode,"C:\\TC"); /*这里*/<br/>rectangle(x1,y1,x2,y2); <br/>draw(x1,y1,x2,y2,delta); <br/>gotoxy(1,1); <br/>printf("Press any key to exit!"); <br/>getch(); <br/>closegraph(); <br/>return 0; <br/>}

说明：将main()函数中的initgraph(&gdriver,&gmode,"");中的""更改为你的TC安装目录,一般tc必须安装在c盘根目录下，所以就是initgraph(&gdriver,&gmode,"C:\\TC");如你的TC安装目录为D盘的Tools目录下的TC目录，那么上述语句改为：
initgraph(&gdriver,&gmode,"D:\\Tools\\TC");
同时保证在D:\\Tools\\TC目录里有文件EGAVGA.BGI,万一不行，将本程序复制到你的TC安装目录下再运行。

J. 扫描线填充算法与种子填充算法的区别是什么

种子优点是非常简单，缺点是需要大量栈空间来存储相邻的点。

改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。