研究生计算机图形学

3.1直线的生成算法

在点阵设备中，直线是用一系列靠近直线的像素点来逼近的。图3.1.1是像素点逼近直线的几个例子(用小圆点代表逼近的像素点)。从图中可见，只有当直线是水平的(如AB)、垂直的(如AC)或与水平线成45°(如AD)时，由像素点拼成的图形才是真正的直线，其他位置的直线(如AE)都呈阶梯形，这种现象称为阶梯效应。研究直线的生成就要减少这种阶梯效应。对生成直线的要求是：直线要直(即逼近程度好)、起点和终点位置要准确(否则会在直线连接处出现间隙)、线上各点亮度要均匀(即要求点的密度要均匀，否则给人一段亮一段暗的感觉)、画线速度要快(与直线生成算法和计算机速度均有关)。第1页/共152页第一页，共153页。图3.1.1直线的像素化(VRC变换)第2页/共152页第二页，共153页。

点阵设备中直线的生成方法主要有：对称DDA法、简单DDA法、Bresenham算法、中点画线法等，每种方法各有优缺点。矢量设备中直线的生成方法主要有：逐点比较法、正负法、Bresenham算法等。直线的生成算法是在设备坐标系(如屏幕坐标系、绘图机坐标系等)中进行的，要求直线已知点即起点和终点的坐标为设备坐标。若已知点坐标为世界坐标则要换算成设备坐标。第3页/共152页第三页，共153页。1.DDA法

DDA法即数字微分分析法(DigitalDifferentialAnalyzer)。我们知道，直线微分方程为这里(xa,ya)、(xb,yb)为直线起点和终点坐标。将上式数字化(即像素化)，便可得到下面的递推公式：第4页/共152页第四页，共153页。

当ε取值不同时，便形成对称DDA法和简单DDA法。下面以屏幕上生成直线为例来介绍这两种算法。

(1)对称DDA法。对称DDA法取ε=2-n，n由下面关系式决定：

2n-1≤max(|Δx|,|Δy|)≤2n,n为正整数第5页/共152页第五页，共153页。计算点的公式为

上式中加0.5是为了减少误差而采用的“四舍五入法”，xi、yi、xi+1、yi+1是计算坐标，而xis、yis是显示坐标，即像素点的位置坐标。第6页/共152页第六页，共153页。【例1】用对称DDA法在起点A(2，1)和终点B(12，7)之间生成一段直线。求解的第一步是计算初值Δx,Δy,n。这里Δx=10,Δy=6,n=4。第二步按递推公式循环计算点的坐标，并取整显示。表3.1.1是本例的循环计算过程。图3.1.2是其屏幕显示结果。第7页/共152页第七页，共153页。表3.1.1对称DDA法计算过程第8页/共152页第八页，共153页。图3.1.2对称DDA法生成的直线第9页/共152页第九页，共153页。

对称DDA法生成的直线比较精确，像点位置偏离直线不超过半个像素。逻辑上也比较简单，用2的负指数幂作为ε，意味着把存放Δx和Δy的寄存器通过移位操作就可得到点与点之间的坐标增量εΔx、εΔy，而不用除法计算，计算直线上每一点只用两次加法即可实现。对称DDA法适合用硬件来实现，当然也可用软件来实现。第10页/共152页第十页，共153页。(2)简单DDA法。简单DDA法取 。计算点的公式为第11页/共152页第十一页，共153页。图3.1.3简单DDA法生成的直线第12页/共152页第十二页，共153页。

简单DDA法是按Δx,Δy绝对值较大的方向走步的，在这个方向上，每步走一个像素，然后再确定另一个方向的走步。简单DDA法生成直线的精度同对称DDA法，但它在求一个点时要做两次除法以决定坐标增量值。简单DDA法不适合硬件实现，只适合于软件处理。第13页/共152页第十三页，共153页。2.Bresenham直线生成算法由Bresenham提出的算法最初是为数控绘图机设计的，后来被广泛用于光栅扫描图形显示器。Bresenham直线生成算法实际上也是简单DDA算法，即在某一计长方向上，每次必变化一个单位步长或一个像素单位，另一方向上的变化量可通过计算得到。这种算法只用到整型数计算，不必作四舍五入操作，而且在计算判别式时，计算量很小，因而得到广泛的应用。下面我们介绍在光栅扫描图形显示器上实现的这种算法。第14页/共152页第十四页，共153页。

假设要生成的直线起点为(xa,ya)、终点为(xb,yb)，经变换后直线起点为(0，0)、终点为(Δx,Δy)，其中Δx=xb-xa,Δy=yb-ya。此时直线方程可简化为

先考虑直线的斜率在0~1之间的情况。如图3.1.4所示，设Pi-1(xi-1,yi-1)是已确定的逼近像素点，令Pi-1的坐标为(r,q),Si(r+1,q)、Ti(r+1,q+1)是靠近直线的两个像素点，现在要决定下一个像素是Si还是Ti。由图中可直观地看出：若s<t,则Si比较靠近直线，应选Si;

若s≥t，则应选Ti。第15页/共152页第十五页，共153页。第16页/共152页第十六页，共153页。现在我们推导由Pi-1确定下一个像素点的递推关系式。由于则即第17页/共152页第十七页，共153页。由于此时Δx为正，故我们可以用Δx(s-t)的正、负作为选择Si和Ti的标准。若令di=Δx(s-t)，则有di=2(r·Δy-q·Δx)+2Δy-Δx将r=xi-1，q=yi-1代入，于是di=2xi-1·Δy-2yi-1·Δx+2Δy-Δx将式(3-1)中的i用i+1替换，便有di+1=2xi·Δy-2yi·Δx+2Δy-Δx用di+1减去di得di+1-di=2Δy(xi-xi-1)-2Δx(yi-yi-1)(3-1)第18页/共152页第十八页，共153页。由于此时走步方向为x方向，即xi-xi-1=1，重写上式得di+1=di+2Δy-2Δx(yi-yi-1)

若di≥0，即s≥t，则选Ti,此时

yi=yi-1+1 Di+1=di+2(Δy-Δx)

若di<0,即s<t，则选Si，此时

yi=yi-1 di+1=di+2Δy

这样，我们就有了一个递推的方法，即由前一个di计算出下一个di+1，并对Si及Ti进行选择。di的初值d1可由式(3-1)求出，将i=1,x0=y0=0代入得d1=2Δy-Δx(3-3)(3-4)第19页/共152页第十九页，共153页。

根据以上分析，我们可得到斜率在0~1之间的Bresenham直线生成递推计算公式：(3-5)第20页/共152页第二十页，共153页。

上式中的坐标x0、y0、xi-1,yi-1、xi,yi均为以直线起点为坐标原点的局部坐标系下的坐标。当斜率大于1时，只需将x,y交换计算即可(此时以y方向作为走步方向，每次增加一个像素单位)，显示时再将x,y换过来。对于任意走向的直线，在用式(3-5)计算时，Δx,Δy要用绝对值代入，并根据Δx,Δy的正、负号决定x,y方向增量的正负。第21页/共152页第二十一页，共153页。3.生成直线的逐点比较法逐点比较法就是在输出直线或圆弧的过程中，每走完一步就与理论的直线或圆弧进行比较，确定当前点是在线或弧上，还是在线或弧的一侧，然后再决定下一步的走向，这样一步一步地逼近所画直线或圆弧。第22页/共152页第二十二页，共153页。

逐点比较法是针对笔式绘图机提出的。根据绘图机的结构原理及数字控制原理，绘图机的笔架可能的移动方向(称为走步方向)有八个：+X、-X、+Y、-Y、+X+Y、-X+Y、-X-Y、+X-Y。其中+X、-X、+Y、-Y四个走步方向是一般绘图机都提供的，称为基本走步方向。可见，绘图机的基本绘图元素是与走步方向相对应的小直线段。绘图机所画的一般直线和曲线，实际上是由许多小直线段所组成的折线来逼近的。根据所画图线的已知条件(如直线两个端点坐标，圆弧的起点、终点和圆心等)计算画图所需要的一系列中间点(即折线的端点)的坐标，称为插补运算。根据插补对象不同，插补运算有直线插补、圆弧插补和抛物线插补等，前两种是基本的插补运算。插补运算可用软件或硬件实现，不少绘图机采用插补器(或称线发生器、弧发生器)来完成插补运算，目的在于提高图线生成速度。逐点比较法可用于插补运算。第23页/共152页第二十三页，共153页。

下面介绍逐点比较法。为叙述简捷并减少计算量，算法中建立了局部坐标系，将有关坐标转化为局部坐标计算。形成局部坐标的方法很简单，对直线而言，各点坐标减去起点坐标就得到每点的局部坐标，直线的起点就是局部坐标系的原点；对圆弧而言，各点坐标减去圆心坐标就得到每点的局部坐标，圆心就是局部坐标系的原点。直线的生成运算按直线所在的象限进行。第24页/共152页第二十四页，共153页。

若画第一象限的直线OA，如图3.1.5所示，起点为O(0，0)，终点为A(xa,ya)，设绘图笔当前的位置为K(xk,yk)，这里坐标均为局部坐标。点K相对于直线OA的位置有三种情况：点K在OA上方，点K在OA上以及点K在OA下方。为判断点K与OA的相对位置，引入偏差函数Fk。Fk=xayk-xkya当K在OA上时，Fk=0;K在OA上方时，Fk>0;K在OA下方时，Fk<0。第25页/共152页第二十五页，共153页。第26页/共152页第二十六页，共153页。

对第一象限内直线的生成规定如下：当Fk≥0时，绘图笔从当前位置沿+X方向走一步，记作+Δx；当Fk<0时，绘图笔从当前位置沿+Y方向走一步，记作+Δy；在绘图笔到达新的位置时，应计算出新位置的偏差，为判断绘图笔下一步走向作准备。绘图笔走+Δx时，新点坐标为xk+1=xk+1,yk+1=yk这时新点偏差为Fk+1=xayk+1-xk+1ya=xayk-xkya-ya=Fk-ya第27页/共152页第二十七页，共153页。

绘图笔走+Δy时，新点坐标为xk+1=xk,yk+1=yk+1这时新点偏差为Fk+1=xayk+1-xk+1ya=xayk+xa-xkya=Fk+xa

根据新偏差Fk+1的正、负号再确定绘图笔的下一步走向，这样逐步进行，直到绘图笔到达直线的终点为止。终点判断可由X及Y向总走步数J(J=|xa|+|ya|)来控制，每走一步J减去1，当J=0时即到达终点。第28页/共152页第二十八页，共153页。

对其他象限内直线段生成计算走步方向的规定如图3.1.6所示。偏差的递推计算均按以下两式进行：当沿X方向走步时，Fk+1=Fk-|ya|；当沿Y方向走步时，Fk+1=Fk+|xa|。第29页/共152页第二十九页，共153页。图3.1.6各象限内直线生成的走步方向第30页/共152页第三十页，共153页。【例2】用逐点比较法画直线OA，其起点为O(0，0)，终点为A(5，3)。计算从起点开始，总走步数J=8，起点处F0=0，走步方向的规定按第一象限进行。算法的计算结果如图3.1.7所示，其过程列于表3.1.2。图3.1.7逐点比较法生成直线的图例第31页/共152页第三十一页，共153页。表3.1.2直线生成的递推计算过程第32页/共152页第三十二页，共153页。3.2圆弧与椭圆弧的生成算法

1.角度DDA法产生圆弧若已知圆心坐标为(xc,yc)，半径为R，则以角度t为参数的圆的参数方程可写为

当t从0变化到2π时，上述方程所表示的轨迹是一整圆；当t从起始角ts变化到终止角te时，则产生一段圆弧。由于我们定义角度的正方向是逆时针方向，所以圆弧是由ts到te逆时针画圆得到的。第33页/共152页第三十三页，共153页。

若给定圆心坐标(xc,yc)，半径R及起始角ts和终止角te，要产生从ts到te这段圆弧的最主要问题是离散化圆弧，即用小直线段逼近圆弧，这就需要求出从ts到te所需运动的总步数n。可令其中，dt为角度增量，即每走一步对应的角度变化。问题是如何选取dt?通常是根据半径R的大小来给定dt的经验数据。在实际应用中，应对速度和精度的要求加以折衷，并适当调整dt的大小。如果用户给定的te<ts，则可令te=te+2π，以保证从ts到te逆时针画图。如果画整圆，则令n=2π/dt+0.5。为避免累积误差，最后应使t=te，强迫止于终点。第34页/共152页第三十四页，共153页。

若给定画圆弧的条件为圆周上三点P1(x1,y1),P2(x2,y2),P3(x3,y3)，则利用几何关系和三角关系不难求出圆心(xc,yc),半径R及起始角ts和终止角te，要注意将ts,te规范至均大于0且ts<te,并由ts逆时针画弧至te(若连接P1,P2,P3构成的两矢量叉乘为负，则说明顺时针画弧，此时应将P1,P3交换，就可保证逆时针画弧)。第35页/共152页第三十五页，共153页。2.Bresenham画圆算法算法中以圆心为坐标原点建立了局部坐标系。先考虑产生第一象限的八分之一圆弧，即从S(0，R)到 之间的45°圆弧，如图3.2.1所示。设Pi-1(xi-1,yi-1)为已确定的逼近像素点。现在，当xi=xi-1+1时，必须决定是Ti(xi-1+1,yi-1-1)还是Si(xi-1+1,yi-1)更接近实际的圆弧。令D(Si)=［(xi-1+1)2+y2i-1］-R2

D(Ti)=［(xi-1+1)2+(yi-1-1)2］-R2

第36页/共152页第三十六页，共153页。

它们分别代表从圆心(坐标原点)到Si或到Ti的距离平方与半径平方的差。如果|D(Si)|≥|D(Ti)|，则Ti比Si更接近实际的圆弧，应选Ti;如果|D(Si)|<|D(Ti)|，则Si比Ti更接近实际的圆弧，应选Si。令di=|D(Si)|-|D(Ti)| (3-6)于是，di≥0时，应选Ti;di<0时，应选Si。式(3-6)的计算要用到绝对值，故比较麻烦。参照图3.2.2实际的圆弧穿过栅格的各种可能的形式(从A到E)，可以简化式(3-6)的计算。第37页/共152页第三十七页，共153页。图3.2.1Bresenham算法与八分之一圆弧第38页/共152页第三十八页，共153页。图3.2.2Bresenham画圆算法的判别点第39页/共152页第三十九页，共153页。对于情况C，因为Si在圆外，我们有D(Si)>0，同时因为Ti在圆内，故有D(Ti)<0。于是式(3-6)可改写为di=D(Si)+D(Ti) (3-7)即可直接根据式(3-7)中di的正、负来选择Ti或Si。对于情况A和B，由于|D(Si)|<|D(Ti)|，按式(3-6)应选Si。若按式(3-7)计算，由于Ti在圆内，有D(Ti)<0;Si在圆内(情况A)或圆上(情况B)，有D(Si)≤0，故有di<0，也选Si。可见式(3-7)对情况A和B也是适用的。经过类似地分析可知，式(3-7)对于情况D和E也是适用的。第40页/共152页第四十页，共153页。

因此，我们可以用式(3-7)代替式(3-6)进行判断计算。下面的工作是要推导一个递推公式，以简化di的计算。由式(3-7)及D(Si)、D(Ti)的表达式有用i+1代替上式中的i，得用di+1减去di,得第41页/共152页第四十一页，共153页。若di≥0，则选Ti，此时(3-9)若di<0，则选Si，此时(3-10)第42页/共152页第四十二页，共153页。di的初值d1可由式(3-8)求出，将i=1,x0=0,y0=R代入之，得

显然，式(3-9)、式(3-10)、式(3-11)的计算量是很小的，因此效率较高。(3-11)第43页/共152页第四十三页，共153页。

根据以上分析，我们可以得到Bresenham算法产生八分之一圆弧的递推计算公式：第44页/共152页第四十四页，共153页。3.生成圆弧的逐点比较法圆弧的生成按圆弧所在的象限以及画弧方向(逆时针还是顺时针)进行。若圆弧跨过几个象限，应按象限分段生成。若画第一象限的圆弧AB，如图3.2.4所示，起点为A(xa,ya)，终点为B(xb,yb)，圆心为O(0，0)，设绘图笔当前位置为K(xk,yk)，这里的坐标为局部坐标。第45页/共152页第四十五页，共153页。图3.2.3一个圆上的8个对称点第46页/共152页第四十六页，共153页。图3.2.4逐点比较法与圆弧的生成第47页/共152页第四十七页，共153页。

点K相对于圆弧AB的位置有三种情况：点K在AB外侧，点K在AB上以及点K在AB内侧。为判断点K与AB的相对位置，引入偏差函数Fk，((((R是为便于推导引入的半径。当K在AB上时，Fk=0;

K在AB外侧时，Fk>0;

K在AB内侧时，Fk<0。(((第48页/共152页第四十八页，共153页。

对第一象限的圆弧逆时针方向生成时，规定如下：当Fk≥0时，绘图笔从当前位置沿-X方向走一步，记作-Δx；当Fk<0时，绘图笔从当前位置沿+Y方向走一步，记作+Δy。绘图笔走-Δx时，新点坐标为xk+1=xk-1,yk+1=yk新点偏差为第49页/共152页第四十九页，共153页。绘图笔走+Δy时，新点坐标为新点偏差为第50页/共152页第五十页，共153页。

新点偏差Fk+1由当前点的坐标值及偏差来计算。根据Fk+1的正、负号再确定绘图笔的下一步走向，这样逐步进行，直到绘图笔到达圆弧的终点为止。终点判断可由总走步数J(J=|xb-xa|+|yb-ya|)来控制。每走一步J减去1，当J=0时即到达终点。对其他象限内圆弧生成的走步方向按图3.2.5(a)、(b)进行。第51页/共152页第五十一页，共153页。图3.2.5各象限内圆弧生成的走步方向(a)逆时针方向画圆弧；(b)顺时针方向画圆弧第52页/共152页第五十二页，共153页。【例3】用逐点比较法逆时针画圆弧AB，设起点为A(4，3)，终点为B(0，5)，圆心为O(0，0)。算法生成圆弧从起点开始，总走步数J=|0-4|+|5-3|=6，起点处F0=0，走步方向的规定按第一象限进行。算法的计算过程列于表3.2.1，其结果如图3.2.6所示。第53页/共152页第五十三页，共153页。表3.2.1圆弧生成的递推计算过程第54页/共152页第五十四页，共153页。图3.2.6逐点比较法生成圆弧的图例第55页/共152页第五十五页，共153页。

4.角度DDA法产生椭圆弧设给定的椭圆弧条件为：椭圆中心(xc,yc)，长、短半轴a和b，椭圆弧起始点参数角ts及终止点参数角te、长轴与X轴正向的夹角α，如图3.2.7所示。这里对ts和te的要求同前面的圆弧，由ts逆时针画弧至te。现在我们要做的工作是推导出椭圆弧在世界坐标系下的坐标表达式。椭圆弧从标准位置(水平放正)变换至图3.2.7所示位置，是经过旋转变换和平移变换这样的组合变换形成的，利用第4章4.1.4节图形变换的方法，我们可得到所需要的坐标表达式，即x=acostcosα-bsintsinα+xcy=acostsinα+bsintcosα+yts≤t≤te

第56页/共152页第五十六页，共153页。图3.2.7椭圆弧及其参数第57页/共152页第五十七页，共153页。

绘制椭圆弧的方法是用小直线段逼近。同DDA法产生圆弧一样，我们将这段椭圆弧离散为几等分，角度增量为dt，于是对于第i步，其对应的参数角为ti=ts+i·dt

i=1,2,…,n

该点坐标为xi=acosticosα-bsintisinα+xcyi=acostisinα+bsinticosα+y第58页/共152页第五十八页，共153页。3.3区域填充1.扫描线算法

(1)(YX)算法。这种算法充分利用一条扫描线上的像素存在着相关性这一特征进行填充。因为在一条扫描线上，如果某个像素在多边形之内，那么，一般地说，紧挨着的各像素也多半在多边形内。对于边界外的像素也同样存在着这种相关性。只有当多边形的边恰好通过两个像素之间时，它们在多边形内、外的性质才有所不同，而这种情况一般说来是有限的。在图3.3.1中，对于y=8这条扫描线，可求出交点a、b、c、d，因此，在该条扫描线上，凡是a<x<b和c<x<d之内的像素，都位于多边形之内。根据这一思想，(YX)算法的步骤可叙述如下：第59页/共152页第五十九页，共153页。图3.3.1多边形和扫描线第60页/共152页第六十页，共153页。①求交。求出每一条扫描线与多边形各边的交点，建立起(x,y)交点表，若为水平边则跳过。②排序。按x及y增加(或减少)的顺序，对这些交点进行排序。例如，交点(x1,y1)和(x2,y2)，当y1≤y2而x1<x2时，则(x1,y1)先于(x2,y2)。③填充。将每一对交点之间的所有像素置成所需要的像素值。(YX)算法的核心是按(x,y)值对交点作一次分类，以便找出像素的相关群。分类的顺序并不是特别重要的，但是却影响位于多边形内的像素出现的顺序，也即影响显示画面出现的顺序。此算法是对每一对交点之间的所有像素进行填充，因此交点的个数必须是偶数才能保证填充的正确性。而当扫描线恰好通过多边形的顶点(称为奇异点)时，不适当地计数就会造成错误。第61页/共152页第六十一页，共153页。

如图3.3.1中y=7这条扫描线，若顶点④(亦即交点(7，7))只计一次，就会出现这种情况。对于顶点①、③、⑤也有类似的情况。对这些奇异点，我们最好多计入一个交点。但对于顶点②、⑥，重复计数又会出现错误。为此，我们提出一种可靠的处理奇异点的方法，它依赖于多边形的拓扑性质。具体地说，它利用多边形相继各边的方向，若多边形的边单调地向上或向下伸展时，则对于每条与两条边的端点相交的扫描线，只需记录一个交点。而当边的方向是由向下变成向上或相反时，则必须重复记录一个交点。第62页/共152页第六十二页，共153页。

还有一种简单的处理奇异点的方法，就是对于那些不需要重复计数的奇异点，可以将其中一条边的y坐标值抬高一个像素，以保证仅有一条边与扫描线有交点，确保填充的正确性。在设备分辨率足够高的情况下，这种处理方法可以满足一般的要求，对于图3.3.1中的边e2及e5，如使其y的最小值分别为y=4和y=6，则保证了顶点②及⑥只计一次交点。第63页/共152页第六十三页，共153页。(2)Y-X算法。上边介绍的(YX)算法的第一步，也就是计算交点这一步，工作量是很大的，因为需要对多边形的每一条边都进行测试，看其是否与每一条扫描线相交。但是对于某一条扫描线，我们感兴趣的常常只有少数几条边。而且，与第i条扫描线相交的许多条边，一般地说也与第i+1条扫描线相交，也即在与一条边相交的很多条扫描线范围内，存在着边的相关性。因此，对于每一条扫描线，我们只比较与其相交的那些边。算法执行时要求建立一张有效边表(AET)，AET中的内容随每一条扫描线y值的不同而变化，也即在AET中，只保留与当前扫描线相交的所有的边。而且这些边按其与该扫描线交点的x坐标大小的顺序存放，以便于在一对交点之间填充。当从一条扫描线移到下一条扫描线时，我们利用两条扫描线间隔为1的特性，可以简化边与扫描线交点的计算。第64页/共152页第六十四页，共153页。图3.3.2中，设边AB的斜率为m，若其与扫描线yi的交点横坐标为xi,则与扫描线yi+1的交点的横坐标为

为了便于建立和修改AET，首先需要建立一张边表(ET)。边表一般是由一系列的存储桶(bucket)构成的，桶的数目与扫描线数一样多。凡是与每条边两端点中较小的y坐标值(ymin)对应的桶，都记录着待填充多边形各边的有关信息，包括每条边两端点中最大的y坐标值(ymax)，y值较小的那个端点的x坐标值(xmin)以及该边斜率的倒数(1/m)。图3.3.3表示出图3.3.1的六条边是如何存放的。第65页/共152页第六十五页，共153页。第66页/共152页第六十六页，共153页。图3.3.3边表第67页/共152页第六十七页，共153页。

当形成了ET以后，Y-X算法按如下步骤执行：

(1)将y值设置为ET中所列的最小y值，也即第一个非空的存储桶。

(2)将AET初始化，使其为空。

(3)重复做以下各步，直至AET和ET都为空：①把ET中y的信息与AET合并，同时保存AET中按x值大小实现的排序序列。②对于扫描线y,在一对交点之间填充所需要的像素值。③从AET中删去y>ymax的项。④对于仍留在AET中的每一项，用x+1/m代替x。⑤检查并保证AET中各项按x值大小的排序。⑥使y增1，成为下一条扫描线的坐标。第68页/共152页第六十八页，共153页。图3.3.4有效边表(a)扫描线9；(b)扫描线10第69页/共152页第六十九页，共153页。2.种子填充算法种子填充算法首先假定区域内某点(即种子点)是已知的，然后算法开始搜索与它相邻且位于边界(封闭轮廓线)内的点。如果相邻点不在边界内，那么就到达区域的边界；如果相邻点位于边界之内，那么这一点就成为新的种子点，然后继续递归地搜索下去。种子填充算法只适用于光栅扫描设备。在下面的讨论中假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有像素取值可与边界不同或相同。第70页/共152页第七十页，共153页。图3.3.5两类连通区域示意图第71页/共152页第七十一页，共153页。

区域可以分为四向连通和八向连通两种，四向连通区域指的是从区域上一点出发，可通过四个方向(上、下、左、右)移动的组合，在不越出区域的前提下，到达区域内的任意像素；八向连通区域指的是区域内每一个像素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向移动的组合来到达。图3.3.5(a)所示的区域是四向连通区域，图3.3.5(b)所示的区域是八向连通区域。第72页/共152页第七十二页，共153页。

种子填充算法中，允许从四个方向寻找下一像素的，称为四向算法；允许从八个方向搜索下一像素的，称为八向算法。八向算法可以填充八向连通区域，也可以填充四向连通区域。但四向算法只能填充四向连通区域。如果图3.3.5(b)中的区域是两个分离的区域，并且每个区域需填成不同的颜色，那么，用八向算法会使两个区域被错误地填上同一颜色。以下我们只讨论四向算法。只要把搜索方向从四个改变到八个，即可得到八向算法。可以使用栈结构来实现简单的种子填充算法。算法原理为：种子像素入栈。具体地，当栈非空时重复执行如下三步操作：第73页/共152页第七十三页，共153页。(1)栈顶像素出栈；

(2)将出栈像素置成填充色；

(3)按左、上、右、下顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成填充色，则把该像素入栈；若其中某个像素值与填充色相同，说明该像素已填充过或者该像素就是边界上的像素(当填充色与边界色相同时)，这时像素不入栈。上述算法也可以用于填充带有内孔的平面区域。第74页/共152页第七十四页，共153页。

简单的种子填充算法把太多的像素压入堆栈，有些像素甚至会入栈多次，这一方面降低了算法的效率，另一方面还要求很大的存储空间以实现栈结构，解决这个问题的一个办法是，在任意一个扫描线与多边形相交的区间(含若干个连续像素)上，只取一个种子像素。相应的算法称为扫描线种子填充算法，算法原理为：种子像素入栈。具体地，当栈非空时作如下四步操作：

(1)栈顶像素出栈；第75页/共152页第七十五页，共153页。(2)在区间上，沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止，即每出栈一个像素，就对包含该像素的整个区间进行填充；

(3)上述区间内最左、最右的像素分别记为xl和xr；

(4)在区间［xl,xr］中，检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素，若存在非边界、未填充的像素，则把每一区间的最右像素取作种子像素入栈。第76页/共152页第七十六页，共153页。3.区域填充图案前面介绍的区域填充算法，把区域内部的像素全部置成同一种颜色。但在实际应用中，有时需要用一种图案来填充平面区域。这可以通过对前述扫描线算法中写像素的部分稍作修改来实现：在确定了区域内一像素之后，不是马上往该像素填色，而是先查询图案位图的对应位置。若是以透明方式填充图案，则当图案位图对应位置为1时，用前景色写像素，否则，不改变该像素的值。而若以不透明方式填充图案，则视图案位图对应位置为1或0来决定是用前景色还是背景色去写像素。第77页/共152页第七十七页，共153页。

进行图案填充时，在不考虑图案旋转的情况下，必须确定区域与图案之间的位置关系。这可以通过把图案原点与图形区某点对齐的办法来实现。对齐方式有两种。第一种方式是把图案原点与填充区域边界或内部的某点对齐。用第一种方式填充的图案，将随着区域的移动而跟着移动，看起来很自然。对于多边形，可取区域边界上最左边的顶点。而对于圆和椭圆这样的具有光滑边界的区域，则最好取区域内部某一点(如中心)对应图案原点。第78页/共152页第七十八页，共153页。

第二种对齐方式是整除取余方式。假定图案是一个M×N位图，用M×N数组存放。M、N一般比需要填充的区域的尺寸小得多。所以图案总是设计成周期性的，使之能通过重复使用，构成任意尺寸的图案。当需要填充的区域与当前扫描线的相交区间确定之后，假定相交区间上一像素坐标为(x,y)，则其与图案位图上的对应位置为(x%M,y%N)，其中%为C语言整除取余运算符。当然，在图形填充时，若设备驱动程序提供一次写多个连续像素的指令时，也可以利用区间连贯性，把区间上的像素按一个周期一个周期地填充。例如，假设图案是16×16位图，那么每个周期为16。第79页/共152页第七十九页，共153页。

如果区间左端点对应图案的左边缘，即x坐标除以16余为0，且区间长度超过16，那么可以一次把图案的一行直接写到区间的一组对应像素上去。如果区间剩余长度还超过16，那么就把图案的一行再写到区间的对应部分。这样一直重复下去，直至把整个区间填满。如果区间的左端点或右端点并不刚好对应于图案的边缘，那么可先把区间的首或末周期内不属于区域的像素屏蔽起来，再执行上述多像素写操作。从算法复杂性看，第二种对齐方式比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果。但是它有一个潜在的毛病，即当区域移动时，图案不会跟着移动。其结果是区域内的图案变了。第80页/共152页第八十页，共153页。

有些反复使用的图符以及一些应用系统常用的特殊符号，若按第二种对齐方式下填充图案的方法，则每填一次图形就必须进行扫描转换一次。如果在系统启动时就对图形扫描转换填充图案，并把图形各像素的值存起来，以后每次生成时直接读出，并写到指定位置，可以大大提高系统效率。为了提高以后每次填充的速度，可构造图符的包围盒矩形，把含于包围盒，但不在图符区域内部的像素用0表示，把图符区域内部的像素用非零的颜色值表示，在需要填充图符时，以透明方式写矩形：for(i=0;i<矩形宽；i++)for(j=0;j<矩形高；j++)if(symbol［i,j］)drawpixel(i0+i,j0+j,symbol［i,j］);第81页/共152页第八十一页，共153页。

有些图符仅由0、1构成，1代表前景色，0代表背景色，每个像素仅占一位。这时若采用上述写矩形的方法，则不仅不属于图符的部分是透明的，而且矩形中属于图符，但用背景色表示的部分像素也透明了。如图3.3.6(a)所示，图符与原有图形混在一起了。这个问题有两种解决办法，一是用不透明方式写，即当矩形中像素值为0时，不管像素属于图符与否，统统用背景色改写屏幕像素，结果如图3.3.6(b)所示。屏幕上原有图形中不该清除的部分也被清除了。可见，简单地用透明或不透明方式都不能产生理想的结果(图3.3.6(c))。为了得到图3.3.6(c)的填充效果，可采用扫描转换与填充图案分开的办法进行。扫描转换时，对图符轮廓线图(图3.3.7(a))处理一次，得一位图(图3.3.7(b))。用透明方式写位图矩阵得图3.3.7(c)。再把位图(图3.3.7(b))和图案(图3.3.7(d))进行与(AND)运算得图3.3.7(e)。再用透明方式写矩阵3.3.7(e)即得理想结果(图3.3.6(c))。第82页/共152页第八十二页，共153页。图3.3.6把一图符加入图形的三种方案第83页/共152页第八十三页，共153页。图3.3.7用二次写方式绘制图符第84页/共152页第八十四页，共153页。

目前的C语言软件都向用户提供了定义图案(或称模板、掩码(mask))和填充图案的功能。如在MicrosoftC/C++软件中，定义图案的函数为-setfillmask。其中，参数mask(即掩码数组)是8×8位的数组，每一位代表一个像素。值为1的位，将相应像素设置成当前颜色；值为0的位，则不改变原像素值。而在一些CAD系统(AutoCAD)中，图案的定义则采用矢量(即几何)参数形式，图案可看作是由几组带间隔的平行线构成的。图案填充的思想较简单，将每组平行线按剖面线方式填充，按顺序将所有平行线填完后就得到了在区域内要填充的图案。第85页/共152页第八十五页，共153页。3.4线宽与线型的生成1.直线线宽的生成要产生具有宽度的线，可以顺着扫描所生成的单像素线条轨迹，移动一把具有一定宽度的“刷子”来获得，“刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生有宽度的线(如AutoCAD系统即是)。线刷子的原理最简单。假设直线斜率在［-1,1］之间，这时可以把刷子置成垂直方向，刷子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出”具有一定宽度的线。当直线斜率不在［-1,1］之间时，把刷子置成水平方向。具体实现刷子时，只要对直线扫描转换算法稍作修改即可。例如，当直线斜率在［-1,1］之间时，把每步迭代所得的点的上、下方半线宽之内的像素全部置成直线颜色。如图3.4.1所示为线宽是5个像素的情形。第86页/共152页第八十六页，共153页。图3.4.1用线刷子绘制的具有宽度的线第87页/共152页第八十七页，共153页。图3.4.2线刷子所产生的缺口第88页/共152页第八十八页，共153页。

算法简单、效率高是线刷子的优点。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，看起来很不自然。当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口，如图3.4.2所示。再者，斜线与水平(或垂直)线不一样粗。对于水平线或垂直线，刷子与线条垂直，因而最粗，其粗细与指定线宽相等；而对于45°斜线，刷子与线条成45°角，粗细仅为指定线宽的 倍。线刷子还有另一个问题：当线宽为偶数个像素时，用上述方法绘制的线条要么粗一个像素，要么细一个像素。第89页/共152页第八十九页，共153页。

为了生成有宽度的线，还可以用正方形的刷子。把边宽为指定线宽的正方形的中心沿直线作平行移动，即可获得具有线宽的线条，如图3.4.3所示为用正方形刷子绘制的具有宽度的线条。比较图3.4.3与图3.4.1可知，用正方形刷子所得的线条比用线刷子所绘制的线条要粗一些。与线刷子类似，用正方形刷子绘制的线条始末端也是水平或垂直的，且线宽与线条方向有关。与线刷子的情形相反，对于水平线与垂直线，线宽最小，而对于斜率为±1的线条，线宽最大，为垂直(水平)线宽度的倍。第90页/共152页第九十页，共153页。图3.4.3第91页/共152页第九十一页，共153页。

实现正方形刷子最简单的办法是：把正方形中心依次对准单像素宽的线条上各个像素，并把正方形内的像素全部置成线条颜色。这种简单方法将会重复地写像素。这是因为对应于相邻两像素的正方形一般会重叠。为了避免重复写像素，可以采用与有效边表类似的技术，为每条扫描线建一个表，存放该扫描线与线条的相交区间左右端点位置。在每个像素使用正方形刷子时，用该正方形与各扫描线的相交区间端点坐标去更新原表内端点数据，图3.4.4为刷子移动的相邻两步和有关扫描线的临时数据结构所保存的对应于各步的区间端点坐标。生成具有宽度的线条还可以采用区域填充的算法。先算出线条各角点，再用直线段把相邻角点连接起来，最后调用多边形填充算法把所得的四边形进行填色，即得到具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条。第92页/共152页第九十二页，共153页。图3.4.4正方形刷子移动的相邻两步对应的数据结构第93页/共152页第九十三页，共153页。

2.圆弧线宽的生成为了生成具有宽度的圆弧，可采用与直线情形类似的方法，当采用线刷子时，在经过曲线斜率为±1的点时，必须把线刷子在水平与垂直方向之间切换。由于线刷子总是置成水平或垂直的，所以在曲线接近水平与接近垂直的地方，线条更粗一些；而在斜率接近±1的点附近，线条更细一些，如图3.4.5所示。当采用正方形刷子时，无须移动刷子方向。只需顺着单像素宽的轨迹，把正方形中心对准轨迹上的像素，把正方形内的像素全部用线条颜色填充。用正方形刷子绘制的曲线条，在接近水平与垂直的部分最细，而在斜率为±1的点附近最粗，这恰与线刷子情形相反，如图3.4.6所示。第94页/共152页第九十四页，共153页。图3.4.5用线刷子绘制的圆弧第95页/共152页第九十五页，共153页。图3.4.6用正方形刷子绘制的圆弧第96页/共152页第九十六页，共153页。

绘制具有宽度的圆弧线条也可以采用填充的办法，先绘制圆弧线条的内边界和外边界，然后在内外边界之间填色。可以让内外边界都与单像素弧线轨迹距离半线宽，或把内外边界之一对准单像素弧线轨迹，另一边界线离开此线一个线宽距离。如图3.4.7所示为采用填充方法所得的圆弧线条示意图。第97页/共152页第九十七页，共153页。图3.4.7采用区域填充方法绘制的圆弧第98页/共152页第九十八页，共153页。3.线型的生成在绘图应用中常用到不同线型的线条，以便区分各种不同的意义。如采用实线表示立体线框图中可见的轮廓线，用虚线表示不可见的轮廓线，用点划线表示中心线等等。线型可以用一个布尔值的序列来存放。例如，用一个32位整数可以存放32个布尔值。用这样的整数存放线型定义时，线型必须以32个像素为周期进行重复。可按下述语句写像素：if(位串［i%32］)drawpixel(x,y,color)；其中i为循环变量，在扫描转换算法的内循环中，每处理一个像素就递增1，然后除以32取余。第99页/共152页第九十九页，共153页。

用这种简单办法实现的线型有个毛病。因为每位对应于算法的一个迭代步骤而不是线条上一个长度单位，因此线型中的笔划长度与直线长度有关，斜线上的笔划长度比横向或竖向上的笔划更长。对于工程图，这种变化是不能接受的。这时，每个笔划应该作为与角度无关的线段进行计算并扫描转换。粗线的线型计算为实的或透明的正方形，其顶点位置根据线型要求进行准确计算。然后对正方形进行扫描转换，对于垂直或水平的粗线线型，可以用写方块的简单办法进行。第100页/共152页第一百页，共153页。3.5字符的生成

字符是指数字、字母、汉字及各种符号，用于图形的标注、说明等。国际上应用最广的字符集是“美国信息交换用标准代码集”(AmericanStandardCodeforInformationInterchange)简称ASCII码。该字符集规定了127个字符代码。其中代码0~31表示控制字符，代码32~127表示英文字母、标点符号、数字符号、各种运算符以及特殊符号。每个ASCII码用一个字节(实际上只要7位二进制)代码表示。第101页/共152页第一百零一页，共153页。

我国除采用ASCII码外，还另外制订了汉字代码的国家标准字符集。最常用的字符集是“信息交换用汉字编码字符集基本集”GB2312-80。该字符集包含了6000多个常用汉字、英文字母、数字和其他图形符号，分成94个区、94个位。区码和位码各用一个字节(实际上只要7位二进制)来表示。为了能识别哪些字节表示ASCII码，哪些字节表示汉字编码，一般采用多余的一位(最高位)来标识。最高位为0时，表示ASCII码，最高位为1时，表示汉字编码。为了在终端显示器或绘图仪上输出字符，系统中必须装备有相应的字符库。字符库中储存了每个字符的形状信息。字符库分为矢量型和点阵型两种。第102页/共152页第一百零二页，共153页。

在笔式绘图仪上采用矢量型字符比较适合，矢量型字符库采用矢量代码序列表示字符的各个笔画。输出一个字符时，系统中的字符处理器解释该字符的每个矢量代码，输出对应的矢量，达到产生字符的目的。在终端显示器上显示字符一般采用点阵型字符库。点阵型字符库为每个字符定义一个字符掩膜，即表示该字符的像素图案的一个点阵。第103页/共152页第一百零三页，共153页。

1.矢量字符与AutoCAD的形用软件产生矢量字符时，应先定义字符，把字符的笔划数字信息按事先定义好的编码结构存储起来，再编写通用程序调用和书写字符。定义字符时，一般在正方形的网格(如8×8、16×16、32×32……)纸上写好要定义的字符，并记录各笔划的顶点坐标及抬、落笔信息的编码，以一定的格式存储形成编码文件。由此可见，一个能产生字符的好的软件需要有一套完整的定义字符的编码系统。下面以AutoCAD软件中矢量字符的生成为例加以说明。在AutoCAD中，使用一种称为形(Shape)的图形实体来定义西文字符、汉字及符号等。形定义中使用直线、圆弧作为基本笔划。第104页/共152页第一百零四页，共153页。1)形的定义格式每个形的定义由一个标题行和若干个描述行组成，即*〈形编号〉，〈定义字节数〉，〈形名称〉(标题行)〈控制码1〉，〈矢量1描述码〉，〈矢量2描述码〉，…，〈控制码2〉，矢量1描述码〉，…，〈控制码n〉，…，0(结束码)(描述行)第105页/共152页第一百零五页，共153页。

各项内容解释如下：形编号：每个形必须有一个编号，占用一个字节，编号范围是0~255之间的整数值。定义字节数：定义形所需的字节总数。字节用逗号隔开，从描述行第一个编码开始数，直到结束符“0”(包括该字符在内)。形名称：每个形赋予一个名称，即形名。形名小写时只起到形的一种标志作用，而不被存入存储器中。形名全部大写时才能被调用。第106页/共152页第一百零六页，共153页。控制码：由系统规定的专用码。有14个，常用码含义如下：000形定义结束001启动绘图方式(落笔)002退出绘图方式(抬笔)008由下两个字节给出X、Y位移(相对坐标)，绘制非标准矢量009由下面多个字节给出连续的X、Y位移来绘制非标准矢量，并必须用(0，0)结束00A(10)由下两个字节定义八分圆弧第107页/共152页第一百零七页，共153页。2)形的描述方式直线段采用标准矢量方式和非标准矢量方式(即相对坐标方式)来描述；圆弧用八分圆弧和非八分圆弧等方式描述。下面介绍常用的几种形描述方式。

(1)标准矢量方式。标准矢量划分为16个单位矢量，其方向及代码如图3.5.1所示，图中各方向矢量长度不同，但都作为一个单位长度。字符的线段走向凡符合这16个标准方向的，用其对应的代码表示，线段长度根据需要而定。方向及长度结合起来构成矢量描述码。第108页/共152页第一百零八页，共153页。图3.5.1标准矢量方向代码第109页/共152页第一百零九页，共153页。

矢量描述码由三位数组成(×××)。最左一位是前导，“0”表示十六进制数，否则表示十进制数。最右一位是矢量的方向代码(大小写均可)。中间一位是矢量长度，用矢量单位长度的整数倍(1~F）表示。用标准矢量描述形时，对于非水平和非垂直方向的矢量(代码为1，2，3，5，6，7，9，A，B，D，E，F)，规定其大小为该矢量X与Y方向分量中长度较大者。AutoCAD在用矢量描述形时，都要定义一个矢量的起点，该点称为基点。第一个矢量从基点出发，以后的矢量(包括抬笔的空矢量)首尾相连。基点的另一个作用是与形调用时的插入点重合。可见，为了以后形调用的方便应选择合适的基点。第110页/共152页第一百一十页，共153页。

在一个形定义内，描述行的第一个控制码缺省时，其默认状态为落笔(即控制码001)。另外，一旦设置了抬笔或落笔状态，此状态在该形定义内一直保持下去直到改变这种状态为止。例如，图3.5.2所示图形的形定义为*10,6,RECT(标题行)014,020,01C,028,021,0(描述行)

再如，图3.5.3所示表面粗糙度符号的形定义为(符号的图线采用标准矢量近似表示)*20,7,ROUG002,053,001,058,05D,0A3,0第111页/共152页第一百一十一页，共153页。图3.5.2矩形图例第112页/共152页第一百一十二页，共153页。图3.5.3表面粗糙度符号第113页/共152页第一百一十三页，共153页。(2)非标准矢量方式。这种方式采用相对坐标描述线段的长度和方向。由控制码008和009引出，紧跟其后的相对坐标取值为-128~127的整数。这一方式完成后自动回到标准矢量方式。例如，图3.5.4的汉字“中”的形定义为*30,25,ZHONG002,008,(2,2),001,009,(0,4),(4,0),#;(0,-4),(-4,0),(0,0),002,008,(2,6),001,#;008,(0,-8),0

上述形定义中，相对坐标加括号是为了增加可读性，括号不包括在总字节数内。标准矢量方式与非标准矢量方式可以混合使用。第114页/共152页第一百一十四页，共153页。图3.5.4用相对坐标描述汉字第115页/共152页第一百一十五页，共153页。(3)八分圆弧方式。该方式由控制码00A(10)引出，八分圆弧是指把一个整圆作八等分，如图3.5.5表示各段圆弧的起点位置码(0，1，2，…)。要求所画弧的起点、终点必须落在等分点上。一段圆弧用两个字节描述，即

10,(半径，(-)0SC)其中，半径的取值为1~255。0SC前面的符号，规定以逆时针画弧取正(省略“+”号)，否则取负。S为圆弧起点位置码；C为圆弧跨过八分弧的个数，取值为0~7，画整圆时取0。括号用来改善可读性。第116页/共152页第一百一十六页，共153页。

用八分弧方式可以定义含有圆或弧的各种符号，可与其他描述方式混合使用。例如，图3.5.6所示的基准符号的形定义为*60,16,JZ#;002,038,001,060,002,014,001,068,002,030,001,0A4,10,(004,060),0

上述定义中，取圆的半径为4个单位，中间连线长度为10，下方两条横线长均为6，用两条靠近的线来代替一条粗线(因为形描述的线均为细线)。第117页/共152页第一百一十七页，共153页。图3.5.5八分弧划分第118页/共152页第一百一十八页，共153页。图3.5.6基准符号第119页/共152页第一百一十九页，共153页。3)形的调用用文本编辑软件把若干个形定义放在一个形文件中，就形成了AutoCAD所使用的字符库。形文件经过编译(COMPILE)、装入(LOAD)，形调用(SHAPE)通过后，就可以随时调用形绘出字符。第120页/共152页第一百二十页，共153页。2.点阵字符在点阵字符库中，每个字符都定义成一个称为字符掩膜的矩阵。矩阵中的每个元素都是一位二进制数。该位为1时，表示字符的笔划经过此位，对应于此位的像素应置为字符颜色；该位为0时，表示字符的笔划不经过此位，对应此位的像素应置为背景色(若当前的写方式是“替换”方式)或不改变(若当前写方式是“与”方式)。一般认为，定义西文字符的掩膜矩阵尺寸应不小于5×7，而定义汉字字符的掩膜矩阵尺寸应不小于16×16。在我国广泛使用的微机汉字系统，如中文Windows等，都采用16×16点阵汉字作为显示用字符，而在打印时，采用24×24，40×40甚至72×72的点阵字符。第121页/共152页第一百二十一页，共153页。

一个5×7西文字符点阵包括35个点，需要35b，故需要35b二进制数(占4个多字节)。一个16×16点阵汉字，需要256b，即32B。而一个72×72点阵汉字需要9×72=648B。用于打印的高分辨率点阵字符的掩膜位图，可以用扫描仪输入放大的手写美术字符或印刷字符，然后用交互作图程序对位图的个别像素进行修改，使之完善。用于显示的或用于低分辨率打印机的字符位图可以使用交互绘图程序，通过手工建立。用低分辨率点阵字符产生的字符一般比较粗糙，不美观，所以在微机上通常使用几个不同分辨率的字符库，以满足不同的需要。第122页/共152页第一百二十二页，共153页。3.字型技术当应用对输出字符的要求较高时(如排版印刷)，需要使用高质量的点阵字符。然而直接使用上一小节所介绍的点阵字符方法将耗费巨大的存储空间。对于GB2312-80所规定的6763个基本汉字，假设每个汉字是72×72点阵，那么一个字库就需要4.4MB存储空间!在实际使用时，需要多种字体(如宋体、仿宋体、黑体、楷体等)，而每种字体又需要10种以上字号。因此把每种字体、字号的字符都存储成一个对应的点阵，在一般情况下是不可行的。第123页/共152页第一百二十三页，共153页。

解决这个问题一般采用压缩技术。对字型数据压缩后再存储，使用时，将压缩的数据还原为字符位图点阵。压缩方法有多种，最简单的是黑白段压缩法。这种方法简单，还原快，不失真，但压缩效果较差，使用起来也不方便，一般用于低级的文字处理系统中。二是部件压缩法。这种方法压缩比大，缺点是字型质量不能保证。三是轮廓字型法(一种双线笔划)。这种方法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法，基本上也被认为是符合工业标准化的方法。第124页/共152页第一百二十四页，共153页。

轮廓字型法采用直线或者二/三次Bézier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。这种控制信息用于保证字符变倍时引起的字符笔划原来的横宽/竖宽变大变小时，其宽度在任何点阵情况下永远一致。采用适当的区域填充算法，可以从字符的轮廓线定义产生字符位图点阵，区域填充算法可以用硬件实现，做在RISC集成电路板上成为光栅图像处理器RIP(RasterImageProcessor)；也可以用软件实现，写成一段精心编制的程序。如目前国际上广泛使用的TrueType字体，采用的是轮廓字型法，国产的电子出版系统(如方正、华光)中的汉字字型技术也采用轮廓字型法。第125页/共152页第一百二十五页，共153页。TrueType字型技术是由Apple公司和Microsoft公司联合开发的，它使用二次Bézier曲线来描述字符轮廓，对字符轮廓线的控制点进行编号，编号的方法是按顺时针