第三章基本图形生成

计算机图形学

第三章基本图形生成信电学院王利娟本章内容3.1直线的生成3.2圆与椭圆的生成3.3区域填充3.5线宽与线型的处理本章预备知识光栅显示输出技术

目前，主要图形输出设备如计算机显示器、打印机等都采用光栅显示输出技术。

光栅显示技术：显示器屏幕或打印机上打印出的图形可以认为是由许多像素点组成。

★像素点的坐标位置(x,y)必须为整数值。★控制像素点的颜色值来显示图形或文字。本章预备知识光栅（点阵）显示输出技术屏幕分辨率为M×N大小，固定排列方式xy设备坐标系像素(10,5)(4,6)(0,0)本章预备知识选择绘制基本图形的坐标系？世界坐标系，

为直角坐标系xy本章预备知识如何在屏幕上绘制生成基本图形？

通过在屏幕（或显示设备）上确定生成一个图形

所需的一个像素集合及其颜色。该过程称为图形的扫描转换或图形的光栅化。所谓的基本图形生成原理，是指在点阵（光栅）输出设备的情况下，如何对一条斜的直线或弯曲的曲线尽可能快地输出其最接近理想的直线或曲线，即如何以最快的速度确定最佳逼近于图形的像素集。本章预备知识直线的扫描转换或光栅化

数学直线：由无穷多个无限小连续点组成本章预备知识图形的扫描转换或光栅化

屏幕上显示直线：由尽可能接近直线的像素点集合并填充颜

色来表示。(1,1)(2,1)

(3,2)(4,2)

(5,3)(6,3)

(7,4)(8,4)写像素的函数：putpixel(x,y,color)第3章基本图形生成3.1直线的生成问题：如何发现最佳逼近直线的像素集？3.1.1数值微分算法3.1.2中点画线算法3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线k表示斜率；b表示y轴截距设直线端点为(x1,y1)和(x2,y2),斜率截距方程为：斜率k就是直线的微分该式子称为

直线的微分方程第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线考虑让x从起点到终点变化，每步递增或递减1，讨论:若生成直线斜率|k|<1设直线上前一点为(xi,yi)，随后一点为(xi+1,yi+1)如何查找最逼近该直线的像素集？第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线讨论:若生成直线|k|<1设直线上前一点为(xi,yi)，

随后一点为(xi+1,yi+1)(xi+1,yi+1)点(xi,yi)(xi+1,yi+1)需要转换为最近的整像素位置点，(xk,yk)，(xk+1,yk+1)(xk,yk)(xi+1,(int)(yi+k+0.5)第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线考虑让y从起点到终点变化，每步递增或递减1，讨论:若生成直线斜率|k|>1设直线上前一点为(xi,yi)，随后一点为(xi+1,yi+1)(xi+1,yi+1)(xi,yi)(xk,yk)(xk+1,yk+1)第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线让y从起点到终点变化，每步递增或递减1，讨论:若生成直线斜率|k|>1(xi+1,yi+1)(xi,yi)(xk,yk)(xk+1,yk+1)第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线若生成直线斜率|k|=1若生成直线斜率|k|=0若生成直线斜率|k|=∞复习

绘图软件程序设计如何在屏幕上绘制生成基本图形？光栅扫描显示技术直线的生成数值微分DDA算法直线的微分方程:|k|<1;

|k|>1;

|k|=1;

|k|=0;

|k|=第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线算法代码：算法中根据|k|来决定是x变化还是y变化假设直线两端点：

计算kdx=x2－

x1;dy=y2－

y1;if(dx≠0)k=dy/dx;

判断k的取值范围分成|k|≤1和|k|>1两种情况if(k<=1&&k>=-1){}else{}确定每步递增还是递减，并确定像素点一般认为A(x1,y1)为起点，B(x2,y2)为终点，所以x＝x1,y＝y1;|k|≤1时，x每步改变1，计算y±＝k

if(x1＜x2)

for(x＝x1;x＜x2;x＋＋)

{putpixel(x,int(y+0.5),color);y＋＝k;}

else

for(x＝x1;x＞＝x2;x－－)

{putpixel(x,int(y+0.5),color);y－＝k;}确定每步递增还是递减，并确定像素点|k|>1时，y每步改变1，计算x±=1/k

if(y1＜y2)

for(y＝y1;y＜y2;y＋＋){putpixel(int(x+0.5),y,color);x＋＝1／k;}

else

for(y＝y1;y＞＝y2;y－－){putpixel(int(x＋0.5),y,color);x－＝1／k;}确定每步递增还是递减，并确定像素点|k|>1时，y每步改变1，计算x±=1/k

if(y1＜y2)

for(y＝y1;y＜y2;y＋＋){putpixel(int(x+0.5),y,color);x＋＝1／k;}

else

for(y＝y1;y＞＝y2;y－－){putpixel(int(x＋0.5),y,color);x－＝1／k;}|k|=∞的特殊情况（即竖直线：x1＝x2)if(y1＜y2

)

for(y＝y1;y＜＝y2;y＋＋

)putpixel(x,y,color);

else

for(y＝y1;y＞＝y2;y－－

)putpixel(x,y,color);第3章基本图形生成3.1直线的生成3.1.1数值微分（DDA）算法利用直线的微分方程生成直线例：画直线段P0(0,0)－－P1(5,2)

计算直线斜率

沿着x方向查找像素集xi+1=xi+1yi+1=yi+kint(yi+1+0.5)

0 0 01 0.40 2 0.81 3 1.21 4 1.62 5 2.02 int()表示向下取整的函数3.1.2中点画线算法第3章基本图形生成3.1直线的生成分析直线生成算法，总结规律（以k[0,1]为例）：

若直线在x方向增加一个像素单位，则在y方向增量只能在01之间。设直线上当前像素点为P0(xk,yk),则下一个最逼近直线的像素点只能在其正右方或右上方。中点画线法的算法表达式：3.1.2中点画线算法第3章基本图形生成3.1直线的生成问题：如何判断M与Q点的关系？3.1.2中点画线算法第3章基本图形生成3.1直线的生成设直线两端点为(x1,y1)，(x2,y2)直线的线性方程令3.1.2中点画线算法第3章基本图形生成3.1直线的生成根据直线方程点在直线上点在直线上方点在直线下方欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。3.1.2中点画线算法第3章基本图形生成3.1直线的生成构造判别式当d<0，M在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取正右方P1；当d=0，选P1或P2均可，

约定取P1；能否采用增量算法呢？把M代入F(x,y)采用增量计算dd≥0时，取正右方像素P1，再下一个像素的判断，计算d1d<0时，取右上方像素P2，再下一个像素的判断，计算d2d的增量为ad的增量为a+bd的初值第一个像素取左端点(x1,y1)，则判断第二个像素的判别式为：算法运行中只使用d的符号，增量a或a+b都是整数，只有初始值包含小数，因此，把d以及增量都扩大2倍，即摆脱了小数，也不会改变符号

中点画线法的迭代表达式

程序分析

参数计算a＝y1－y2;b＝x2－x1;

d0以及增量

d0＝2a＋b;d1=2a;d2=2(a＋b)

循环结构确定像素x＝x1;y＝y1;putpixel(x,y,color)

for(x＝x1;x＜＝x2;x

＋＋){if(d＜0){y＋＋

;d＋＝d2;}

else{d＋＝d1;}

putpixel(x,y,color);}例：用中点画线法画直线段P0(0,0)－－P1(5,2)3.1.2中点画线算法第3章基本图形生成3.1直线的生成

计算a＝y1－y2＝－2；b＝x2－x1＝5

计算参数：

d0＝2a＋b=12a＝－42(a＋b)＝6

xk

dk

yk 0 d0=1 0 1 d1=d0+2a=－3 0 2 d2=d1+2(a+b)=3

1 3 d3=d2+2a=－1

1

4 d4=d3+2(a+b)=525d5=d4+2a=42例：用中点画线法画直线段P0(0,0)－－P1(5,2)3.1.2中点画线算法第3章基本图形生成3.1直线的生成(0,0)(1,0)(2,1)(3,1)(4,2)(5,2)3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成基本原理:构造决策变量dk来确定下一个像素点if(d1>d2)，取P2if(d1<d2)，取P1构造dk=△x(d1-d2)，根据dk的符号确定下一个像素考虑0<k<1情况3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成计算dkif(dk>0)，直线理想位置接近右上方像素P2(xk+1,yk+1)if(dk<0)，直线理想位置接近正右方像素P1(xk+1,yk)if(dk=0)，约定取右上方点P2(xk+1,yk+1)计算dk每步的增量取右上方像素P2时，yk+1=yk+1，增量为：2△y-2△x取正右方像素P1时，yk+1=yk，增量为：2△y3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成计算初始判别量d13.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成Bresenham画线法的迭代表达式程序分析

参数计算dx＝x2－x1;dy＝y2－y1;dp＝2dy－dx;

循环确定下一像素

y＝y1;

for(x＝x1;x＜＝x2;x＋＋){putpixel(x,y,color)；

if(dp＞＝0){y＋＋;dp－＝2dx;}

dp＋＝2*dy;}例：用Bresenham画线法画直线段,给出两端点

为：P0(20,10)－－P1(30,18)3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成

计算△y

，△x

△y＝

y2－

y1＝8；

△x＝

x2－

x1＝10

计算参数dk：

d0＝2△y－△x＝62△y＝162△y－2△x＝－4

例：用Bresenham画线法画直线段,给出两端点

为：P0(20,10)－－P1(30,18)3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成idi(xi+1,yi+1)idi(xi+1,yi+1)06(21,11)56(26,15)12(22,12)62(27,16)2-2(23,12)7-2(28,16)314(24,13)814(29,17)410(25,14)910(30,18)

d0＝2△y－△x＝62△y＝162△y－2△x＝－4

2021222530101518例：用Bresenham画线法画直线段,给出两端点

为：P0(20,10)－－P1(30,18)3.1.3Bresenham画线算法第3章基本图形生成3.1直线的生成(21,11),(22,12),(23,12),(24,13),(25,14),(26,15),(27,16),(28,16),(29,17),(30,18)第3章基本图形生成3.2圆与椭圆的生成问题：如何发现最佳逼近圆或椭圆的像素集？3.2.1圆的特性3.2.2中点画圆算法3.2.3Bresenham画圆算法3.2.4椭圆的生成算法3.2.1圆的特性第3章基本图形生成3.2圆与椭圆的生成圆的直角坐标方程画圆方法一

沿x轴从xc－r到xc＋r以单位步长改变，并计算相应y值计算量大，所画像素位置间距不一致，x的改变量均匀，但y不一致3.2.1圆的特性第3章基本图形生成3.2圆与椭圆的生成圆的极坐标参数方程画圆方法二采用极坐标形式，以固定角度为边长，可以绘出等距点，但牵涉到三角函数调用、浮点运算，速度太慢减少计算量是关键

圆的对称性只要画出其中一个8

分圆，根据对称性可

得另外7个8分圆上的

对应点关键为一个8分圆的

生成算法3.2.1圆的特性第3章基本图形生成3.2圆与椭圆的生成处理对象：圆心在原点的圆弧；一般取第一象限内以y=x为界的上半部分，即第二8分圆3.2.2中点画圆算法第3章基本图形生成3.2圆与椭圆的生成基本原理Q在M上（M在Q下），取P1Q在M下（M在Q上），取P2考虑对象：中心在原点的圆的第二8分圆；第3章基本图形生成3.2圆与椭圆的生成3.2.2中点画圆算法构造函数：

圆上的点F(x,y)＝0

圆外的点F(x,y)＞0

圆内的点F(x,y)＜0第3章基本图形生成3.2圆与椭圆的生成3.2.2中点画圆算法设M是P1和P2的中点，即M＝(xp＋1,yp－0.5),

当F(M)＜0时，M在圆内，说明P1距离圆弧更近，取P1；当F(M)＞0时，P取P2第3章基本图形生成3.2圆与椭圆的生成3.2.2中点画圆算法构造判别式：if(d>0)，中点M在圆外，Q距P2近，取右下方点P2作为下一个像素if(d<0)，中点M在圆内，Q距P1近，取正右边点P1作为下一个像素if(d＝0)，中点M在圆上，约定取右下方点P2

计算增量

d＜0时，取正右方像素P1，再下一个像素的判断，计算d1

d≥0时，取右下方像素P2，再下一个像素的判断，计算d2d的增量为2xp＋3d的增量为2(xp－yp)＋5

计算d的初值顺时针方向生成第二个8分圆，所以第一个像素取为(0,r)，则判断第二个像素的判别式为：d0包含小数，而e=d0-0.25=1-r为整数算法中判别d的符号，等同于判断e是否大于-0.25d的增量都是整数，因此，e始终为整数，所以，判断e>-0.25与e>0等同。算法中有浮点数，用e＝d－0.25代替

中点画圆法的迭代表达式程序分析赋初值d＝1－r;x＝0;y＝r;循环确定下一像素While(x＜＝y){if(d＜0)d＋＝2*x＋3；

else{d＋＝2*(x－y)＋5;y－－;}

x＋＋;

WholeCircle(xc,yc,x,y,color);}第3章基本图形生成3.2圆与椭圆的生成3.2.2中点画圆算法第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法设Pi(xi,yi)是已经选取的一个像素点，根据这段第二8分圆的特点，可以判定下一个像素将从Hi(xi+1,yi)和Di(xi+1,yi-1)两点中选取第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法构造函数：第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法引入判别式根据di的符号可以选择候选像素为Di还是Hi

。如果di≥0,则应选取Di;如果di<0,则应选取Hi;

第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法像素迭代计算di每步的增量如果di<0,应选择Hi,则下一点(xi+1,yi)的判别式是如果di>0,应选择Di,则下一点(xi+1,yi-1)的判别式是第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法像素迭代计算di每步的增量对于初值d0,x0=0,y0=r第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法Bresenham画圆法的迭代表达式，圆弧靠近P1，圆弧靠近P2第3章基本图形生成3.2圆与椭圆的生成3.2.3Bresenham画圆算法程序分析参数计算x＝0;y＝r;d＝3－2*r;循环确定下一像素While(x＜y){WholeCircle(xc,yc,x,y,color);

if(d＜0)d＋＝4*x＋

6；

else{d＝4*(x－y)＋10;y－－;}

x＋＋;}if(x＝＝y)WholeCircle(xc,yc,x,y,color);复习当在屏幕上显示一条直线时，在显示器所给定的有限个像素矩阵中，确定发现最佳逼近该直线的像素集，并且按扫描顺序对这些像素进行写操作。这就是用显示器绘制直线或直线的扫描转换3.1直线的生成（直线的扫描转换）1.什么是直线的扫描转换？2.掌握DDA画线、中点画线和Bresenham画线算法步骤和计算？3.直线生成规律①生成直线斜率k[0,1],（正右方）（右上方）

中点画线法的迭代表达式令Bresenham画线法的迭代表达式3.2圆与椭圆的生成基本思想：确定发现最佳逼近圆或椭圆的像素集，并且按扫描顺序对这些像素进行写操作。这就是圆或椭圆的扫描转换

只要画出其中一个8分圆，根据对称性可得另外7个8分圆上的对应点。关键为一个第二8分圆的生成算法圆心在原点的圆弧；一般取第一象限内以y=x为界的上半部分，即第二8分圆1.如何生成一个圆弧？3.2圆与椭圆的生成2.分析第二8分圆生成规律？生成第二8分圆规律第一象限内以y=x为界的上半部分（正右方）（右下方）第二8分圆起始点：(0,R);终止条件为x=y;3.掌握中点画圆和Bresenham画圆算法

步骤和计算？

中点画圆法的迭代表达式Bresenham画圆法的迭代表达式，圆弧靠近P1，圆弧靠近P2第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法长半轴为a，短半轴为b，中心为原点的标准椭圆ab

根据椭圆对称性的特点,考虑对象：第一象限1/4椭圆弧(x,y)(－x,y)(－x,－y)(x,－y)N以弧上斜率为-1的点作为分界45o把椭圆弧分为上下两部分上部分椭圆弧生成？？下部分椭圆弧生成？？上部分下部分第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：如何区分开上半部分和下半部分椭圆弧？ab上部分下部分构造函数：

弧上斜率为-1的分界点(xN,yN)：1/4椭圆弧上部分：1/4椭圆弧下部分：(xN,yN)F(xN,yN)=02b2xN=2a2yN第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法构造函数：说明(x,y)在椭圆边界内说明(x,y)在椭圆边界外说明(x,y)在椭圆边界上第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？沿着x方向来确定下一像素点。PP1P2M对于当前确定弧上像素点P(xp,yp)M为候选像素点P1和P2的中点M＝(xp＋1,yp－0.5)中点画椭圆法判别式：第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？中点画椭圆法M为候选像素点P1和P2的中点判别式：if(dp>0)，M在椭圆外，下一个像素取右下方点P2if(dp<0)，M在椭圆内，下一个像素取正右边点P1if(dp=0)，约定取右下方点P2第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？if(dp<0),取正右方像素P1，再下一个像素的判断，计算M第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？if(dp≥0

),取右下方像素P2，再下一个像素的判断，计算M第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？M取弧起点P0(0,b)，再下一个像素的判断，计算第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的上半部分的生成算法？满足：第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？沿着y方向来确定下一像素点。PP1P2M对于当前确定弧上像素点P(xp,yp)M为候选像素点P1和P2的中点M＝(xp＋0.5,yp－1)中点画椭圆法判别式：第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？PP1P2MM为候选像素点P1和P2的中点中点画椭圆法判别式：if(dp>0)，M在椭圆外，下一个像素取正下方点P1if(dp<0)，M在椭圆内，下一个像素取右下方点P2if(dp=0)，约定取右下方点P2第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？if(dp<0),取右下方像素P2，再下一个像素的判断，计算M第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？if(dp≥

0),取正下方像素P1，再下一个像素的判断，计算M第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？下半部分中点判别式d0初始值：M若上半部分椭圆弧生成的最后一个像素为(xp,yp)，则下半部分第一个中点为：(xp＋0.5,yp－1)为由上部分转入下部分条件满足时的值第3章基本图形生成3.2圆与椭圆的生成3.2.4椭圆的生成算法问题：1/4椭圆弧的下半部分的生成算法？满足：第3章基本图形生成3.3区域填充讨论问题：如何用一种颜色或图案来填充一个2-D区域，该区域可为多边形、圆或椭圆，甚至是带孔的一般步骤确定那些像素位于填充图元的内部；确定以什么颜色填充这些像素；第3章基本图形生成3.3区域填充3.3.1有序边表填充算法3.3.2边填充算法3.3.3种子填充算法3.3.4圆和椭圆的填充算法颜色填充封闭区域算法图案填充封闭区域算法3.3.5图案填充第3章基本图形生成3.3区域填充3.3.1有序边表填充算法对于若干边所构成的区域，用扫描线y＝i扫描，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素问题1：多边形区域扫描线填充算法?以扫描线“6”为例与多边形的边界交于A、B、C、D四个点把扫描线划分为五个区间①②③④⑤其中②和④落在多边形内，该区间内像素应取填充色，其余区间的像素取背景色！0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)①②③④⑤多边形P1P2P3P4P5P6，注意相交顺序及交点排序问题第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题2：多边形区域扫描线填充算法步骤：1．求交计算扫描线与多边形各边的所有交点；2．排序按x坐标递增顺序对交点进行排序；3．交点配对第1、2个，第3、4个为一对等等，每对代表一个区间4．区间填色区间内像素置成填充色，区间外像素置成背景色第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题3：多边形顶点处的扫描线交点取舍：情况1：共享顶点的两条边在扫描线的两边

扫描线交点只能算一个如扫描线2，边P6P1、P1P2位于扫描线2的两边，交点算一个，即扫描线2与多边形的交点为2、8，给区间[2,8]着色第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题3：多边形顶点处的扫描线交点取舍：情况2：共享顶点的两条边在扫描线的一边

扫描线交点可算零个或两个取0还是2，取决于该点是多边形的局部最高点

还是局部最低点如扫描线1，与多边形交于点顶点P2，共享该顶点的另外两条边的另外两个顶点均高于P2，故取交点P2两次，即像素P2用多边形填充色着色如扫描线7，与多边形交于顶点P6，边P6P1、P5P6的另外两顶点均低于P6点，所以，取交点P6

0次，P6点不填充第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题3：多边形顶点处的扫描线交点取舍：第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题4：活化边表（Active-Edge-Table）AET的概念

活化边表（Active-Edge-Table）与当前扫描线相交的边称为活化边，把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为活化边表！引入活化边表的概念，目的在于提高计算效率，在处理每一条扫描线时，不必将其与所有边求交，只需考虑与活化边求交即可！第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题4：活化边表活化边表AET的结点内容：

x：当前扫描线与边的交点坐标

△x：从当前扫描线到下一条扫描线间的x增量

ymax：该边所交的最高扫描线号，边上最高的顶点扫描线6的活性边表P6P1P5P6P4P5P3P4ABCD扫描线7的活性边表P4P5P3P49281108∧FG第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题4：活化边表

更新活化边表每离开一条扫描线，进入下一条扫描线之前，应做的工作：

将与当前扫描线相交而与下一条扫描线不相交的边，从AET表中清除！将下一条扫描线新交上的边，加入AET中适当的位置！

活化边表(AET)的作用

通过AET，可以充分利用边的连贯性和扫描线的连贯性，减少求交计算量，提高排序效率

新边表(NET)概念的引入为了方便活化边表的建立与更新，为每条扫描线建立一个新的边表称之为NET（New-Edge-Table

）第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题5：AET&NET第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题6：有序边表(SET)或新边表(NET)概念构建新边表为每一条扫描线建立一个新边表，存放在该扫描线第一次出现的边若某边的较低端点为ymin，则该边就存放在扫描线ymin的边表中，边表的每个结点存放对应边的初始信息：lower.x，△x，以及该边的最大y值ymax构建新边表第3章基本图形生成3.3区域填充3.3.1有序边表填充算法问题5：有序边表填充算法步骤输入多边形的顶点数及其顶点坐标求填充区域的扫描线最大值、最小值对处理范围内的每条扫描线建立有序边表对处理范围内的每条扫描线，进行处理用有序边表建立当前扫描线的活化边表从活化边表中依次取出一对交点，对这两个交点内的像素填充为下一条扫描线更新活化边表，即增加交点的x值和删除不再相交的边重新活化边表复习：3.2圆与椭圆的生成1.如何生成第一象限1/4椭圆弧？以弧上斜率为-1的点作为分界，把第一象限1/4椭圆弧分为上下两部分：上部分圆弧点：起始点(0,b)，条件：2b2x2a2y

在x方向取单位步长下部分圆弧点：终点(a,0)

，条件：2b2x2a2y

在y方向取单位步长（正右方）（右下方）（右下方）（正下方）复习：3.3区域填充1.有序边表填充算法？①基本原理：按照扫描线从小到大（由下而上）的移动顺序，计算当前扫描线与多边形各边交点，然后把这些交点按x值递增顺序进行排序、配对，以确定填充区间，然后用指定颜色填充区间内所有像素。②步骤：求交；排序；交点配对；填充颜色复习：3.3区域填充1.有序边表填充算法？③求交问题：多边形顶点与当前扫描线的交点？复习：3.3区域填充1.有序边表填充算法？④活化边表AET的建立多边形与当前扫描线相交的边称为活化边，把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为活化边表。xΔxymaxnext当前扫描线与边的交点x坐标从当前扫描线到下一条扫描线间的x增量该边所交的最高扫描线号复习：3.3区域填充1.有序边表填充算法？⑤新边表NET的建立——活化边表的改进X0|yminΔxymaxnext边低端(y值较小的端点)所对应的x坐标从当前扫描线到下一条扫描线间的x增量该边所交的最高扫描线号第3章基本图形生成3.3区域填充3.3.2边填充算法

原理是一种实区域扫描转换算法。对每一条扫描线和多边形的每条边的交点（x,y)右方的所有像素取补。二次取补等于抹掉。边填充算法示意图P1P2P3P4P5P1P5P5P4P4P3P3P2如果按其它顺序填充，会如何？边填充算法示意图缺点：每个象素可能访问多次，输入/输出量大；图形输出不能与扫描同步进行，只能全部画完才能打印。P3P2P3P4P5P4P5P6P2P3P3P4P4P5P5P1按

任

意

顺

序

填

充，

结

果

相

同第3章基本图形生成3.3区域填充3.3.2边填充算法

栅栏填充算法引入栅栏，以减少填充算法访问像素的次数。栅栏：与扫描线垂直的线，通常过一顶点，且把多边形一分为二。基本思想：对每条扫描线与多边形边的交点，将交点和栅栏之间的像素取补。减少了像素访问数目，但不彻底。

若交点位于栅栏左侧，将交点之右至栅栏之左所有像素取补；若交点位于栅栏左侧，将交点之右至栅栏之左所有像素取补；栅栏填充算法示意图P1P2P3P4P5P2P3P3P4P4P5P5P1第3章基本图形生成3.3区域填充3.3.3种子填充算法

原理

不是按扫描线顺序进行填充多边形区域的。填充方法是从多边形区域内部的一点开始，由此出发找到区域内所有像素，区域内部所有像素颜色值和区域边界上颜色值不同。区域边界外像素可具有与边界像素相同颜色值。第3章基本图形生成3.3区域填充3.3.3种子填充算法

区域指已经表示成点阵形式的填充图形，它是像素的集合区域可分为4向连通区域和8向连通区域

区域填充

指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程区域填充算法要求区域是连通的从当前点检测相邻像素的方法

四向连通八向连通4连通与8连通区域

算法原理种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈；将出栈像素置成填充色；按“右→上→左→下”的顺序检查与出栈像素相邻的四像素，若其中某像素不在边界上且未被置成填充色，则将其入栈！第3章基本图形生成3.3区域填充3.3.3种子填充算法种子填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799第3章基本图形生成3.3区域填充3.3.3种子填充算法

存在问题

简单的种子填充算