计算机图形学试验参考指导书v.doc

计算机科学和技术学院

《计算机图形学》

试验指导书

陈笑威 张健 编写

适用专业 计算机科学

贵州大学
二OO 七年八月

前 言
计算机图形学是计算机学科最活跃分支之一，也是计算机专业必修课程之一。
计算机图形学是一门实践性很强学科，其内容改变也是日新月异。
本指导书包含了光栅图形学、几何造型、真实感图形学三部分内容，对各部分内容中经典算法有具体算法原理介绍及算法描述。经过本指导书，读者能够快速地掌握计算机图形学中经典算法应用及实现原理。在此基础之上，能够愈加好了解计算机图形学研究前沿。

目 录
试验一 直线生成算法 3
数值微分法 (DDA-Digital Differential Analyzer) 4
中点画线法 4
Bresenham画线算法 6
试验二 圆生成算法 7
生成园弧中点算法 8
Bresendham 画园算法 12
试验三 椭园生成算法 15
中点算法 16
试验四 多边形填充算法 19
扫描线算法 20
边填充算法-正负相消法 21
边标志算法（轮廓填充算法） 21
种子填充算法 22
区域填充(种子填充法) 22
扫描线种子算法 23
试验五 常见曲面和曲线生成算法 24
三次Hermite曲线生成: 25
Bezier曲线(以迫近为基础参数曲线): 26
B样条曲线: 27
试验六 二维图形几何变换 30
标准齐次坐标(x,y,1) 二维变换矩阵表示 32
试验七 淘汰及消隐 36
直线淘汰 37
多边形淘汰 43
Roberts消隐算法 45
Z缓冲器算法 51
扫描线Z缓冲器算法 53
光线跟踪算法 53
试验八 曲线和曲面算法应用/实体造型？ 56
试验九 真实感图形生成 57
简单光照模型 58
Gouraud明暗处理 59
Phong明暗处理 60
利用光照模型光线跟踪算法 62
试验汇报基础内容及要求 65
附件1：试验汇报格式 66
试验一 直线生成算法
试验课时：4
试验类型：（验证、综合、设计）
试验要求：必修
一、试验目标
经过本试验，使学生了解并掌握在光栅显示系统中直线生成和显示算法，熟悉相关开发平台。为后继试验打下基础。
二、试验内容
实现DDA画线算法，中点画线算法和Bresenham画线算法，并比较。
三、试验原理、方法和手段
参见本指导书。
四、试验组织运行要求
以学生自主训练为主开放模式组织教学。
五、试验条件
硬件平台：PC
软件(推荐)：Windows平台，Visual C++，matlab
六、试验步骤
1. 掌握算法原理；
2. 依据算法，编写源程序并进行调试；
3. 对运行结果进行保留和分析；
4. 把源程序以文件形式提交；
5. 按格式书写试验汇报。
七、思索题
八、试验汇报
关键包含试验预习、试验统计和试验汇报三部分，基础内容详见附件1。
数值微分法 (DDA-Digital Differential Analyzer)
yi
xi
yi+1
xi+1
算法原理：
设直线两端点为:P1(x1,y1)及 P0(x0,y0),
则直线斜率为：

直线方程为：

当 |k|<=1，x每增加1，y 最多增加1(或增加小于1)。

当 |k|>1 ,y每增加1,x 最多增加1 (或增加小于1) 。

算法分析：
复杂度：加法+取整
优点：避免了y=kx+b 方程中浮点乘法,比直接用点斜式画线快。
缺点：需浮点数加法及取整运算,不利于硬件实现。
x
Pi=(xi, yi)
M
Q
P1
p2
y

中点画线法
算法原理：
设0<k<1
中点M在直线下方，下一点取p1点；
中点M在直线上方取p2点。

y
x
F(x,y)=0
F(x,y)>0
F(x,y)<0
(x1,y1)
(x0,y0)
中点算法用整数加法及比较替换了DDA中浮点数加法及取整运算,效率大大提升。
假设直线起点、终点分别为：（X0,Y0),(X1,Y1)，直线将二维空间划分为三个区域:
直线方程: F(x,y)=ax+by+c=0
其中: a=-(y1-y0)，b=(x1-x0)，c=-B(x1-x0)
如F(x,y)=0, 则(x,y) 在直线上
如F(x,y)<0, 则(x,y)在直线下方
如F(x,y)>0, 则(x,y)在直线上方
所以，可将中点M坐标(Xp+1,Yp+0.5)代入直线方程，并判定其符号即可确定象素点选择。
定义决议变量: d= F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c
假如 d>0,则M在理想直线上方,选正右方P2点；
假如 d<0,则M在理想直线下方,选右上方P1点；
假如 d=0,则M在理想直线上,选P1/ P2点。

因为d是xi和yi线性函数，可采取增量计算提升运算效率。
1.如由pi点确定在是正右方P2点(d>0).，则新中点M仅在x方向加1,新d值为:
dnew=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c
而 dold=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c
dnew=dold+a= dold-dy
2.如由pi点确定是右上方P1点(d<0)，则新中点M在x和y方向全部增加1,新d值为
dnew=F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c
而 dold=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c
dnew=dold+a+b= dold-dy+dx
在每一步中,依据前一次第二迭中计算出d值符号,在正右方和右上方两个点中进行选择。
d初始值: d0=F(x0+1,y0+0.5)=F(x0,y0)+a+b/2=a+b/2=-dy+dx/2
F(x0,y0)=0，(x0,y0)在直线上。
为了消除d分数,重新定义 F(x,y)=2(ax+by+c)
则每一步需要计算dnew 是简单整数加法
dy=y1-y0，dx=x1-x0
d0=-2dy+dx
dnew=dold-2*dy，当 dold>=0
dnew=dold-2(dy-dx)，当dold<0
Bresenham画线算法
算法原理：
和DDA算法相同，Bresenham画线算法也要在每列象素中找到和理想直线最迫近象素点。
依据直线斜率来确定变量在x或y方向递增一个单位。另一个方向y或x增量为0或1，它取决于实际直线和最靠近网格点位置距离。这一距离称为误差。算法巧妙构思，使每次只需检验误差项（增量）符号即可。
定义决议变量：d =d+k (0<k<1)
设0<k<1，如直线上一点为（x,y）,则下一点为:（x+1,y） (d<0.5) 或（x+1,y+1）(d>=0.5)
当d>1时,让d=d-1,以确保0<=d<1，d0=0
令e =d-0.5 (0<k<1)，则e0 = -0.5
则下一点为:
（x+1,y），(e<0)
（x+1,y+1）(e>=0)
当e >0时, 让e =e-1，(重新初始化误差项)
因为算法只用到误差项符号,为了改用整数以避免去法,能够作以下替换:
e = 2*e*dx
定义决议变量 e = 2*e*dx，则e0 = -dx，e=e +2*dy
则下一点为:
（x+1,y），(e <0)
（x+1,y+1）(e >=0)
当e >0时, 让 e =e -dx, (重新初始化误差项)
试验二 圆生成算法
试验课时：4
试验类型：（验证、综合、设计）
试验要求：必修
一、试验目标
经过本试验，使学生了解并掌握在光栅显示系统中园生成和显示算法，深入熟悉相关开发平台。
二、试验内容
实现中点画园算法、二阶差分算法、及Bresendham画园算法，并比较各算法。
三、试验原理、方法和手段
参见本指导书
四、试验组织运行要求
以学生自主训练为主开放模式组织教学。
五、试验条件：
硬件平台：PC
软件(推荐)：Windows平台，Visual C++，matlab
六、试验步骤
1. 掌握算法原理；
2. 依据算法，编写源程序并进行调试；
3. 对运行结果进行保留和分析；
4. 把源程序以文件形式提交；
5. 按格式书写试验汇报。
七、思索题
八、试验汇报
关键包含试验预习、试验统计和试验汇报三部分，基础内容详见附件1。
生成园弧中点算法
F(x,y)>0
F(x,y)<0
F(x,y)=0
算法原理：
画出第二个八分园（45°-90°），利用八对称性画出其它八分园。
1.用中点算法画第二个八分园。
从目前已取得象素递推出下一个象素。
园弧隐函数形式为
F(x,y)=x2+y2-R2=0
则园弧正负划分性为：
F(x,y)>0，(x,y)在园外；
F(x,y)<0，(x,y)在园内；
F(x,y)=0，(x,y)在园上。
xi，yi
M
E
SE
设(xi,yi)为已确定象素坐标，则下一个象素只能是正右方E点或右下方SE点。
设M是E和SE中点，则M=(xi+1,yi-0.5)：
如F(M)<0，则M在园内，说明E距离圆弧更近,下一点取正右方E点；
如F(M)>0，则M在园外，说明SE距离圆弧更近,下一点取右下方SE点；
如F(M)=0，则M在园上，下一点取E点或SE点。

结构判别式：d=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2
（1）d<0，中点在圆内,选正右方E点,再下一个象素判别式为：
dnew=F(xi+2,yi-0.5) =(xi+2)2+(yi-0.5)2-R2=d+(2xi+3)
沿正右方向,d增量为：
(2) d>=0,中点在圆外,选右下方SE点,再下一个象素判别式为：
dnew=F(xi+2,yi-1.5) =(xi+2)2+(yi-1.5)2-R2=d+(2xi+3)+(- yi+2)
=d+2(xi-yi)+5
沿右下方向,d增量为：
（3）d初始值为：d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R
在d运算中包含了浮点数运算，为了消除d中浮点数运算，分析上述算法，能够看出，算法中取作用只是d符号，所以可设另一整数变量h：h=d-0.25
所以：初始化运算d0 = 1.25–R 对应于:h0=1-R
判别式 d<0 对应于 h<-0.25
又因为：h初值h0为整数，运算过程中分量也为整数(∆E和∆SE为整数)，故h一直为整数。所以可用h替换d作判定。
其初始值：h0=d0-0.25=(1.25-R)-0.25=1-R
有以下对应关系：
h<0 d<0
h>0 d>0
h=0 d=0

例：用中点算法画一R=5园
d0=1-R=1-5=-4<0 M在园内，取E点(1,5)；
d1=d0+(2xi+3)=-4+(2*0+3)=-1<0，M在园内，取E点(2,5)；
d2=d1+(2xi+3)=-1+(2*1+3)=4>0，M在园外，取SE点(3,4)；
d3=d2+2*(xi-yi)+5=4+2*(2-5)+5=3>0，M在园外,取SE点(4,3)；
d4=d3 +2*(xi-yi)+5=3+2*(3-4)+5=6>0，M在园外,取SE点(5,2)；
y<x，stop。
%画第二个八分园
R=5.0;
y=R;x=0;
d=1-R;
X(1)=0;Y(1)=R;
while y>x
if d<0
d=d+2*x+3; %取E点
else
d=d+2*(x-y)+5;%取SE点
y=y-1;
end
x=x+1;
X(x+1)=x;
Y(x+1)=y;
end
%利用对称性求其它七个八分园
X1=Y;Y1=X;
X2=-Y;Y2=X;
X3=-X;Y3=Y;
X4=Y;Y4=-X;
X5=X;Y5=-Y;
X6=-X;Y6=-Y;
X7=-Y;Y7=-X;
plot(X,Y,X,Y,'o',X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,X6,Y6,X7,Y7);
title('R=5');
算法分析：
二阶差分法：利用二阶差分降低增量阶数
二阶差分(降低增量阶数,用差分法消除中点算法中乘法运算)。
中点算法中：
1，如在现有点p(xp,yp)上，对p+1点选择了E(xp+1,yp)点
(1)增量ÄΔE
二阶差分增量为：
(2)增量ÄΔSE
二阶差分增量为：
2，如在现有点p(xp,yp)上，对p+1点选择了SE(xp+1,yp-1)点
(1)增量ÄΔE
二阶差分增量为：
(2)增量ΔSE
二阶差分增量为：

x
y
d
DE
D SE
x=x+1 ( d<0)
y
d + DE
DE+2
DSE+2
x=x+1 (d>0)
y-1
d + DSE
DE+2
DSE+4

算法步骤：
1，依据上一次迭代中d符号来选择现在点E或SE (d0=1-R)；
2，用在上一次迭代计算和来计算新d；
3，用移到新象素点二次差分值，并用它来更新和移到下一点。

例:设R=5,试用二阶差分法画园。
x
y
d
DE
D SE
0
5
1-5=-4
3
5-2*5=-5
1
5
-4+3=-1
3+2=5
-5+2=-3
2
5
-1+5=4
5+2=7
-3+2=-1
3
4
4-1=3
7+2=9
-1+4=3
4
3
3+3=6
9+2=11
5+4=9
%画第二个八分园
clear;
R=5.0;
Y(1)=R; X(1)=0; d=1-R; deltaE=3; deltaSE=5-2*R;
x=0;y=R;
while y>x
if d<0 %选 E点
d=d+deltaE;
deltaE=deltaE+2;
deltaSE=deltaSE+2;
else %选 SE点
d=d+deltaSE;
deltaE=deltaE+2;
deltaSE=deltaSE+4;
y=y-1;
end
x=x+1;
X(x+1)=x;
Y(x+1)=y;
end

%利用对称性求其它七个八分园
X1=Y; Y1=X;
X2=-Y; Y2=X;
X3=-X; Y3=Y;
X4=Y; Y4=-X;
X5=X; Y5=-Y;
X6=-X; Y6=-Y;
X7=-Y; Y7=-X;
plot(X,Y,X,Y,'o',X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,X6,Y6,X7,Y7);
title('R=5');
Bresendham 画园算法
H(xi+1,yi)
D(xi+1,yi-1)
(xi,yi)
V(xi,yi+1)
算法原理：
设(xi,yi)为已确定象素坐标，则下一个象素只能是（H、D、V）三象素之一。
五种情况：
① H、D、V全在园内；
② H在园外，D、V在园内；
③ D在园上，H在园外，V在园内；
④ H、D在园外，V全在园内；
⑤ H、D、V全在园外。
H、D、V到园心距离平方和园外半径平方之差分别为：

增量算法：（为判定(xi+2,yi+2)判别式）
1、如在现有点(xi,yi)上，下一点选择了H(xi+1,yi)点，在H点
2、如在现有点(xi,yi)上，下一点选择了D(xi+1,yi-1)点，在D点

3、如在现有点(xi,yi)上，下一点选择了V(xi,yi-1)点，在V点
初始值：

%画第二个八分园
clear;
R=5.0; delta=2*(1-R); x=0;y=R;i=1;
while y>x -1
X(i)=x; Y(i)=y;
if delta<0
delta1=2*(delta+y)-1;
if delta1<=0
direction=1;
else
direction=2;
end
else if delta >0
delta2=2*(delta-x)-1;
if delta2<=0
direction=2;
else
direction=3;
end
else
direction=2;
end
end
switch direction
case 1
x=x+1; delta=delta+2*x+1;
case 2
x=x+1; y=y-1;
delta=delta+2*(x-y+1);
case 3
y=y-1; delta=delta-2*y+1;
end
i=i+1;
end %While end
%利用对称性求其它七个八分园
X1=Y; Y1=X;
X2=-Y; Y2=X;
X3=-X; Y3=Y;
X4=Y; Y4=-X;
X5=X; Y5=-Y;
X6=-X; Y6=-Y;
X7=-Y; Y7=-X;
plot(X,Y,X,Y,'o',X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,X6,Y6,X7,Y7);
title('R=5');
plot(X,Y,X,Y,'o',X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,X6,Y6,X7,Y7);
title('R=5');
试验三 椭园生成算法
试验课时：4
试验类型：（验证、综合、设计）
试验要求：选修
一、试验目标
经过本试验，使学生了解并掌握在光栅显示系统中椭圆生成和显示算法。
二、试验内容
实现中点椭圆算法。
三、试验原理、方法和手段
参见本指导书
四、试验组织运行要求
以学生自主训练为主开放模式组织教学。
五、试验条件：
硬件平台：PC
软件(推荐)：Windows平台，Visual C++，matlab
六、试验步骤
1. 掌握算法原理；
2. 依据算法，编写源程序并进行调试；
3. 对运行结果进行保留和分析；
4. 把源程序以文件形式提交；
5. 按格式书写试验汇报。
七、思索题
八、试验汇报
要求在指导书中明确学生试验汇报内容及具体要求，关键包含试验预习、试验统计和试验汇报三部分，基础内容详见附件1。
中点算法
y
x
b
a
算法原理：
中点算法能够推广到通常二次曲线如椭圆。
x
y
p(x,y)
上
下
中心在原点椭圆方程为：
隐函数形式为：

a=b时，该方程表示是圆。
椭圆含有四对称性，可只考虑第一象限椭圆弧。
椭圆上任一点(x,y)处法向量为：

如在p点法线两分量相等,则p点将椭圆第一象限分成两部份，上半部份法向量在y方向分量比x方向大，在下半部份相反。在p点：

在目前中点处，法向量（2b2 (Xp+1)，2a2 (Yp-0.5))y分量比x分量大，即：
b2 (Xp+1) < a2 (Yp-0.5)
而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。

B
M
T
Pi(xi,yi)
和圆弧中点算法类似：确定一个象素Pi后，接着在下两个候选象素中点计算一个判别式d＝F（M）值，由判别式符号确定更近点。
1.先讨论椭圆弧上半部分(令△x=1)
设Pi(xi，yi)已确定，则下一对待选像素中点是：
M(xi+1,yi-0.5)

对初始点（0,b)，第一个中点为(1,b-0.5)，则：

(1)当d<0(取T点)时，下一点(i+1)点坐标为(xi+1，Yi)，为确定i+2点取下一个中点M坐标为：(xi+2，yi-0.5)
(2)当d>=0(取B点)时，下一点(i+1)点坐标为(xi+1，Yi-1)，为确定i+2点取下一个中点M坐标为：(xi+2，Yi -1.5)

L
M
R
Pi(xi, yi)
2.在每一次迭代中全部要判定椭圆是否已从上半部进入了下半部，假如b2x>=a2y，则椭圆进入下半部份，此时令△y=1，且：

(1)若d<0,取右下方像素R，则

(2)若d>=0,取正下方像素L，则

3.终止条件为：y=0

MidpointEllipe(a,b, color)
int a,b,color;
{ int x,y; float d1,d2;
x = 0; y = b;
d1 = b*b +a*a*(-b+0.25);
putpixel(x,y,color);
while( b*b*(x+1) < a*a*(y-0.5))
{ { if (d1<0)
d1 +=b*b*(2*x+3); x++; }
else { d1 +=(b*b*(2*x+3)+a*a*(-2*y+2))
x++; y--; }
putpixel(x,y,color);
}//上部分
d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b);
while(y >0)
{ if (d2 <0) { d2 +=b*b*(2*x+2)+a*a*(-2*y+3);
x++; y--；}
else {d2 += a*a*(-2*y+3); y--; }
putpixel(x,y,color); } //下部分
}

算法优化(提醒)：
联解以下方程：
得到椭圆上、下部分分界点P坐标为：
(1)令x由0→Px， y由0→Py，从而避免上述算法中反复计算循环中止条件。
(2)采取增量算法，避免在计算d时乘法和平方运算。
试验四 多边形填充算法
试验课时：4
试验类型：（验证、综合、设计）
试验要求：必修
一、试验目标
使学生掌握光栅显示系统中多边形扫描转换和区域填充算法。掌握4连通和8连通区域扩展性。
二、试验内容
实现多边形扫描转换算法和区域填充算法。（任选两个算法并实现）
三、试验原理、方法和手段
对于设计性试验，应依据“由学生自行设计试验方案并加以实现试验”内涵要求，注意省略由学生自主设计“试验方案”。
四、试验组织运行要求
依据本试验特点、要求和具体条件，采取“以学生自主训练为主开放模式组织教学，还是采取集中讲课形式”，须加以明确。
五、试验条件：
硬件平台：PC
软件(推荐)：Windows平台，Visual C++，matlab
六、试验步骤
1. 掌握算法原理；
2. 依据算法，编写源程序并进行调试；
3. 对运行结果进行保留和分析；
4. 把源程序以文件形式提交；
5. 按格式书写试验汇报。
七、思索题
八、试验汇报
要求在指导书中明确学生试验汇报内容及具体要求，关键包含试验预习、试验统计和试验汇报三部分，基础内容详见附件1。
扫描线算法
算法原理：
利用相邻像素之间连贯性，提升算法效率。依据多边形内部点连续性知：一条扫描线和多边形交点中，入点和出点之间全部点全部是多边形内部点。所以，对全部扫描线填充入点到出点之间全部点就可填充多边形。
10
2
4
6
8
10
12
0
2
4
6
8
1
2
3
4
处理对象：非自交多边形（边和边之间除了顶点外无其它交点）
判定扫描线上点是否在多边形之内,依据多边形区域连续性，分为3个步骤：
– 求出扫描线和多边形全部边交点；
– 把这些交点x坐标值以升序排列；
– 对每一对交点间区域进行填充。
– 第三个步骤是从奇数个交点出发到偶数个交点。如右图，对y＝8扫描线排序x坐标得到表是(2,4,9,13)，然后对交点2和4之间、9和13之间全部象素点进行填充。
几点规则：
边界上象素:“左闭右开”，“下闭上开”(将左边界和下边界点算为内部，而将右边界和上边界算为外部)
顶点：“上开下闭”。

多个特殊情况：
1．扫描线交于一顶点，共享两条边分另处于扫描线两边，这时交点只取一个，如扫描线y=3，该点被填充一次。
2.共享交点两条边处于扫描线上方，这时交点取二个，如扫描线y=1，该点被填充一次。
3．共享交点两条边处于扫描线下方，这时交点取0个，如扫描线y=9，无交点，不填充。
4．水平边在算法中不起任何作用，可不考虑。

活性边表(提升效率)：
为了降低求交计算量，要利用一条边和相继两条扫描线交点连贯性。在处理一条扫描线时只对活性边（和它相交多边形边）进行求交运算。把交点按x增加方向存在一个链表（活性边表）中。
活性边：和目前扫描线相交边。
活性边表（AEL）：按交点x增量次序存放在一个链表中，该链表称作活性边表（AEL）。
边填充算法-正负相消法
算法原理：
对每一条扫描线和每条多边形边交点，全部将扫描线上右边全部象素求余。（偶数次取余，结果不变，）
设A为一正整数，正整数M余定义为A-M，记为 风。当计算机中用n位表示M时，可取A为n位能表示最大整数，即A=2n-1。可知
即对M作偶数次取余，结果仍为M。
求余可用异或显示模式实现。
以扫描线为中心边缘填充法：
设是目前扫描线和多边形交点x坐标数列，填充该扫描线上在多边形内区段由下列步骤完成：
算法1（以扫描线为中心边缘填充算法）
1、将目前扫描线上全部象素着上颜色；
2、求余：
for(i = 0;i <= m; i++)
在目前扫描线上，从横坐标为Xi交点向右求余；

算法2（以边为中心边缘填充算法）
1、将绘图窗口背景色置为；
2、对多边形每一条非水平边做：该边上每个象素开始向右求余；

边缘填充算法和扫描线法比较：
适适用于含有帧缓存图形系统。处理后，按扫描线次序读出帧缓存内容，送入显示设备。
l优点：边缘填表充法数据结构和程序结构全部比扫描线法简单
l缺点：对于复杂图形，每一象素可能被访问数次，输入/输出量比扫描线算法大得多。要对帧缓存大量象素反复赋值，速度较慢，并难于用图元填充。

边标志算法（轮廓填充算法）
改善边填充法：
优点：对每个象素只访问一次。无须建立、维护边表及对边表进行排序，适于硬件实现。
步骤：
１、对多边形每条边进行直线扫描变换，立即多边形经过象素打上边标志；
２、填充，即对每条多边形相交扫描线依次从左到右逐一访问该扫描线上象素；
使用一个布尔变量inside 来指示目前点状态(inside初始值为False) ，若目前象素在多边形内部,则inside为真,反之为假。
若目前象素为打上边标志点，就将inside取反(为 True)，对未打标志象素，inside不变仍为False。
对inside为True 象素进行填充。

种子填充算法
种子填充算法首先假定区域由封闭轮廓线围成，且轮廓线内某点是已知，然后开始搜索和种子点相邻且在轮廓线内点。假如这相邻 点不在轮廓线内，则已达成轮廓线边界；假如相邻点在轮廓线之内，则这相邻点成为新种子点，继续搜索下去。只适适用于光栅扫描设备。
区域分类（区域采取边界定义，即区域边界上和边界外象素取相同值，区域内部点取不一样值）
1、 四向连通区域：各象素在水平垂直四个方向是边通。即从区域内任一点出发，可水平／垂直移动抵达区域内任一点。
2、 八向连通区域：各象素在水平、垂直、及四个对角线方向全部是是边通。即从区域内任一点出发，可水平、垂直、及四个对角线方向移动抵达区域内任一点。

区域填充(种子填充法)
区域填充–对区域重新着色过程。
–将指定颜色从种子点扩展到整个区域过程
–区域填充算法要求区域是连通
l 连通性： 4连通、8连通
堆栈结构实现种子算法,四向算法:
1、种子象素压入堆栈
2、若堆栈非空，即有区域中象素在堆栈中，做以下循环：
A.栈顶象素出栈；
B.将出栈象素置为多边形颜色；
C.按左、上、右、下四个方向左右次序检验和出栈象素相邻四个象素，若其中某象素不在边界置为多边形颜色，则将该象素推入堆栈。
算法特点：简单。
问题：算法是深度递归，效益低。要求很大存放空间来实现堆栈。
八向算法：将搜索方向改为八个。可填充八向连通区域和四向连通区域。
设象素种子为S(4,3)，按左、上、右、下检验出栈象素四个相邻四个象素，当算法进行到(5,5)堆栈深度为23层，栈内包含很多无须要信息。

S
1-8
2-11
3-7
4
9
10
5
6
0
1
2
3
4
5
1
0
2
3
4
入栈次序

出栈填色次序

S
5-11
7-10
3-9
1
8
6
4
2
0
1
2
3
4
5
1
0
2
3
4

种子填充算法缺点：
(1)有些象素会入栈数次，降低算法效率；栈结构占空间。
(2)递归实施，算法简单，但效率不高，区域内每一象素全部引发一次递归，进/出栈，费时费内存。
改善算法，降低递归次数，提升效率。

扫描线种子算法
测试对象为象素段 ,对区域内每一象素段,只保留其最右边(或左边)象素作为种子象素.
区域填充(扫描线算法)：
–目标：降低递归层次
–适适用于内点表示4连通区域
基础过程：
当给定种子点时，首先填充种子点所在扫描线上在给定区域一个区段，然后确定和这一区段相通上下两条扫描线上在给定区域内区段，并依次保留下来。反复这个过程，直到填充结束。

算法步骤：
1、填充并确定种子区段；
2、初始化：将种子区段压入堆栈；
3、出栈：假如堆栈为空，则算法结束；不然取栈顶元素y,xLeft,xRight），以纵坐标为y扫描线为目前扫描线，[xLeft, xRight]为搜索区间；
4、填充并确定新区段 。
试验五 常见曲面和曲线生成算法
试验课时：
试验类型：（验证、综合、设计）
试验要求：必修
一、试验目标
掌握常见曲线和曲面生成算法，为几何造型打下基础。
二、试验内容
编写绘制Hermit、Bezier、B样条曲线程序。
三、试验原理、方法和手段
对于设计性试验，应依据“由学生自行设计试验方案并加以实现试验”内涵要求，注意省略由学生自主设计“试验方案”。
四、试验组织运行要求
依据本试验特点、要求和具体条件，采取“以学生自主训练为主开放模式组织教学，还是采取集中讲课形式”，须加以明确。
五、试验条件：
硬件平台：PC
软件(推荐)：Windows平台，Visual C++，matlab
六、试验步骤
1. 掌握算法原理；
2. 依据算法，编写源程序并进行调试；
3. 对运行结果进行保留和分析；
4. 把源程序以文件形式提交；
5. 按格式书写试验汇报。
七、思索题
八、试验汇报
要求在指导书中明确学生试验汇报内容及具体要求，关键包含试验预习、试验统计和试验汇报三部分，基础内容详见附件1。
三次Hermite曲线生成:
算法原理：
给定直线两个端点：P0，P1，及两端点处切线：R0，R1，则三次Hermit曲线方程为：

例：
P0=[100,100];P1=[200,150];
Q0=[-200,100];Q1=[-100,120];
count=100; deltat=1/count;
t=0.0;
PX(1)=P0(1); PY(1)=P0(2);
for i=1:count
t=t+deltat;
F3=2*t*t*t-3*t*t+1;
F2=-2*t*t*t+3*t*t;
F1=t*t*t-2*t*t+t;
F0=t*t*t-t*t;

PX(i+1)=F3*P0(1)+F2*P1(1) +F1*Q0(1)+F0*Q1(1);
PY(i+1)=F3*P0(2)+F2*P1(2) +F1*Q0(2)+F0*Q1(2);
end
figure;plot(PX,PY,PX,PY,'o');
title('P0=[100,100];P1=[200,150];
Q0=[-200,100];Q1=[-100,120];');

P0=[100,400];P1=[200,450];Q0=[-200,100];Q1=[-100,120];
count=1000; deltat=1/count;
t=0.0;
PX(1)=P0(1); PY(1)=P0(2);
for i=1:count
t=t+deltat;
F3=2*t*t*t-3*t*t+1; F2=-2*t*t*t+3*t*t;
F1=t*t*t-2*t*t+t; F0=t*t*t-t*t;

PX(i+1)=F3*P0(1)+F2*P1(1) +F1*Q0(1)+F0*Q1(1);
PY(i+1)=F3*P0(2)+F2*P1(2) +F1*Q0(2)+F0*Q1(2);
end
figure;plot(PX,PY,PX,PY,'o');
title('P0=[100,400];P1=[200,450];Q0=[-200,100];Q1=[-100,120];');

Bezier曲线(以迫近为基础参数曲线):
满足以下条件一组折线集(Bezier特征多边形)称为Bezier曲线：
曲线起点和终点和多边形起点和终点重合，多边形第一条边和最终一条边表示曲线在起点和终点切矢量方向。曲线形状趋向于Bezier特征多边形形状。
当给定Bezier特征多边形n+1个顶点Pi时，
Bezier曲线插值公式为：
(权Bi,n(t) i=0,1,2,3,…n+1称为基函数)
Bernstein(伯恩斯坦)基函数：

三次Bezier曲线矩阵表示：
调合函数：

例：
P0=[100,100];P1=[200, 450];
P2=