《计算机图形学》课件第三章

第三章基本图形生成技术

3.1直线的生成算法3.2圆的生成算法3.3多边形的扫描转换与区域填充3.4字符的生成3.5基本图元的输出属性3.6光栅图形的反走样充区域、字符串等基本几何结构，本章将讨论这些基本几何结构的设备级算法。对此，假定物体的位置直接以整数坐标给出，像素位置按照扫描线行数和列数指定，其编址方案如图3.1所示。扫描线从屏幕底部由零开始编号，像素列则沿每条扫描线从左至右由零开始编号，每个像素区域由左下角的整数网格坐标来指定。图3.1光栅显示器编址为了将对应于沿扫描线y的列x的位置上指定颜色装入帧缓冲器，我们假设有以下形式的底层函数：

setPixel(x，y，c)

有时也要求能提取当前帧缓冲器某个特定位置的亮度值（颜色值），为此我们假设有下述的底层函数：

getPixel(x，y)

3.1直线的生成算法

由于光栅图形显示器可看做是由离散的可发光像素组成的矩阵，因此，很难将一点和另一点直接连成直线，我们将确定像素最佳逼近直线的过程称为光栅化。显然，水平线、垂直线以及45°线的光栅化比较简单，而其他方向直线的光栅化则较为困难。3.1.1画直线的一般要求

首先假设为两状态显示，即每个像素点非黑即白，于是将屏幕上的像素点设置成黑色或者白色就可以显示出一幅图像来，除过水平线和垂直线之外，所有的直线都将显示出“锯齿”或“阶梯状”效果。给定直线段的端点整数坐标后，光栅图形显示器画直线的一般要求有以下三点：

（1）直线是直的、光滑的，且具有精确的起点和

终点。

光栅图形显示器采用逼近的思想来生成直线的特性决定了它难以生成完美的直线，也不能保证直线精确地通过指定的起点和终点，这些使得所画的直线呈现阶梯状或锯齿状。这一点可通过使用高分辨率显示器来改善。（2）与直线段的显示顺序无关，所显示的亮度沿直线不变，且与直线的长度和方向无关。首先，直线段的起点和终点只是数学上的一个叫法，生成的直线与哪个端点被定义为起点，哪个端点被定义为终点无关，也即与生成直线的顺序无关。另外，一个明显的事实是只有水平线、垂直线和45°线的亮度线段是沿直线段不变的，而其他方向直线的亮度由于光栅化导致其结果是不均匀的。即使对于上述的特殊情形，直线的亮度也与其方向有关。如图3.2所示，45°线上像素间距大于垂直线和水平线上的像素间距，这使垂直线和水平线比45°线较亮。图3.2垂直线与45°线上像素点分布假设图中像素点的亮度值为I，则垂直线上单位长度的亮度值为I，而45°线上单位长度的亮度值为。为了使不同长度和方向的直线具有相同亮度，需要进行开方运算，这使得运算速度变慢。一般采用折中方法，即只计算线段长度的近似值，利用整数运算减少计算量以及用硬件实现运算等。3.1.2直线的DDA算法

实现直线光栅化最简单的方法就是解直线的微分方程。设直线的起点坐标为(xs，ys)，终点坐标为(xe，ye)，那么该直线的微分方程是：(3.1)(3.２)其解为或式中，(xi，yi)是直线上某一点的坐标值。式（3.1）和（3.2）表示所求直线y值和x值的逐次递归关系，递归的初值为直线的起点(xs，ys)。DDA(DigitalDifferentialAnalyzer)算法即数字微分分析算法就是基于式（3.1）或（3.2）对直线进行光栅化的算法。在一个坐标轴上以单位间隔对直线采样，以此决定另一个坐标轴上最靠近直线的对应整数值。首先考虑具有非负斜率的直线，当m≤1时，在单位

x间隔(Δx=1)取样并计算每个连续的y值：

yi+1=yi+m

(3.3)

由于m可以是介于0与1之间的任意实数，所以计算出的y值显示在光栅显示器上时应先取整。

当m>1时，则将x和y交换，即在单位y间隔(Δy=1)取样并计算每个连续的x值：

xi+1=xi+m－1

(3.4)当直线的斜率为负时，如果－1≤m≤0，那么，Δx=－1，并且

yi+1=yi－m

(3.5)

当m<－1时，则Δy=－1，且

xi+1=xi－m－1

(3.6)

总结起来也可以将问题简化为：当|m|≤1时，令

xs<xe，则Δx=1，yi+1=yi+m；当|m|>1时，令ys<ye，

则Δy=1，xi+1=xi+m－1。

DDA算法的C语言程序实现如下：

#include<stdio.h>

#include<graphics.h>

voidline_DDA(intxs，intys，intxe，intye，intc)

{

inti，x=xs，y=ys；

floatxIncrement，yIncrement，steps，dx=xe-xs，

dy=ye-ys；

steps=abs(dx)；

if(abs(dy)>abs(dx))steps=abs(dy)；

xIncrement=dx/steps；

yIncrement=dy/steps；

setPixel(x，y，c)；

for(i=1；i<=steps；i++)

{

x+=xIncrement；

y+=yIncrement；

setPixel(x，y，c)；

}

}算法将直线两个端点的像素位置作为输入，其过程可概括为：将端点位置的水平和垂直差赋给参数dx和dy，两者中绝对值大者决定参数steps的值。从像素位置(xs，ys)

开始，确定沿直线生成下一个像素位置每步的所需偏移量，并循环上述过程steps次。

如果dx的绝对值大于dy的绝对值，那么x方向和y方向的增量分别为±1和±m；如果dy的绝对值大于dx的绝对值，那么y向和x方向的增量分别为±1和±m－1。3.1.3直线的Bresenham算法

DDA算法原理简单、有效，利用显示器的光栅特性，消除了直线方程中求点的乘法运算，在x，y两个方向使用合理的增量沿直线逐步求出各像素的位置。然而，浮点增量的连续迭加中取整误差的累积会使长线段所计算的像素位置偏离实际线段，而且程序中的取整操作和浮点运算仍然十分耗时。为此，这里我们讨论生成直线的Bresenham算法。

Bresenham于1965年提出了一个只使用整数运算的经典算法（通常称为Bresenham算法）。作为生成直线的最有效的算法之一，该算法根据前一个已计算的像素点(xi，yi)

进行增量运算得到下一个像素点(xi+1，yi+1)，而不必进

行取整操作。该算法也可扩充其浮点数功能以处理端点坐标是任意实数的直线。为了说明算法原理，我们首先考虑斜率非负且不超过

1的直线的光栅化过程。设直线的起点和终点坐标分别为(xs，ys)和(xe，ye)，则直线的方程为y=mx+b，其中

b=ye－mxe

由于0≤m≤1，所以当直线光栅化时，x每次都增

加1，即xi+1=xi+1，而y的相应增加值为m。为了光栅化，yi+1只能选择yi或yi+1(图3.3)。选择的原则是看精确的y值与

yi及yi+1的距离d1和d2的大小。图3.3纵坐标的位置选择由于

所以，如果d1(xi+1)－d2(xi+1)>0，则yi+1=yi+1，否则，yi+1=yi。因此，算法的关键在于如何简便地求d1(xi+1)－d2(xi+1)的符号。因为令Pi=(d1(xi+1)－d2(xi+1))dx，则有为了有效地计算决策函数Pi，我们需要建立一个关于

Pi的递推公式。由Pi的定义可知为了确定决策函数Pi的初值P1，只需将直线的起点坐

标(xs，ys)代入Pi的表达式中，并注意到0≤m≤1的假设，则有

P1=2dy－dx

综上所述，满足条件0≤m≤1的直线的Bresnham算法的步骤如下：

Step1初始化：

dx=xe－xs，dy=ye－ys，x=xs，

y=ys，P=2dy－dx；

Step3算法结束。

Brsenham算法的程序实现如下：

#include<stdio.h>

#include<graphics.h>

voidline_BRES(intxs，intys，intxe，intye，intc){

intdx=xe-xs，dy=ye-ys，x=xs，y=ys；

inttwoDX=2*dx，twoDY=2*dy，P=2*dy-dx；

setPixel(x，y，Color)；

while(x<xe){

if(P>0){y++；P-=twoDX；}

x++；

P+=twoDY；

setPixel(x，y，c)；

}

}下面给出利用Bresenham算法画连接P0(0，0)和P1(5，2)两点的直线段的离散化结果，其结果如图3.4所示。

上面讨论的只是0≤m≤1的情形，考虑到xy平面各种八分和四分区域间的对称性，可以知道Bresenham算法对于任意斜率的直线具有通用性。对于斜率为正且大于1的直线，即dy>dx>0，只要变换x和y的地位，即沿y方向以单位步长步进并计算最接近直线的x值；若dy<0或dx<0，那么程序中的操作y++或x++则变成y－－或x－－。图3.4Bresenham算法实例一般情况下，任意直线的Bresenham算法为：

#include<stdio.h>

#include<graphics.h>

voidBRES_line(intxs，intys，intxe，intye，intc)

{

intdx=abs(xe-xs)，dy=abs(ye-ys)，i，x=xs，y=ys；inttwoDX=2*dx，twoDY=2*dy，P=2*dy-dx；

ints1，s2，interchange=0，temp；

if(xe-xs>=0)

s1=1；

else

s1=-1；

if(ye-ys>=0)

s2=1；

else

s2=-1；

if(dy>dx)/*按照直线的斜率交换dx和dy*/

{

temp=dx；

dx=dy；

dy=temp；

interchange=1；

}

for(i=0；i<=dx；i++)

{

setPixel(x，y，c)；

if(P>0)

{if(interchange)

x+=s1；

else

{y+=s2；

P-=twoDX；

}

}

if(interchange)

y+=s2；

else

x+=s1；

P+=twoDY；

}

}

Bresenham算法的优点有：

(1)不计算直线的斜率，因此不做除法运算。

（2）不用浮点数，只用整数。

（3）只做整数的加法和减法运算，而乘2运算可以用移位操作实现。

（4）运算速度快，便于硬件实现。通过对Bresenham算法进一步优化，减少算法中确定像素点的判定次数，即可得到增强的Bresenham算法——双步算法，该改进是由Wu和Rokne于1987年给出的。

Bresenham算法采用整数运算，由点(xi，yi)计算出(xi+1，yi+1)，算法首先确定线段的斜率，再继续在每一步中，通过判定函数在两个可选的像素点中选出一个。双步算法则在每一步都通过判定函数求得一对像素点而不只是一个像素点，如此继续直至到达线段的终点。对当前求得的像素点来说，随后可能出现的一对像素点只有图3.5所示的四种情况。图3.5双步算法中像素点的选择

Wu证明对于一条线段，图案1和图案4不会同时出现。当线段斜率大于1/2，图案1不会出现；当斜率小于1/2时，图案4不会出现。因此，通过测试斜率，选择将限定于1、2、3或2、3、4三种图案中的一个。下面考察当斜率在0到1/2之间的情形，此时可能出现的图案是图案1、图案2和图案3。为了确定像素点对，我们需要在图案1、图案2、图案3中做出决定。判定变量P

置初值P=4dy－dx。于是每一次增量测试以是否P<0确定是否使用图案1，即选择像素点：(xi+1，yi)，(xi+2，yi)。如果P大于或等于0，则必须在图案2和图案3之间做出选择。这是一个简单的测试：当P<2dy时选取图案2，即选择像素点：(xi+1，yi)，(xi+2，yi+1)。否则，选取像素点：(xi+1，yi+1)，(xi+2，yi+1)。为了有效地计算判定函数，同样需要建立关于P的递推公式：双步算法的参考代码如下：

voidline_DoubleStep(intxs，intys，intxe，intye，intColor)

{/*设0≤m≤1/2*/

intdx=xe-xs，dy=ye-ys，current_x=xs，y=ys；intincr_1=4*dy，incr_2=4*dy-2*dx，

P=4*dy-dx，cond=2*dy；

setPixel(current_x，y，Color)；

while(current_x<xe){

if(d<0){

setPixel(current_x+1，y，Color)；

setPixel(current_x+2，y，Color)；

P+=incr_1；

}

elseif(d<cond){

setPixel(current_x+1，y，Color)；

setPixel(current_x+2，y+1，Color)；

P+=incr_2；y++；

}

else{

setPixel(current_x+1，y+1，Color)；

setPixel(current_x+2，y+1，Color)；

P+=incr_2；y++；

}

current_x+=2；

}

}此外，还有利用中点法则进行直线绘制的中点算法，其与Bresenham算法的区别在于构造判定函数方法的不同。尽管如此，中点算法与Bresenham算法最终推导得到的判定函数递推公式和初值表达形式却是完全相同的。中点法是由Pitteway于1967年提出的，VanAken和另外的一些研究人员于1984年对其进行了一些改进。在生成直线的过程中，需另外考虑直线端点的顺序问题，即画一条从(xs，ys)到(xe，ye)的直线是否和画一条从(xe，ye)到(xs，ys)的直线能够生成相同的像素序列。从数学的角度来讲，画出的线应该与线的端点顺序无关。出现像素选择依赖于线的方向的惟一情况是线正好穿过两像素中间而决策函数是0。此时，从左向右扫描时会选择当前像素右侧的像素，根据对称性，如果是从右向左扫描，则选择的是当前像素左侧的像素，而这样选择的像素就比从左向右扫描时所选择的相应像素在y方向上高出一个单位。因此，在从右向左扫描时，当决策函数为0时应该调整为选择当前像素左下位置的像素。

3.2圆的生成算法

圆是最基本的图形之一，许多种场合都能用到它。因此，图形软件包都包含有生成圆和圆弧的程序，故生成圆的算法也很多。

圆心在(xc，yc)，半径为R的圆的方程是

(x－xc)2+(y－yc)2=R2

显然，利用该方程沿x轴从xc－R到xc+R以单位步长步进计算出对应的y值，即可得到圆周上每点的y值：但这并非是最好的算法。该算法每步包含了大量的计算，且所画像素沿圆周分布不均匀。另外，|x－xc|越大，对应生成圆周上的点之间的弧长也就越大。我们可以在圆的斜率绝对值大于1后，交换x和y来调整间距。这样一来增加了所需的计算量和处理过程。另一种消除不等间距的方法是使用圆的极坐标方程：

x=xc+Rcosθ，y=yc+Rsinθ

这种方法计算圆周上的点又涉及到三角运算，同样增加了计算量。3.2.1生成圆的Bresenham算法

Bresenham算法是画圆的最有效的算法之一。不失一般性，设要画圆的圆心在坐标原点(0，0)，半径为R。我们这里来讨论第一象限的上半部的八分之一圆弧的生成过程，即图3.6中的圆弧AB。如果要生成整圆，只需在显示圆弧AB上任一点(x，y)的同时，显示圆周上的另外七个点(x，－y)，(－x，y)，(－x，－y)，(y，x)，(y，－x)，(－y，x)和(－y，－x)。图3.6圆的对称性现在，从点(0，R)开始顺时针生成八分之一圆周AB。在这种情况下，x每步增加1，即xi+1=xi+1，相应的yi+1则有两种选择：yi+1=yi或yi－1。选择的原则是考察精确值y是靠近yi还是靠近yi－1(图3.7)。图3.7yi+1的选择准则设Rs满足方程：那么，以坐标原点为圆心，Rs为半径做圆弧S，上式表明点(xi+1，yi)和(xi+1，yi－1)到圆弧S的距离是相等的。因此，S可作为分界线。当圆在S上方时，应选yi+1=yi；当圆在S下方时，应选yi+1=yi－1(图3.7)。下面建立判断圆是在S上方或下方的决策函数。

令显然，di是R的递减函数。当R=Rs时，di=0；当R>Rs时，圆在S的上方，此时di<0；当R<Rs时，圆在S的下方，此时di>0。由此，我们得到决策函数di。若di<0，则yi+1=yi；否则，yi+1=yi－1。接下来的问题是如何快速地计算决策函

数di。

已知x1=0，y1=R，所以因为所以基于上述推导，生成圆的Bresenham算法的步骤如下：

Step3若x=y，画像素点(x，y)；

Step4算法结束。

下面给出利用Bresenham算法画圆心为O(0，0)，半径为R=10的八分之一圆弧离散化结果，如图3.8所示。图3.8Bresenham算法画圆实例生成圆的Bresenham算法程序如下：

#include<stdio.h>

#include<graphics.h>

voidCircle_BRES(intxc，intyc，intRadius，intc){intx=0，y=Radius，d=3-2*Radius；

while(x<y)

{Plot_Circle_Point(xc，yc，x，y，c)；

If(d>=0)

{d+=4-4*y；

y--；

}

d+=4*x+6；

x++；

}

if(x==y)

Plot_Circle_Point(xc，yc，x，y，c)；

}子函数Plot_Circle_Point(xc，yc，x，y，c)的程序代码如下：

voidPlot_Circle_Point(intxc，intyc，intx，inty，intc)

{

setPixel(xc+x，yc+y，c)；

setPixel(xc+x，yc-y，c)；

setPixel(xc-x，yc+y，c)；

setPixel(xc-x，yc-y，c)；

setPixel(xc+y，yc+x，c)；

setPixel(xc+y，yc-x，c)；

setPixel(xc-y，yc+x，c)；

setPixel(xc-y，yc-x，c)；

}图3.9画圆中点算法3.2.2生成圆的中点算法

Bresenham算法是画圆的最有效的算法之一，其效率要高于基于圆的隐式方程和极坐标方程的算法。对于圆心坐标和半径为整数的情况，运用中点准则可建立一个类似的算法，它能产生相同的一组优化的像素。这里仍然考虑第一象限的上半部的八分之一圆弧的生成过程，并利用圆的对称性画出圆上其余的所有点。与画直线的中点算法相似，这里所用的方法是：在2个像素之间的中点处给出一判定函数，并据此在2个像素中选择最靠近圆的那个像素。如图3.9所示，设函数F(x，y)=x2+y2－R2。对于圆上的点，此函数的值为0；对于圆内的点，函数值为负；对于圆外的点，函数值则是正的。这样，如果像素E和SE的中点M在圆外，则SE更靠近圆。相反，如果中点在圆内,则E更靠近圆。与画直线类似，我们选择像素的依据是判定函数d的值，即函数F(x，y)在中点处的值：如果di<0，就选择像素E，并将当前中点的x坐标增加一个单位来得到下一个中点，从而得到：显然，di+1=di+(2xi+3)，可得增量：ΔE=2xi+3。

如果di≥0，就选择像素SE，而下一个中点是将当前中点的x坐标增加一个单位，y坐标减少一个单位，从而得到：最后还需要确定判定函数d的初值。由于限定该算法处理的圆的半径为整数，并只画八分之一圆弧，因此，圆的起始像素是(0，R)，而下一个中点的位置是(1，

R－1/2)，因此实现该算法的程序结构与画直线的算法很相似：

voidCircle_Midpoint(intradius，intColor)

{

intx，y；

floatd；

x=0；y=radius；d=5.0/4-radius；

Plot_Circle_Point(0，0，x，y，Color)；

while(x<y){

if(d<0){d+=x*2.0+3；}

else{d+=(x-y)*2.0+5；y--；}

x++；

PlotCirclePoint(0，0，x，y，Color)；

}

}上述算法的不足是由于判定函数d的初值是浮点数，因此算法必须做浮点数的算术运算。我们希望有一个效率更高的且只进行整数运算的算法。为此，定义一个新的判定函数：h=d－1/4。这样在初始化时，h=1－R，而条件d<0变成了h<－1/4。由于h的初值是整数，且其相应的增量也是整数，因此可将条件h<－1/4改为h<0。这样算法就变成了关于h的只进行整数运算的形式。为了与画直线算法保持一致性，仍然用d表示决策函数。改进后的算法如下所示：

voidCircle_Midpoint_Integer(intradius，intColor)

{

intx，y，d；

x=0；y=radius；d=1-radius；

Plot_Circle_Point(0，0，x，y，Color)；

while(x<y){

if(d<0){d+=x*2+3；}

else{d+=(x-y)*2+5；y--；}

x++；

Plot_Circle_Point(0，0，x，y，Color)；

}

}图3.10给出利用中点算法画圆心为O(0，0)，半径为R=10的八分之一圆弧数值结果。

对上述增量计算方法进一步拓展可改善画圆的中点算法效率。由于任意一个多项式都可以按增量方式进行计算，即利用了差分算法。差分的基本思想是计算函数在其相邻两个点上的值以及这两个值的差。对于中点画圆算法，在当前的迭代中，如果选择了E，则估值点从(xi，yi)变化到(xi+1，yi)。显然，在点

(xi，yi)处的一阶差分为ΔEold=2xi+3。因此，在点(xi+1，yi)处的一阶差分为ΔEnew=2(xi+1)+3，其二阶差分为ΔEnew－ΔEold=2。类似地，在点(xi，yi)处，ΔSEold=2xi－2yi+5；在点(xi+1，yi)处，ΔSEnew=2(xi+1)－2yi+5，因此二阶差分为ΔSEnew－ΔSEold=2。如果在当前的循环中选择了SE，则估值点从(xi，yi)变化到(xi+1，yi－1)。因此，在点(xi+1，yi－1)处的一阶差

分为ΔEnew=2(xi+1)+3，而二阶差分为ΔEnew－ΔEold=2。

同样，在点(xi+1，yi－1)处，ΔSEnew=2(xi+1)－2(yi－1)

+5，而相应的二阶差分ΔSEnew－ΔSEold=4。于是，改进后的算法包括以下几个步骤：①根据上次循环所计算的判定函数d的值的符号选择一个像素；②运用上次循环所计算的相关ΔE或ΔSE对判定函数d的值进行修改；③根据像素的移动情况，用前面计算的差分常量修改ΔE或ΔSE；④移动像素。差分ΔE或ΔSE使用起始像素进行初始化。改进后的程序如下所示：

voidCircle_Midpoint_Difference(intradius，intColor)

{

intx，y，d，deltaE，deltaSE；

x=0；y=radius；d=1-radius；deltaE=3；deltaSE=5-radius*2；

PlotCirclePoint(0，0，x，y，Color)；

while(x<y){

if(d<0){

d+=deltaE；deltaE+=2；deltaSE+=2；

}

else{

d+=deltaSE；deltaE+=2；deltaSE+=4；y--；}

x++；

Plot_Circle_Point(0，0，x，y，Color)；

}

}3.2.3生成圆的正负法

设要绘制的圆的圆心在(xc，yc)，半径为R，令

Fcircle(x，y)=(x－xc)2+(y－yc)2－R2

则圆将平面分为三个区域：我们以第一象限的四分之一圆弧为例，说明正负法的原理。取P0(x0，y0)=(xc，yc+R)，求得点Pi(xi，yi)后，

寻找Pi+1(xi+1，yi+1)的原则是：当Fcircle(xi，yi)≤0时，xi+1=xi+1，yi+1=yi；当Fcircle(xi，yi)>0时，xi+1=xi，yi+1=yi－1。因此，由Pi(xi，yi)和Fcircle(xi，yi)求Fcircle(xi+1，yi+1)的递推公式为显示初值点为(xc，yc+R)取在圆周上，则决策函数的初值为Fcircle=0。下面是基于上述递推公式设计的生成圆的实现程序：

#include<stdio.h>

#include<graphics>

voidCircle_PNM(intxCenter，intyCenter，int

Radius，intc)

{

intx=xCenter，y=yCenter+Radius；

intf=0；

while(y>yCenter)

{

setPixle(x，y，c)；

if(f>0)

{

f+=2*(yCenter-y)+1；

y--；

}

else

{

f+=2*(x-xCenter)+1；

x++；

}

}

if(y==yCenter)setPixel(x，y，c)

}3.2.4生成圆的多边形逼近法

方法1（基于圆的极坐标表示）:

设圆的内接多边形的第i个顶点是Pi(xi，

yi)，CPi的幅角是θi，则：设多边形每条边所对应的圆心角为α，那么下一个顶点Pi+1(xi+1，yi+1)的坐标是：采用矩阵表示，则有式（3.7）可用于高速绘图机绘图。用两个微处理器作管道式处理，前一个计算正多边形的顶点，后一个只生成直线。如果不考虑绘图机笔架运动的加速度的限制，绘制半径为R的圆几乎和绘一条长为2πR的直线花的时间同样。该方法亦可用于椭圆内接多边形的计算。设椭圆的长短半轴分别为a和b，中心点坐标为C(xc，yc)，对称轴平行于坐标轴，则该椭圆的参数方程是

x－xc=acosθ，y－yc=bsinθ

设椭圆的内接多边形的第i个顶点为Pi(xi，yi)，CPi的幅角是θi，其中：

xi－xc=acosθi，yi－yc=bsinθi

那么，第i+1个顶点Pi+1(xi+1，yi+1)的坐标满足：

xi+1－xc=acos（θi+α），yi+1－yc=bsin（θi+α）

由此可得(3.8)(3.9)上式便是计算椭圆的内接多边形顶点的递推公式。如果对由式（3.8）生成的椭圆作旋转β角或缩放变换，则要分别用变换矩阵如果两个变换同时都做，则变换矩阵为这两个矩阵的乘积T=TR·TS。这时，只要用TMT－1代替式（3.8）中的M，便可得到变换后的椭圆内接多边形的顶点坐标。在第五章中可以看到式（3.8）可由式（3.7）经过缩放变换求得。(3.11)图3.11式（3.10)的几何意义式（3.11）还可以写成更一般的形式：(3.12)其中k为常数。当k>1时，由其求出的点列{(xi，yi)}位于一支双曲线上。因而，式（3.12）可用于双曲线的绘制。3.2.5多边形逼近算法稳定性分析

这里对递推公式（3.7）作关于初始误差的稳定性分析。设在初始真值(x0，y0)上附加误差E0=(ex，ey)，此真值则变成为有误差的初值，即：在求解过程中，假设计算是精确的，因而假设真值(xi，yi)也满足式（3.7），即可令则有其中，矩阵它的特征值为λ1=cosα+isinα，λ2=cosα－isinα，所以存在二阶方阵U，使得UAU－1为对角阵，则：(3.14)利用递推公式（3.7）求圆的内接多边形的顶点时，为了减少计算工作量，可以以近似的方式计算三角函数cosα和sinα。例如，用Taylor级数的前n项来代替，cosα≈1，sinα≈α，这样近似后式（3.7）则成为：也可近似用这样则有：这两种方法均不能精确地求出圆内接多边形的顶点，α取得越小，误差就越小。3.2.6生成椭圆的正负法

下面我们仅讨论椭圆曲线的生成问题。

这种方法不失一般性，我们假定椭圆的中心在坐标原点，长半轴为a，短半轴为b，则椭圆的方程是：令Fellipse(x，y)=b2x2+a2y2－a2b2，则该函数具有以下

特性：因此，将函数Fellipse(x，y)作为正负法的决策函数。已知当前一个像素点(xi，yi)，下一个像素点(xi+1，yi+1)的选择依照决策函数，其规则如下：从(x1，y1)=(0，b)开始，依次对椭圆进行采样，绘制四分之一椭圆。显然

Fellipse(x1，y1)=0

即是决策函数的初值。为了快速求出决策函数值，我们建立决策函数的递推公式。

由于

Fellipse(xi+1，yi+1)=b2xi2+1+a2y2i+1－a2b2

分两种情况予以讨论。3.3多边形的扫描转换与区域填充

3.3.1多边形的扫描转换

1.什么是多边形的扫描转换

在光栅图像表示方法中，像素是构成图像的基本单位，如图3.12。图3.12图像的表示对于给定的图像，可以将它光栅化为一系列像素点的集合来表示，称之为光栅图形表示方法。当然也可以用矢量图形表示方法来表示同一图像，在矢量图形表示方法中，顶点和线是构成图像的两个主要要素，这里的线包括直线和曲线，通常它们都有显式的数学表达形式。一般情况下，这些线可以是曲线段，或者由Bézier曲线等复杂曲线构成，但更多情况下是由直线段构成的。因为曲线可以在特定误差范围内由一系列直线段逼近得到，这种情形下矢量图形的基本构成单位就变为多边形了。在计算机图形学中，多边形有两种表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来刻画多边形。这种方法直观、几何意义强、占用内存少、使用普遍。但由于它没有明确指出哪些像素点在多边形内，故不能直接用于面着色。

点阵表示是用位于多边形内的像素点的集合来刻画多边形。这种方法虽然失去了许多重要的几何信息，但便于运用帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形系统的基本问题之一就是扫描转换，根据图像的表示方法它可以分为两种情况。一种是光栅化过程，也就是将由围线构成的图像转换为由像素点构成的光栅图像，或者填充围线内部的区域，即区域填充。另一种是矢量化过程，包括将光栅图形表示为矢量图形，或者对图像

进行分割并检测其中的围线等。这一小节主要讨论多边形的扫描转换，即把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素点，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色。

2.逐点判断算法

实现多边形的扫描转换最简单的方法就是逐点判断，即逐个像素判断，以确定它们是否在多边形内，从而给出位于多边形内的像素集合。

确定一个点是否在多边形内一般用累计交点的方法。若从一点发出的射线与多边形边界的交点数目为奇数，则该点位于多边形内，否则该点位于多边形外。设P=p0p1…pnp0为一给定的多边形，序列p0p1…pnp0是多边形的顶点表示。设inside(P，x，y)是验证点(x，y)是否在多边形P内的布尔函数。当从(x，y)到(+∞，y)的射线与

P的交点个数是奇数时，该函数取值1，否则取值0。设PolygonColor是多边形P的颜色值，BackgroundColor为屏幕的背景色。

3.扫描线算法

1）区域的连贯性

设多边形P的顶点pi=(xi，yi)，i=0，1，…，n的纵坐标y的非递增序列为：

yi0，yi1，…，yin

(3.15)

即

yik≥yik+1，0≤k≤n－1

(3.16)这样，当yik>yik+1，0≤k≤n－1时，屏幕上位于

y=yik和y=yik+1两条扫描线之间的长方形区域（简记为

{yik，yik+1}）被多边形P的边分割成若干个梯形（三角形

可看做一底边长为0的梯形），它们具有以下性质：（1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰在多边形P的边上或在屏幕的边界上，如图3.13

所示。

（2）这些梯形可分为两类：一类位于多边形P的内部，另一类位于多边形P的外部。

（3）两类梯形在长方形区域{yik，yik+1}内相间排列，即相邻的两个梯形必有一个在P内，另一个在P外。

2）扫描线的连贯性

设e为整数，且yi0≥e≥yin，若扫描线y=e与多边形P的边pi－1pi相交，其交点横坐标记为xei。设

xei1，xei2，…，xeil

(3.17)

是扫描线y=e与P的边界各交点横坐标的递增序列，称为交点序列。那么，由区域的连贯性可知，交点序列具有下列性质：（1）l是偶数。

（2）在该扫描线上，只有区段(xeik，xeik+1)，k=1，3，5，…，l－1，位于多边形P内，而其余区段在多边形P外。

上述性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。

3）边的连贯性

设d=e－1满足条件yi0≥d≥yin，且位于扫描线y=d上的交点序列为

xdj1，xdj2，…，xdjh

(3.18)现考察交点序列（3.18）和（3.17）之间的关系。若

多边形P的边pr－1pr与扫描线y=e，y=d都相交，那么序列（3.17）和（3.18）中对应元素xer，xdr满足下列关系：(3.19)这样，运用公式（3.21）可直接由序列（3.18）求得序列（3.17）。

4）奇点处理

当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点。上述多边形的三种形式的连贯性都是基于这样的几何事实：每一条扫描线与多边形P的边界的交点个数是偶数（包括零）。但是，如果把每一奇点简单地记为一个交点，则交点个数可能出现奇数；同样，若将每一奇点都简单地记为两个交点，亦会导致反常的结果。因此，奇点必须按不同的情况区别对待。多边形P的顶点可分为两类：极值点和非极值点。如果(yi－1－yi)(yi+1－yi)<0，则称顶点pi(xi，yi)为P的非极值点，否则称为P的极值点。

为了在算法中统一处理多边形三种形式的连贯性，使每一条扫描线与P的边界的交点个数保持为偶数，规定当

奇点为P的极值点时，该点按两个交点计算，否则按一个交点计算。实际计算时，可在求交点以前，对多边形顶点中的非极值点进行预处理。即若Pi是非极值点，则将pi－1pi和pipi+1两边中位于扫描线y=yi上方的那条边在Pi处沿纵向截

取一单位长，如图3.14所示。这样可保证扫描线y=yi只和

pi－1pi、pipi+1两边中的一边相交，求得一个交点。图3.14非极值点的预处理

5）扫描线算法的数据结构

为了实现多边形P的扫描转换，首先对多边形P的顶点的纵坐标由大到小排序，得到一递减序列：

yi0，yi1，…，yin

取d=yin，容易求得扫描线y=d上的交点序列：

xdj1，xdj2，…，xdjh

这一序列由位于扫描线y=d上的多边形P的顶点组成。由上述序列开始即可根据多边形的边的连贯性和扫描

线的连贯性，按从下到上的顺序求得各扫描线的交点序列，并确定各扫描线上位于多边形P内的区段，最后将多边形P表示成点阵形式。此算法就是对多边形作扫描转换

的扫描线算法。边的分类表ET和边的活化链表AEL中的基本元素为多边形的边。边结点的结构如下：其中：ymax：边的上端点y坐标；

x：边的下端点x坐标，在AEL中表示边与扫描线的交点x坐标；

Δx：边的斜率的倒数；

next：指向下一条边的指针。边的分类表ET是按边的下端点纵坐标y对非水平边进行分类的指针数组(Y桶分类)。下端点的纵坐标y值等于i的边归入第i类，有多少条扫描线，就设多少类。同一类中，各边按x值(x值相等时，按Δx的值)递增的顺序排列成行。例如，对于多边形P=［p0p1…p6p0］=［(2，5)，

(2，10)，(9，6)，(16，11)，(16，4)，(12，2)，(7，2)，(2，5)］（图3.15），其对应的边的分类表ET如图3.16所示。这里已对非极值点p0

，

p4作了预处理，即

对边e1、e4而言，下顶点的y坐标分别为6和5，e6作为水平边不参与分类。图3.15多边形P=［P0P1…P6P0图3.16多边形的边分类表ET边的活化链表AEL是由与当前扫描线相交的所有多边形的边组成的一个链表。它记录了多边形沿扫描线的交点序列，并且根据边的连贯性（式(3.19)）不断地刷新交点序列。例如，图3.15所给的多边形对应于不同扫描线，其AEL如图3.17所示。图3.17边的分类表

6）算法步骤

建立了多边形的分类表ET后，扫描线算法的实现步骤如下：

Step1(扫描线初始化)取扫描线纵坐标y的初始值为ET中非空元素的最小序号。(对上述的多边形，y=2)；

Step2(AEL初始化)将边的活化链表AEL置为空表；Step3按从下到上的顺序对纵坐标值为y的扫描线执行以下操作，直到边的分类表ET和边的活化链表AEL为空表为止。

（1）若边的分类表ET中第y类元素非空，则将属于该类的所有边从ET中取出并插入到边的活化链表AEL中。AET中的各边按照x值(当x值相等时，按Δx值)递增的顺序排序。（2）若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两配对。即第1、2边为一对，第3、4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内。依次对这些区段上的像素点按多边形颜色着色。

（3）将边的活化链表AEL中满足条件ymax=y的边删去。（4）将边的活化链表AEL中剩余的每一条边的x域累加Δx，即x=x+Δx。

（5）将当前扫描线的纵坐标值y累加1，即y=y+1。

7）程序实现

若采用C语言，那么边结点的数据类型可说明如下：

structtEdge{

intyUpper；

floatxIntersect，dxPerScan；

structtEdge*next；

}Edge；

#include<stdio.h>

#inclide<graphics.h>

voidinsertEdge(Edge*list，Edge*edge)/*链表插入*/

{Edge*p，*q=list；

p=q->next；

while(p!=NULL)

{if(edge->xIntersect<p->xIntersect)

p=NULL；

else

{q=p；

p=p->next；

}

}

edge->next=q->next；

q->next=edge；

}

intyNext(intk，intcount，int*y)

/*求下一条非水平边的y坐标*/

{intj；

if((k+1)>(count-1))

j=0；

else

j=k+1；

while(y［k］==y［j］)

if((j+1)>(count-1))

j=0；

else

j++；

return(y［j］)；

}

voidmakeEdgeRecord(intxLower，intyLower，intxUpper，intyUpper，intyComp，

Edge*edge，Edge*edges［］)/*建立边结点*/

{edge->dxPerScan=(float)(xUpper-xLower)/(yUpper-yLower)；

edge->yUpper=yUpper；

if(yLower>yComp)

{edge->yLower=yLower+1；

edge->xIntersect=xLower+edge->dxPerScan；

}

else

edge->xIntersect=xLower；

insertEdge(edges［yLower］，edge)；

}

voidbuildEdgeList(intcount，int*x，int*y，Edge*edges［］)/*建立边表*/

{Edge*edge；

intx1，y1，x2，y2；

inti，yPrev=y［count-2］；

x1=x［count-1］；y1=y［count-1］；

for(i=0；i<count；i++)

{x2=x［i］；y2=y［i］；

if(y1!=y2)/*非水平边*/

{edge=(Edge*)malloc(sizeof(Edge))；

if(y1<y2)

makeEdgeRecord(x2，y2，x1，y1，yNext(i，count，y)，edge，edges)；

else

makeEdgeRecord(x1，y1，x2，y2，yPrev，edge，edges)；

}

yPrev=y1；

x1=x2；y1=y2；

}

}

voidbuildActiveList(intscan，Edge*active，Edge*edges［］)/*建立活化链表*/

{Edge*p，*q；

p=edges［scan］->next；

while(p)

{q=p->next；

insertEdge(active，p)；

p=q；

}

}

voidfillScan(intscan，Edge*active)/*填充当前扫描线*/{Edge*p1，*p2；

inti

p1=active->next；

while(p1)；

{p2=p1->next；

for(i=p1->xIntersect；i<p2->xIntersect；i++)

setPixel(i，scan，PolygonColor)；

p1=p2->next；

}

}

voiddeleteAfter(Edge*q)/*删除已处理过的边*/

{Edge*p=q->next；

q->next=p->next；

free(p)；

}

voidupdateActiveList(intscan，Edge*active)/*修改活化链表*/

{Edge*q=active，*p=active-next；

while(p)

if(scan>=p->yUpper)

{p=p->next；

deleteAfter(q)；

}

else

{p->xIntersect=p->xIntersect+p->dxPerScan；

q=p；

p=p->next；

}

}

voidresortActiveList(Edge*active)/*活化链表排序*/

{Edge*q，*p=active->next；

while(p)

{q=p->next；

insertEdge(active，p)；

p=q；

}

}

voidscanFillPolygon(intcount，int*x，int*y)/*多边形扫描转换*/

{Edge*edges［YMAX］，*active；

inti，scan；

for(i=0；i<YMAX；i++)

{edges［i］=(Edge*)malloc(sizeof(Edge))；

edges［i］->next=NULL；

}

buildEdg