掃描線填充演算法基本步驟

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. 掃描線填充演算法與種子填充演算法的區別是什麼

種子優點是非常簡單，缺點是需要大量棧空間來存儲相鄰的點。

改進的方法就是：通過沿掃描線填充水平像素段，來處理四連通或八連通相鄰點，這樣就僅僅只需要將每個水平像素段的起始位置壓入棧，而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節省大量的棧空間。