计算机图形学3-2课件

第3章基本图形的生成与计算2.3区域填充算法2.1直线的生成算法2.2圆的生成算法2.4字符的生成2.5图形求交2.6图形裁剪2.1直线的生成算法画一条从(x1,y1)到(x2,y2)的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为直线光栅化。连续性粗细、亮度要均匀像素逼近待画直线速度2.1直线的生成算法2.1.1直线DDA算法

(DigitalDifferentialAnalyser)

假设直线的起点坐标为P1(x1,y1)，终点坐标为P2(x2,y2)x方向的增量为△x＝x2－x1

；y方向上增量为△y＝y2－y1

直线的斜率为k＝△y／△x

当△x＞△y时，让x从x1

到x2变化，每步递增1，那么，x的变化可以表示为xi+1＝xi＋1y的变化可以表示为yi+1＝yi＋k

用上式可求得图中直线P1P2和y

向网格线的交点，但显示时要用舍入找到最靠近交点处的象素点来表示。当△x<△y时，让y递增1，x作相应变化。

综合考虑，按照从(x1,y1)到(x2,y2)方向不同，分8个象限(图2.1)。对于方向在第1a象限内的直线而言，取增量值Dx=1，Dy=m。对于方向在第1b象限内的直线而言，取增量值Dy=1，Dx=1/m。2.1直线的生成算法2.1.1直线DDA算法（续）图2.1直线方向的8个象限

象

限dx>dy?

Dx

Dy1atrue1

m1bfalse1/m12atrue-1m2bfalse-1/m13atrue-1-m3bfalse-1/m-14atrue1-m4bfalse1/m-1表2.18个象限中的坐标增量值

研究表中的数据，可以发现两个规律。⒈

当dx>dy时

Dx=1，Dy=m否则

Dx=1/m，Dy=1⒉Dx、Dy的符号与dx、dy的符号相同。

2.1直线的生成算法2.1.1直线DDA算法（续）

算法描述如下：dda_line(intxa,intya,intxb,intyb,intc){floatdelta_x,delta_y,x,y;intdx,dy,steps,k;dx=xbxa;dy=ybya;if(abs(dx)>abs(dy)) steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;2.1直线的生成算法2.1.1直线DDA算法（续）x=xa;y=ya;set_pixel(x,y,c);for(k=1;k<=steps;k++){x+=delta_x;y+=delta_y;set_pixel((int)(x+0.5),y+0.5,c);}}

使用DDA算法，每生成一条直线做两次除法，画线中每一点做两次加法。因此，用DDA法生成直线的速度是相当快的。2.1.1直线的扫描转换——中点画线算法直线方程：F(x,y)=ax+by+c=0P1:(xp+1,yp)P2:(xp+1,yp+1)M:(xp+1,yp+0.5)若M在直线F之上方，则F(x,y)>0若M在直线F之下方，则F(x,y)<0P=(Xp,Yp)P1P2MQ2.1直线的生成算法2.1直线的生成算法令:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+cd<0，则M在直线下方(即在Q下方)，故取P2作为下一个像素点；而若d>0，则取正右方P1；若d=0，二者一样合适，可任取一个，这里约定取P1。为了提高d的运算效率，可采用增量方式计算2.1.1直线的扫描转换——中点画线算法在d≥0时，取正右方像素点P1，则下一个中点M坐标：M1(xp+2,yp+0.5)，则下一个像素点的判别式d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a故d的增量为a。而若d<0，则取右上方像素点P2,则下一个中点M坐标：M2(xp+2,yp+1.5)，则下一个像素点的判别式2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b故在后一种的情况下d的增量为a+b。d的初值，显然第一个像素应取左端点(x0,y0),相应的判别式为：d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法因(x0,y0)在直线上，则F(x0,y0)=0即d0=a+0.5b,由于只用到d的符号，为了减少浮点运算，可用2d代替d，则初值为:2d0=2a+b。中点画线算法的C语言实现voidMidpoint_line(intx0,inty0,intx1,inty1){ inta,b,delta1,delta2,d,x,y; a=y0-y1,b=x0-x1; d=a+a+b;2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法 delta1=a+a; delta2=(a+b)+(a+b); x=x0,y=y0; SetPixel(x,y); while(x<x1) { if(d<0) { x++;y++;d+=delta2; }

else { x++;d+=delta1; } SetPixel(x,y); }}2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法上述算法中，只有整数的加减法运算，没有乘除，所以适合硬件实现2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法2.1.1直线的扫描转换——中点画线算法2.1直线的生成算法2.1直线的生成算法2.1.3直线Bresenham算法

设直线从起点(x1,y1)到终点(x2,y2)。直线可表示为方程y=mx+b，其中

b=y1-m*x1,m=（y2-y1)/(x2-x1)=dy/dx;

此处的讨论先将直线方向限于1a象限(图2.2)，在这种情况下，当直线光栅化时，x每次都增加1个单元，即xi+1=xi

+1而y的相应增加值应当小于1。为了光栅化，yi+1只可能选择图2.2中两种位置之一。图2.2纵坐标的位置选择

2.1直线的生成算法2.1.3直线Bresenham算法(续）

yi+1的位置选择yi+1=yi或者yi+1=yi+1，选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算公式为

y=m(xi

+1)+b(2.1)

d1=y

yi(2.2)

d2=yi+1

y

(2.3)如果d1d2>0，则yi+1=yi+1，否则yi+1=yi。将式(2.1)、(2.2)、(2.3)代入d1d2，再用dx乘等式两边，并以Pi=(d1d2)dx代入上述等式，得

Pi=2xidy2yidx+2dy+(2b1)dx(2.4)d1d2是用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi+1为

Pi+1=Pi+2dy2(yi+1yi)dx

(2.5)2.1直线的生成算法2.1.3直线Bresenham算法(续）

求误差的初值P1，可将x1、y1和b代入式(2.4)中的xi、yi而得到

P1=2dydx

综述上面的推导，第1a象限内的直线Bresenham算法思想如下：⒈

画点(x1,y1)，dx=x2x1，dy=y2y1，计算误差初值P1=2dy

dx，i=1；⒉

求直线的下一点位置xi+1=xi+1

如果Pi>0，则yi+1=yi+1，否则yi+1=yi；⒊

画点(xi+1,yi+1)；⒋

求下一个误差Pi+1，如果Pi>0，则Pi+1=Pi+2dy2dx，否则

Pi+1=Pi+2dy；⒌

i=i+1；如果i<dx+1则转步骤2；否则结束操作。VoidLineBre(PDC*pDC,intx0,inty0,intxend,intyend){ intdx=xend-x0; intdy=yend-y0; intp=2*dy-dx; intx,y;x=x0; y=y0; pDC->SetPixel(x,y,c); while(x<xend) { x++; if(p<0) { p=p+2*dy; } else { p=p+2*dy-2*dx; y++; } pDC->SetPixel(x,y,c); }}根据Bresenham画线算法，直线端点为(20,10)和（30,18)，请填写下列表格数据。解：根据Bresenham画线算法，直线端点为(20,10)和（30,18)Dx＝10，Dy＝8，

k=Dy/Dx=0.8，2Dy＝16，2Dy－2Dx＝－4P0

＝2Dy－Dx＝6画初始点(20,10),并根据判别式确定沿线段路径的后续像素位置如下表：2.1直线的生成算法2.1.3直线Bresenham算法(续）

Bresenham算法的优点如下：⒈

不必计算直线的斜率，因此不做除法。⒉

不用浮点数，只用整数。⒊

只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。Bresenham算法的运算速度很快，并适于用硬件实现。讨论：以上讨论的是0＜△y＜△x的情况，对于适用所有8个方向的直线(图2.1)的生成算法，则要考虑以判断条件|dx|>|dy|为分支，并分别将2a、3a象限的直线和3b、4b象限的直线变换到1a、4a和2b、1b象限方向去，以实现程序处理的简洁。作业，编写程序，比较DDA画线算法与Bresenhan画线速度2.2圆的生成算法2.2.1基础知识

给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：⒈

直角坐标法

(xxc)2+(yyc)2=r2由上式导出：

当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标。但这并非是生成圆的最好方法。这个方法的一个问题是每一步包含很大的计算量。而且，如图所示，所画像素位置间的间距是不一致的。我们可以在圆斜率的绝对值大于1后，交换x和y(即步进y值并计算x值)来调整间距。但是，这种方法增加了算法所需的计算量和处理过程。2.2圆的生成算法2.2圆的生成算法2.2.1基础知识(续）

⒉

极坐标法x=xc+r·cosθ，y=yc+r

·sinθ使用上述方法以固定角度为步长生成显示结果时，就可以利用沿圆周的等距点来绘制出圆。为了减少计算量，我们可以在相邻点间使用较大的角度间隔并用线段连接相邻点来逼近圆的路径。在光栅显示中设定角度间隔为1/r可获得较连续的边界。这样绘出的像素位置大约间隔一个单位。尽管极坐标系统提供了等距点，但三角函数计算是十分耗时的。

2.2圆的生成算法利用圆周坐标的对称性，此算法还可以简化。将圆周分为8个象限，只要将第1a象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。

中点画圆法

由于圆的对称性，下面主要考虑中心在原点半径为r的圆的第二8分圆。若从圆的正上方开始讨论如何确定最佳逼近于该圆弧的像素序列。P=(x,y)P1P2M

假定当前已确定了圆弧上的一个像素点为P(xp,yp)，那么，下一个像素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp–1)两者之一。如图所示

那么，当F(M)>0时，M在圆外，这说明P2距离圆弧更近，应取P2作为下一像素。而当F(M)<0时，P1离圆弧更近，应取P1。当F(M)=0时，在P1与P2之中随便取一个即可，约定取P2。

对于圆上的点，F(x,y)=0；对于圆外的点，F(x,y)>0；而对于圆内的点，F(x,y)<0。与中点画线法类似，设M是P1和P2的中点，即M=(xp+1，yp–0.5)。

构造函数：

F(x,y)=x2＋y2–r2(3–5)P=(x,y)P1P2M

若d＜0，则应取P1为下一像素，而且再下一个像素的判别式为

d=F(xp

+2，yp–0.5)=(xp+2)2+(yp

–0.5)2–R2

=d+2xp+3所以，沿正右方向，d的增量为2xp+3。

与中点画线法一样，构造判别式

d=F(M)=F(xp+1，yp–0.5)=(xp+1)2+(yp–0.5)2–R2

而若d≥0，则P2是下一像素，而且下一像素的判别式为

d'=F(xp+2,yp–1.5)=(xp+2)2

+(yp

–1.5)2–R2=d+(2xp

+3)+(–2yp

+2)所以,沿右下方向,判别式d的增量为2(xp–yp)+5。

初始时，

x0=0，

y0=R，

d0=F(x0+1,y0-0.5)=(0+1)2+(R-0.5)2-R2=1.25-R。

但这个算法中仍然有浮点数运算。令f=d-0.25，那么初始时，x0=0，y0=R，f0=d0-0.25=1-R。假设已知当前列像素位置(xi,yi)和判别式fi，则有：中点画圆算法

1）.如果fi<-0.25，那么下一列像素位置

xi+1=xi+1，

yi+1=yi，

fi+1=fi+2xi+3；

2）.

如果fi≥-0.25，那么下一列像素位置

xi+1=xi+1，

yi+1=yi-1，

fi+1=fi+2xi-2yi+5。

f的初始值1-R为整数，每次迭代f的变化量也是整数，即f保持为整数，因此f<-0.25等价于f<0。

以下是中点画圆算法的C语言描述：voidMidpointCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=1–r；

WholeCircle（xc，yc，x，y，color）；

while（x<=y）

{if（d＜0）

{d+=2*x+3；x++；}else{d+=2*（x–y）+5；x++;y––；}WholeCircle（xc，yc，x，y，color）；

}}voidWholeCircle(intxc,intyc,intx,inty,intcolor){CDC*pDC=GetDC（）；

pDC->Setpixel(xc+x，yc+y，color)；

pDC->Setpixel(xc–x，yc+y，color)；

pDC->Setpixel(xc+x，yc–y，color)；

pDC->Setpixel(xc–x，yc–y，color)；

pDC->Setpixel(xc+y，yc+x，color)；

pDC->Setpixel(xc–y，yc+x，color)；

pDC->Setpixel(xc+y，yc–x，color)；

pDC->Setpixel(xc–y，yc–x，color)；ReleaseDC(pDC);}3.2.3Bresenham画圆算法

考虑圆心在原点，半径为r的第一个8分圆。取(0,r)为起点，按顺时针方向生成圆。如图3.6所示。从这段圆弧的任意一点出发，按顺时针方向生成圆时。在这种情况下，x每步增加1，即：yxyiyi-1xixi+1yxi+1=xi+1则相应的y有二种选择：

yi+1=yi

或yi+1=yi-1Bresenham画圆算法采用一个决策值来确定到底是选择yi还是yi-1。在x=xi+1位置上，用d1和d2来标识两个候选像素的y值与圆弧上理想y值的差值，则：y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2

令di=d1-d2，并代入d1、d2，则有：（方差最小）

di=2(xi+1)2+yi2+(yi-1)2-2r2这里di就是Bresenham画圆算法的第i步决策值。如果di<0，则yi+1=yi，否则yi+1=yi-1。若di=0，则可任选一个，我们约定yi+1=yi-1。

下面来推导di的递推公式。在i+1步，di+1为：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2

若di<0，取右方像素，yi+1=yi，则：

di+1=2(xi+1+1)2+yi2+(yi-1)2-2r2=di+4xi+6而决策值的初值d0由x=0,y=r代入前面公式，得：

d0=2(0+1)2+r2+(r-1)2-2r2=3-2r已知xi+1=xi+1，因而得到：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2

若di>=0，取右下方像素，yi+1=yi-1，则：di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2=di+4(xi-yi)+10

由此，可写出Bresenham画圆算法的C程序：

2.2圆的生成算法2.2.2圆的Bresenham算法(续）

根据上面的推导，圆周生成算法思想如下：⒈求误差初值，p1=32r，i=1，画点(0,r)；⒉求下一个光栅位置，其中xi+1=xi+1，如果pi<0则yi+1=yi，否则yi+1=yi1；⒊画点(xi+1,yi+1)；⒋计算下一个误差，如果pi<0则pi+1=pi+4xi+6，否则pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y则结束，否则返回步骤2。2.2圆的生成算法2.2.2圆的Bresenham算法(续）

圆的Bresenham算法的程序实现如下：

circle(CDC*pDC,intxc,intyc,intradius,intc)

{

intx,y,p;

x=0;

y=radius;

p=32*radius；

while(x<y) {

plot_circle_points(pDc,xc,yc,x,y,c);

if(p<0)p=p+4*x+6;

else {

p=p+4*(xy)+10;

y=1;

}

x+=1;

}

if(x==y)

plot_circle_points(pDC,xc,yc,x,y,c);

}

2.2圆的生成算法2.2.2圆的Bresenham算法(续）plot_circle_points(intxc,intyc,intx,inty,intc){pDC->SetPixel(xc+x,yc+y,c);pDC->SetPixel(xcx,yc+y,c);pDC->SetPixel(xc+x,ycy,c);pDC->SetPixel(xcx,ycy,c);pDC->SetPixel(xc+y,yc+x,c);pDC->SetPixelxcy,yc+x,c);pDC->SetPixel(xc+y,ycx,c);pDC->SetPixel(xcy,ycx,c);}2.3区域填充算法2.3.1基础知识

区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。

多边形的表示方法顶点表示点阵表示图2.5扫描线与多边形相交

图2.6光栅化后直线变成离散点

多边形填色一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判断法”。

2.3区域填充算法2.3.1基础知识(续）

2.3区域填充算法2.3.1基础知识(续）

填色算法分为两大类：⒈

扫描线填色(Scan-LineFilling)算法。这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。⒉

种子填色(SeedFilling)算法。这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色（给出种子点），而难以用于全自动程序填色。2.3区域填充算法2.3.2扫描线填色算法

算法的基本思想。多边形以n、x_array、y_array的形式给出，其中，x_array、y_array中存放着多边形的n个顶点的x，y坐标。用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交点。这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。例：对右图的多边形进行填充思路：算出交点；划分区间；分配颜色步骤：对每条扫描线分为4步(以扫描线6为例)991234568710001876453211求交点，即计算该扫描线与多边形各边的交点排序，由于交点不一定由左到右求出，因此将求出的交点按x坐标值排序交点配对，1与2，3与4，…

…，每对表示一个区间区间填充991234568710001876453211ABCDP1P2P3P4P5P6扫描线2的交点按X排序：2，2，8扫描线7的交点按X排序：2，2，9，11问题：1.扫描线与顶点相交时，交点的取舍2.边界像素的取舍991234568710001876453211ABCDP1P2P3P4P5P6991234568710001876453211ABCDP1P2P3P4P5P60次0次2次1次具体方法1：检查共享该顶点的两条边另外两个顶点的Y值，按这两个Y值中大于共享该顶点Y值的个数是0、1、2来决定是取0、1、2个交点。2.3区域填充算法2.3.2扫描线填色算法(续）

上述基本思想中，有几个问题需要解决或改进：⒈

左、右顶点处理。当以1、2、3的次序画多边形外框时，多边形的左顶点和右顶点如图2.7中所示的顶点2。它们具有以下性质。左顶点2：y1<y2<y3右顶点2：y1>y2>y3

其中y1、y2、y3是3个相邻的顶点的y坐标。图2.7多边形的顶点

当扫描线与多边形的每个顶点相交时，会同时产生2个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。因此，对所有左、右顶点作如下处理：2.3区域填充算法2.3.2扫描线填色算法(续）

左、右顶点的入边(以该顶点为终点的那条边，即1–2边)之终点删去。对于左顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(

,y21)；对于右顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(

,y2+1)；其中，，即入边的斜率。对于多边形的上顶点(y2>y1、y2>y3)或下顶点(y2<y1、y2<y3)，奇偶计数保持正确。

⒉

水平边处理。水平边(y1=y2)与水平扫描线重合无法求交点。因此，将水平边画出后删去，不参加求交点及求交点以后的操作。

2.3区域填充算法2.3.2扫描线填色算法(续）

⒊

扫描线与边的求交点方法采用递归算法。以(x1,y1)、(x2,y2)为端点的边与第i+1条扫描线的交点为此式表示交点不为(x1,y1)。否则，交点为(x1,y1)。⒋

减少求交计算量，采用活性边表。对于一根扫描线而言，与之相交的边只占多边形全部边的一部分,每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改进。

活性边表(ActiveListofSide)的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前扫描线不相交的边的集合。对后者不必进行求交运算，这样就提高了算法的效率。2.3区域填充算法2.3.2扫描线填色算法(续）

图2.8活性边表及其指针的表示

扫描线填充算法是一种非常有效的算法，它对于每个象素只访问一次，其缺点是对于各种表的维持和排序的耗费大。活性边表的构成方法是：1）将经过左、右顶点处理及剔除水平边后的多边形之各边按照maxy值排序，存入一个线性表中。表中每一个元素代表一根边。第一个元素是maxy值最大的边，最后一个元素是maxy值最小的边。图2.3.4(a)中的多边形所形成的线性表如（b）所示。其中F点和B点的y值相等，且为全部多边形的maxy的最大值。因此FG,FE,AB,BC等四边排在表之首。而C点的y值>E点的y值，所以CH排在DE前面，余类推。在maxy值相等的边之间，按任意次序排列。 2)在上述线性表上加入两个指针first和last，即形成活性边表。这两个指针之间是与当前扫描线相交的边的集合和已经处理完（即扫描完）的边的集合。这两者的区分方法是在处理完的边上加上记号：△

y=0。在last指针以后的是尚未与当前扫描线相交的，在first指针以前的是已经处理完了的边。对于图2.3.4(a)中扫描线scan1的情况下，图2.3.4(b)中列出first,last的位置。如果扫描线由上而下移到了scan2的位置，则活性边表的first应指向AB，last应指向CH。每根扫描线只须与位于first,last之间的，而且△

y不为0的边求交即可。这就缩小了求交的范围。3）活性边表中每个元素的内容包括：边的maxy值，记为y_top；与当前扫描线相交点的x坐标值，记为x_int；边的y方向当前总长。初始值为y2-y1。记为△

y；边的斜率倒数：x2-x1/y2-y1

，记为x_change_per_scan。typedefstruct{inty_top;//边的最大Y值

floatx_int;//与扫描线相交点的X坐标

intdelta_y;//直线在Y方向上的总长

floatx_change_per_scan;//直线斜率倒数}EACH_ENTRY;4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：调整first和last指针字间的参加求交的边元素之值：△

y=△y-1;x_int=x_int-x_change_per_scan;调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：当first所指边的△

y=0时，first=first+1；当last所指的下一条边的y_top?下一扫描线的y值时，last=last+1。二、扫描线填色程序 程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count,x,y)，其中参数x,y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为：1、sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表。操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来；如是水平边则直接画出。2、put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，在该边的位置中填入数据。3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。4、process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且?y?0的边）按照x_int的大小排序。操作步骤是：从first到last，对每一根?y?0的边，调用sort_on_x子程序排入活性边表中合适位置。5、sort_on_x子程序主要功能是将一条边side[entry]，在活性边表的first到entry之间按x_int的大小插入合适位置。操作步骤是：检查位于entry的边的x_int是否小于位置entry-1的边的x_int，如是，调用swap子程序交换两条边的彼此位置。6、swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。7、draw_lines子程序的主要功能是在一条扫描线位于多边形内的部分，填上指定的色彩。操作步骤是：在活性边表的激活边范围内，依次取出Δy¹0两边的x_int，作为两个端点（x1,scan），(x2,scan)，画一条水平线。8、update_sides_list子程序的主要功能是刷新活性边表内激活边的值：Δy=Dy-1

x_int=x_int_x_chang_per_scan；2.3区域填充——边填充算法

1.简单的边填充算法每边与扫描线交点右方的所有像素取“补”,多边形边的顺序可任意取P1P2P3P4P5P2P3P3P4P4P5P5P12.3区域填充——边填充算法

1.简单的边填充算法特点：方法简单每一个像素被访问多次，输入/输出工作量大2.3区域填充——边填充算法

2.栅栏填充算法栅栏：与扫描线垂直的直线，通常过多边形顶点，且将多边形分成两半方法：对每个扫描线与多边形的交点，将交点与栅栏间的像素取“补”特点：方法简单减少了被重复访问的像素，特别是有多个填充对象时，效果显著2.3区域填充——边填充算法

2.栅栏填充算法P4P5P5P1P1P2P3P4P5P2P3P3P42.3区域填充——边填充算法

3.边标志算法基本思想：帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。使用一个布尔量inside来指示当前点是否在多边形内的状态。2.3区域填充——边填充算法

3.边标志算法9912345687100018764532119912345687100018764532112.3区域填充——边填充算法

3.边标志算法(算法过程)voidedgemark_fill(polydef,color)多边形定义polydef；intcolor;{对多边形polydef每条边进行直线扫描转换；

inside=FALSE;for(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x){if(象素x被打上边标志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}2.3区域填充——边填充算法

3.边标志算法(算法过程)用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。2.4区域填充——种子填充算法基本原理：假设在多边形区域内部有一象素已知，由此出发找到区域内的所有象素四连通区域和八连通区域四连通方向八连通方向种子可以从四个方向寻找下一像素，称为四向算法；允许从八个方向寻找下一像素，称为八向算法。八向算法可以填充八连通区域和四连通区域，而四向算法只能填充四连通区域2.4区域填充——种子填充算法四连通区域和八连通区域991234568710001876453211四连通区域八连通区域9912345687100018764532112.4区域填充——种子填充算法

1.简单的种子填充算法1.初始化：种子像素入栈，当栈非空时，重复2～

4的步骤2.栈顶像素出栈3.将出栈像素置为多边形颜色4.按左、上、右、下顺序依次检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则该像素入栈5.当堆栈为空时，算法终止2.4区域填充——种子填充算法

1.简单的种子填充算法01234543210S1(2,3)(2,2)(3,3)(2,4)(1,3)(2,2)(3,3)(2,4)(1,2)(1,4)(2,2)(3,3)(2,4)(1,2)(2,4)(2,2)(3,3)(2,4)(1,2)(2,2)(3,3)(2,4)(2,2)(2,2)(3,3)(2,4)(2,1)(3,2)(2,2)(3,3)(2,4)(2,1)(3,3)(2,2)(3,3)(2,4)(2,1)2.4区域填充——种子填充算法

1.简单的种子填充算法voidBoundaryFill4(intx,inty,intboundarycolor,intfillcolor){intcurrentcolor; currentcolor=getpoxel(x,y); if(currentcolor!=fillcolor&¤tcolor!=boundarycolor) { setcolor(fillcolor);setpixel(x,y); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}2.4区域填充——种子填充算法

1.简单的种子填充算法特点：算法简单，可以用于填充带有内孔的区域像素可能重复入栈，降低了算法效率存储空间开销较大2.4区域填充——种子填充算法

2.扫描线种子填充算法基本思想：首先填充种子点所在扫描线上的位于给定区域的一个区段然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。2.4区域填充——种子填充算法

2.扫描线种子填充算法算法步骤：(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。2.4区域填充——种子填充算法

2.扫描线种子填充算法(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈。(5)重复(2)～(4)步。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。2.4区域填充——种子填充算法

2.扫描线种子填充算法sxLxR0123456789101112111098765432108,67,109,96,119,95,119,94,119,93,113,45,49,92,113,45,49,93,45,49,92,45,49,95,49,96,49,97,49,99,92.4区域填充——种子填充算法

2.扫描线种子填充算法(C语言程序)typedefstruct{//记录种子点

intx; inty;}Seed;voidScanLineFill(intx,inty,intoldcolor,intnewcolor){intxl,xr,i;boolspanNeedFill;Seedpt;setstackempty();//清空堆栈pt.x=x;pt.y=y;stackpush(pt);//将前面生成的区段压入堆栈

2.4区域填充——种子填充算法

2.扫描线种子填充算法(C语言程序)while(!isstackempty()){ pt=stackpop(); y=pt.y; x=pt.x; while(getpixel(x,y)==oldcolor)//向右填充

{ drawpixel(x,y,newcolor); x++; } xr=x-1; x=pt.x-1; while(getpixel(x,y)==oldcolor)//向左填充

{ drawpixel(x,y,newcolor); x--; }2.4区域填充——种子填充算法

2.扫描线种子填充算法(C语言程序)

xl=x+1; //处理上面一条扫描线

x=xl; y=y+1; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; }2.4区域填充——种子填充算法

2.扫描线种子填充算法(C语言程序)

while(getpixel(x,y)!=oldcolor&&x<xr) x++; }//Endofwhile(i<xr) //处理下面一条扫描线，代码与处理上面一 //条扫描线类似

x=xl; y=y-2; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; }2.4区域填充——种子填充算法

2.扫描线种子填充算法(C语言程序)

x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; } while(getpixel(x,y)!=oldcolor&&x<xr) x++; }//Endofwhile(i<xr)}//Endofwhile(!isstackempty())}2.4区域填充——圆域的填充算法基本思想：将多边形区域的扫描线算法，推广到圆域的填充。先计算每条扫描线与圆域的相交区间；和圆交点的计算可以改造中点画圆法来进行。再把区间用指定颜色填充。对于同时对多个圆填充时，可以采用类似活性边表的方式，即活性圆表法。2.4区域填充——区域的图案填充图案：一般是用一个M×N的位图来表示2.4区域填充——区域的图案填充图案与区域的相对位置关系：(1)图案与区域边界或内部对齐(2)图案与区域外部对齐设对齐点为(x0,y0)，则图案填充：if(pattern((x-x0)%M,(y-y0)%N) drawpixel(x,y,color);else drawpixel(x,y,background);2.4字符的生成2.4.1点阵式字符

点阵式字符将字符形状表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。

使用点阵式字符时，需将字库中的矩形点阵复制到缓冲器中指定的单元中去。在复制过程中，可以施加变换，以获得简单的变化。图2.11(b)~(d)列出了以字母P为原型的一些变化例子。图2.11点阵式字符及其变化

图（b）变成粗体字。算法是：当字符原型中每个象素被写入帧缓存寄存器的指定位置xi,yi时，同时被写入xi+1,yi。图（c）旋转900

。算法是：把字符原型中每个象素的x,y坐标彼此交换，并使y值改变符号后，再写入帧缓存寄存器的指定位置。图（d）斜体字。算法是：从底到顶逐行拷贝字符，每隔n行，左移一单元。 此外，还可以对点阵式字符作比例缩放等其他一些简单的变换。但是对点阵式字符作任意角度的旋转等变换，是比较困难的操作。 由于光栅扫描显示器的普遍使用，点阵式字符表示已经成为一种字符表示的主要形式。从字库中读出原字型，经过变换拷贝到buffer中去的操作，经常制成专门的硬件来完成。这就大大加快了字符生成的速度。2.4字符的生成2.4.2矢量式字符

矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻画。图2.12示出用矢量式表示的字符“B”。“B”是由顶点序列{a,b,c,d,e,f,e,g,h,i,j,k,j,

a,l}的坐标表达。图2.12矢量式表示字符“B”2.4字符的生成2.4.3方向编码式字符

方向编码式字符用有限的若干种方向编码来表达一个字符。图2.13示出8个方向的编码为0~7。图2.14(a)示出字母“B”的方向矢量构成。这样，“B”就表示为8方向编码{0000123444000123444406666}。方向编码式字符很容易被填入帧暂存寄存器中予以显示(图2.14(b))，方向编码所占的空间比较小，它也能接受一些特定的变换操作。图2.13字符的8方向编码

图2.14方向编码式字符的实例2.4字符的生成2.4.4轮廓字形技术

直接使用点阵式字符方法将耗费巨大的存储空间。压缩方法有多种，最简单的有黑白段压缩法。另一种方法是部件压缩法。三是轮廓字形法，这种方法压缩比大，且能保证字符质，是当今国际上最流行的一种方法。

轮廓字形法采用直线、或者二次Bezier曲线、三次Bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义和一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。采用适当的区域填充算法，可以从字符的轮廓线定义产生的字符位图点阵，区域填充算法可以用硬件实现，也可以用软件实现。由美国Apple和Microsoft公司联合开发的TrueType字型技术就是一种轮廓字型技术，已被用于为Windows中文版生成汉字字库。当前占领主要的电子印刷市场的我国北大方正和华光电子印刷系统，用的字型技术是汉字字型轮廓矢量法。这种方法能够准确地把字符的信息描述下来，保证了还原的字符质量，又对字型数据进行了大量的压缩。调用字符时，可以任意地放大、缩小或进行花样变化，基本上能满足电子印刷中字型质量的要求。轮廓字型技术有着广泛的应用。到目前为止在印刷行业中使用最多。2.5图形求交

在计算机图形学中常常会遇到求交计算。求交运算是比较复杂的，为了减少计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略地比较，排除那些显然不相交的情形。

求交问题可以分为两类：

求交点求交线

2.5图形求交2.5.1求交点算法

求交点可以分两种情况，即求线与线的交点以及求线与面的交点。⒈

直线段与直线段的交点假设两条直线的端点分别为P1、P2和Q1、Q2，则直线可以用向量形式表示为P(t)=A+Bt，

0≤t≤1Q(s)=C+Ds，

0≤s≤1其中，A=P1，B=P2P1，C=Q1，D=Q2Q1。构造方程

A+Bt=C+Ds(2.9)

对三维空间中的直线段来说，上述方程组实际上是一个二元一次方程组，由3个方程式组成。可以从其中两个解出s、t，再用第三个验证解的有效性。当所得的解(ti,si)是有效解时，可用两个方程之一计算交点坐标，例如P(ti)=A+Bti。

2.5图形求交2.5.1求交点算法（续）

根据向量的基本性质，可直接计算s与t。对方程(2.9)两边构造点积得

(CD)·(A+Bt)=(CD)·(C+Ds)由于CD同时垂直于C和D，等式右边为0。故有类似地有2.5图形求交2.5.1求交点算法（续）

⒉

直线段与二次曲线的交点考虑平面上一条直线与同平面的一条二次曲线的交点。假设曲线方程为f(x,y)=0直线段方程为(x,y)=(x1+tdx,y1+tdy)则在交点处有

f(x1+tdx,y1+tdy)=0当曲线为二次曲线时，上述方程可写为

at2+bt+c=0用二次方程求根公式即可解出t值。⒊

圆锥曲线与圆锥曲线的交点在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数法或几何法表示为隐函数形式，另一条表示为参数形式(如二次NURBS曲线)。将参数形式代入隐函数形式可得到关于参数的四次方程。2.5图形求交2.5.1求交点算法（续）

下面讨论线与面的交点的求法。⒈

直线段与平面的交点图2.15线段与平面求交

如图2.15所示。把平面上的点表示为P(u,w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于

R=P(u,w)=Q(t)，即A+uB+wC=D+tE2.5图形求交2.5.1求交点算法（续）

等式两边点乘(BC)，得

(BC)·(A+uB+wC)=(BC)·(D+tE)由于BC既垂直于B，又垂直于C，故有

(BC)·

A=(BC)·(D+tE)可解出类似求得如果是直线与平面区域求交点，则要进一步判断交点是否在平面的有效区域中，其算法可参见2.5.3节。2.5图形求交2.5.1求交点算法（续）

⒉

圆锥曲线与平面的交点圆锥曲线与平面求交点时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程，从而进行求解。⒊

圆锥曲线与二次曲面的交点圆锥曲线与二次曲面求交点时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用四次方程求根公式求解。2.5图形求交2.5.2

求交线算法

⒈

平面与平面的交线先考虑最简单的情形。两个平面区域分别由P(u,w)，Q(s,t)，u，w，s，t[0,1]定义。如果它们不共面而且不分离，则必交于一直线段。这条直线必落在P(u,w)Q(s,t)=0所定义的无限直线上。这是个含有4个未知数，3个方程式的方程组，只要分别与8条边界线方程：u=0，u=1，w=0，w=1，s=0，s=1，t=0，t=1联立，即可求出线段的两个端点的参数。

2.5图形求交2.5.2

求交线算法

（续）

⒉

平面与二次曲面的交线

代数法:

把二次曲面表示为代数形式

Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0

通过平移与旋转坐标变换把平面变为xOy平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为z=0，所以新坐标系下二次曲面方程中，把含z项都去掉即为平面与二次曲面的交线方程。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。

几何法:几何法存储曲线的类型(椭圆、抛物线或双曲线)，以及定义参数(中心点、对称轴、半径等)的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。

当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。2.5图形求交2.5.2

求交线算法

（续）

下面以平面—球求交为例，说明几何法求交算法。平面用一个记录p表示，p的两个子域p.b、p.w分别代表平面上一点、平面法向量。球面用记录s表示，它的两个子域s.c、s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下：plane_sphere_intersect(p,s)planep;spheres;{d=球面中心到平面的有向距离；if(abs(d)==s.r){2个面相交于一(切)点s.cd*p.w;}elseif(abs(d)>s.r){两个面无交；}2.5图形求交2.5.2

求交线算法

（续）

else{所求交线是圆。其圆心、半径、圆所在平面法向量为c=s.cd*p.w;r=sqrt(s.r2d2);w=p.w;}}

2.5图形求交2.5.2

求交线算法（续）

⒊

平面与参数曲面的交线求平面与参数曲面的交线，最简单的方法是把表示参数曲面的变量(x(s,t),y(s,t),z(s,t))代入平面方程

ax+by+cz+d=0得到用参数曲面的参数s、t表示的交线方程

ax(s,t)+by(s,t)+cz(s,t)+d=0

另一种方法是，用平移和旋转对平面进行坐标变换，使平面成为新坐标系下的xOy平面。再将相同的变换应用于参数曲面方程，得到参数曲面在新坐标系下的方程

(x*,y*,z*)=(x*(s,t),y*(s,t),z*(s,t))由此得交线在新坐标系下的方程为z*(s,t)=0。2.5图形求交2.5.3包含判定算法

在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域或三维形体中，线段是否包含在平面区域或三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上的问题可以转化为判断线段两端点是否在平面上。判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有3种，即直线段、圆锥曲线段(主要是圆弧)和参数曲线(主要是Bezier曲线、B样条与NURBS曲线)。点与面的包含判定也类似地分为3种情况。下面分别予以讨论。2.5图形求交2.5.3包含判定算法（续）⒈

点与直线段的包含判定假设点坐标为P(x,y,z)，直线段端点为P1(x1,y1,z1)、P2(x2,y2,z2)，则点P到线段P1P2