第 5章 基本图形处理技术
提纲：
? 1,区域填充；
? 2,线宽与线型处理
? 3,字符显示与处理
? 4,裁剪处理
? 5,反走样技术
5.1 区域填充
区域填充的任务是在一个封闭的区域
中的所有像素，用一种颜色或图案位图来
显示。区域填充可以分两步进行，第一步
先确定填充的区域，第二步确定用什么颜
色值来填充。 在本节中，我们首先讨论如
何用单一颜色填充多边形与图形区域，然
后再讨论图案填充。
5.1.1 多边形域的填充
1．原理描述
这里讨论的是任意多边形，多边形域可以是
凸的、凹的或带孔的。一种常用的填充方法是按
扫描线顺序，计算扫描线与多边形的相交区间，
再用要求的颜色显示这些区间的像素，即可以完
成填充工作。区间的端点可以通过计算扫描线与
多边形边界线的交点获得。
如图 5.1.1所示，扫描线 6与多边形的边界线
交于四点 A,B,C,D。这四点把扫描线分为五
个区间 [0,2],[2,3.5],[3.5,7],[7,11]、
[11,12]。其中 AB[2,3.5],CD[7,11]两个区间
落在多边形内，该区间内的像素应取多边形填充
色，其他区间内的像素取背景色。
P1(2,2)
P2(5,1)
P3(11,3)
P5(5,5)
P4(11,8)P
6(2,7)
E
A B C DD
GF
0 1 2 3 4 5 6 7 8 9 10 11 x
1
2
3
4
5
6
7
8
y
图 5.1.1 一个多边形与若干扫描线
这里的四个交点在计算时未必是按从左到右
顺序获得。例如，当多边形采用顶点序列
P1P2P3P4P5P6表示时，把扫描线 6分别与 P1P2、
P2P3, P3P4, P4P5, P5P6, P6P1 六条边
相交，得到交点序列为 D,C,B,A，必须经过
排序，按 x递增的顺序排列交点顺序，才能得到从
左到右排列的交点序列。
一般多边形的填充过程，对于一条扫描线，
可以分为四个步骤：
(1)求交：计算扫描线与多边形各边的交点；
(2)排序：把所有交点按 x递增顺序进行排序；
(3)交点配对：第一个与第二个，第三个与第四
个,…,第 2i-1与第 2i个交点配对，其中,i取
1~n。每对交点就代表扫描线与多边形的一个相
交区间。
(4)区间填色：把这些相交区间内的像素置成多边
形填充色，把区间外的像素置成背景色。
在多边形填充算法中，必须解决两个特殊的问题：一
是当扫描线与多边形顶点相交时，交点的取舍问题。二是
多边形边界上像素的取舍问题。前者用于保证交点正确配
对，后者用于避免填充扩大化。
先讨论第一个问题。当扫描线与多边形顶点相交时，
会出现异常情况。例如图 5.1.1中过的与 P1,P2,P5、
P6点的扫描线，算几个交点，如果取舍不正确，交点配对
和填充就会出现错误。
为了正确地进行交点取舍，必须按照下面的规则对交
点进行取舍：
(1)扫描线交于一顶点，而共享该顶点的两条边分别落在
扫描线的两边，则交点只算一个。如图 5.1.2(a)。
(2)扫描线交于一顶点，而共享该顶点的两条边在扫描线
的同一边，这时交点作为零个或两个，这取决于该顶点是
多边形的局部最高点（ 0个）还是局部最低点（ 2个）。如
图 5.1.2(b)和如图 5.1.2(c)。
A
B C A
B
C
C
B
A
(a)
取
一
个
(b)
取
零
个
(c)
取
二
个
图 5.1.2 扫描线与多边形顶点相交时交点的取舍
具体实现时，只需检查顶点的两体条边的另外两个端
点的 y值，如果两个 y值中大于交点出 y值的个数是 0,1、
2，那么交点分别取零个、一个或二个。
按照上述规则，图 5.1.1中的顶点 P2,算两个交点，
这样 P2 像素用多边形颜色设置。在顶点 P1 处，只算一个
交点。而在 P6 处，交点算零个，即该点不予填充。
下面讨论第二个问题，即边界上像素的取舍问题。例
如，对左下角为 (1,1)，右上角为 (3,3)的正方形填充时，
若对边界上所有的像素均进行填充，就得到如图 5.1.3的
结果，被填充的像素覆盖的面积为 3х3单位，而正方形的
实际面积只有 2х2单位。这种现象称为边界扩大化问题。
为了克服这个问题，规定落在右 /上边界的像素不予填充，
而落在左 /下边界的像素予以填充。在具体实现时，只要
对扫描线与多边形的相交区间取左闭右开。容易看出，在
解决第一个问题时，对交点的取舍方法保证了多边形的
,下闭上开,,即丢弃上方水平边以及上方非水平边上作
为局部最高点的顶点。
1 2 3 4 x
1
2
3
4
y
图 5.1.3 边界上像素的填充
2．采用的数据结构
（ 1）活性边表
为了计算每条扫描线与多边形各边的交点，最简单的
方法是把多边形的所有边放在一个表中。在处理每条扫描
线时，按顺序从表中取出所有的边，分别与扫描线求交。
这样处理效率很低，这是因为一条扫描线往往只与少数几
条边相交，甚至与整个多边形都不相交。为了提高效率，
在处理一条扫描线时，仅对与它相交的多边形的边进行求
交运算。我们把与当前扫描线相交的边称为活性边，并把
它们按与扫描线交点 x坐标递增的顺序存放在一个链表中，
称此链表为活性边表。
活性边表的每个结点存放对应边的有关信息，如扫描
线与该边的交点 x，边所跨的扫描线条数等。由于边的连
贯性（即当某条边与当前扫描线相交时，它很可能也与下
一条扫描线相交），以及扫描线的连贯性（即当前扫描线
与各边的交点顺序与下一条扫描线与各边的交点顺序很可
能相同或非常类似），在当前扫描线处理完毕之后，不必
为下一条扫描线从头开始构造活性边表，而只要对当前扫
描线的活性边表稍作修改和更新，就可以得到下一条扫描
线的活性边表。具体原理讨论如下：
假设当前扫描线与多边形的某一条边的交点坐标为 x，
那么下一条扫描线与该边的交点不必从头计算，只要加上
一个增量即可。设边的直线方成为
ax+by+c=0
若 y=yi时,x=xi，则当 y=yi+1时，
xi+1=(-byi+1-c)/a=(-b(yi+1)-c)/a=(-b yi -
c)/a-b/a=xi-b/a
其中△ x=-b/a为常量。△ x可以存放在对应边的活性
边表结点中。另外，使用增量法计算时，我们需要知道一
条边何时不再与下一条扫描线相交，以便及时把它从活性
表中删除，避免下一步无谓的计算。
综上所述，活性边表的结点中至少应为对应边保存如
下内容：
x,当前扫描线与边的交点；
△ x：从当前扫描线到下一条扫描线之间的 x增量；
ymax,边所交的最高扫描线号。
若规定多边形的边不自交，则从当前扫描线
延续到下一条扫描线，边与下一条扫描线的交点
顺序保持不变。否则，到下一条扫描线，必须重
新排序。由于扫描线的连贯性，新交点序列与旧
交点序列基本一致，最多只有个别需要调整。因
此，采用冒泡排序法可获得较好效果。对于下一
条扫描线新交上的边，则必须在当前扫描线处理
完之后的更新过程中，插入到活性边表的适当位
置，并保持有序性。这个过程采用插入排序最适
宜。另外，在上述的交点 x坐标更新和新边插入之
前，必须把那些与当前扫描线有交，而与下一条
扫描线不再相交的边，从活性边表中删除。图
5.1.4中，扫描线 6的活性边表如图（ a）所示，
扫描线 7的活性边表如图（ b）所示。
2 0 7 3.5 -1.5 7 7 2 8 11 0 8
9 2 8 11 0 8 Λ
通过活性边表，可以充分利用边的连贯性
和扫描线的连贯性，减少求交计算量与提高排
序效率。
（ 2）新边表
为了方便活性边表的建立与更新，为
每一条扫描线建立一个新边表，存放在该
扫描线上第一次出现的边。也就是说，若
某边的较低端点为 ymin，则该边就放在扫
描线 ymin的新边表中。这样，当我们按扫
描线号从小到大顺序处理扫描线时，该边
在该扫描线第一次出现。新边表的每个结
点存放对应边的初始信息。如该扫描线与
该边的初始交点 x（即较低端点的 x值）,x
的增量△ x以及该边的最大 y值 ymax。新边
表的边结点不必排序。图 5.1.5是各扫描线
的新边表。
Λ
Λ
Λ
Λ
5 2 8
5 -1.5 7 Λ
（ 3）多边形区域填充算法
在活性边表的基础上，进行交点配对和区间填充是很
容易的事。只要设置一个布尔量 b，规定在多边形内时,b
取真值，在多边形外时,b取假。令指针从活性边表中第
一个结点（交点）到最后一个结点遍历一次，每访问一个
结点，把 b取反一次。若 b为真，则把从当前结点的 x值开
始到下一结点的 x值结束的左闭右开区间用多边形填充色
进行填充。这样就可以完成多边形内的像素取多边形色，
多边形外的像素取背景色。
多边形区域填充算法描述如下：
Polygonfill(polydef,color)
int color;
多边形定义 polydef;
{
for (各条扫描线 i)
{
初始化新边表表头指针 NET[i];
把 ymin=i的边放进边表 NET[i];
}
y=最低扫描线号；
初始化活性边表 AET为空；
for (各条扫描线 i)
{
把新边表 NET[i]中的边结点用插入排序法插入 AET表，
使之按 x坐标递增顺序排列；
遍历 AET表，把配对交点之间的区域（左闭右开）上的
各像素 (x,y)，用 DrawPixel(x,y,color)设置填充颜色；
遍历 AET表，把 ymax=i的结点从 AET表中删除，并把
ymax>i结点的 x值递增△ x；
若允许多边形的边子相交，则用冒泡排序法对 AET
表重新排序；
}
} /* End Polygonfill */
多边形区域填充算法又称为有序边表
算法，该算法对显示的每个像素只访问一
次，这样，输入 /输出的要求可降低为最少。
有由于该算法与输入 /输出的细节无关，因
而它也是与设备无关的。该算法的主要缺
点是对各种表的维持和排序开销太大，适
合软件实现而不适合硬件实现。
5.1.2 边填充算法
1．原理描述
边填充算法的基本思想：对于每一条
扫描线和每条多边形边的交点（ x1,y1），
将该扫描线上交点右方的所有像素取补。
对多边形的每条边作此处理，多边形的顺
序随意。如图 5.1.6是一个简单边填充算法
的示意图。
P1 P2
P3
P4
P5
P2P3 P3P4
P4P5 P5P1
图 5.1.6 边填充算法示意图
边填充算法最适用于具有帧缓冲器的图形系
统，按任意顺序处理多边形的边。在处理每条边
时，仅访问与该边有交的扫描线上交点右方的像
素。当所有的边都被处理之后，按扫描线顺序读
出帧缓冲器的内容，送入显示设备。该算法的优
点是简单，缺点是对于复杂图形，每一像素可能
被访问多次，输入输出的量也比较大。
为了减少边填充算法访问像素的次数，可引
入栅栏。所谓栅栏指的是一条与扫描线垂直的直
线，栅栏位置通常取过多边形顶点、且把多边形
分为左右两半。栅栏填充算法的基本思想是：对
于每条扫描线与多边形边的交点，就将交点与栅
栏之间的像素取补。若交点位于栅栏左边，则将
交点置右，栅栏之左的所有像素取补；若交点位
于栅栏右边，则将栅栏置右，交点之左的像素取
补。图 5.1.7是采用栅栏填充算法的示意图。栅栏
填充算法只是减少了被重复访问像素的次数，但
仍有一些像素会被重复访问。
P1 P2
P3
P4
P5
P2P3 P3P4
P5P1
栅栏线
P4P5
图 5.1.7 栅栏填充算法示意图
边标志算法分为两个步骤：
第一步，对多边形的每条边进行直线扫描转换，即
对多边形边界所经过的像素打上边标志。
第二步，填充。对每条与多边形相交的扫描线，依
从左到右顺序，逐个访问该扫描线上像素。使用一个布
尔量 inside来指示当前点的状态，若点在多边形内，则
inside为真。若点在多边形外，则 inside为假。
Inside的初值为假，每当当前访问像素为被打上边标
志的点，就把 inside取反。对未打标志的像素，
inside不变。若访问当前像素时，对 inside作必要操
作之后,inside为真，则把该像素置为多边形色。
边标志算法描述如下：
#define FALSE 0
edge_mark_fill (polydef,color)
多边形定义 polydef;
int color;
{
对多边形 polydef每条边进行直线扫描转换；
inside=FALSE;
for (每条与多边形 polydef相交的扫描线 y)
for (扫描线上每个像素 x)
{
if (像素 x被打上边标志 )
inside= !(inside);
if (inside !=FALSE)
drawpixel(x,y,color);
else
drawpixel(x,y,background);
}
}
用软件实现时，有序边表算法与边标志算法执行速度
几乎相同，但由于在帧缓冲器中应用边标志算法时，不必
建立和维护边表以及对它进行排序，所以边标志算法更适
合硬件实现。
5.1.3 种子填充算法
1．原理和方法
种子填充算法是假设在多边形区域内部取一点（像
素），由此出发找到区域内所有像素。该算法要求区域采
用边界定义，即区域边界上所有像素均具有某个特定值，
而区域内部所有像素均不取这一特定值。
区域可以分为四向连通和八向连通两种。四向连通区
域指的是从区域上一点出发，可通过四个方向，即上、下、
左、右移动的组合，在不越出区域的前提下，到达区域内
的任意像素。八向连通区域指的是区域内每一个像素，可
以通过左、右、上、下、左上、右上、左下、右下这八个
方向的移动组合来达到。
种子填充算法中允许从四个方向寻找下一个像素者，
称为四向算法；允许从八个方向搜索下一像素者，称为八
向算法。八向算法既可以填充八向连通区域，也可以填充
四向连通区域。但是，四向算法只能填充四向连通区域，
而不能填充八向填充区域。
下面只考虑四向算法。
可以使用栈结构来实现简单的种子填充算法，
其原理如下：种子像素如栈，当栈非空时，重复
如下三步操作：
1,栈顶像素出栈；
2,将出栈像素置成多边形色，即填充色；
3,按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素不在边界且未被置成
多边形色，则把该像素入栈。
举例，如图 5.1.9所示，为一个用边界表示
的区域，其中 s1(2,3)为种子像素，用简单的种
子填充算法对该区域进行填充，各像素的出栈顺
序分析如下：
步骤：
（ 1） s1入栈，
栈,s1;
（ 2） 出栈,s1，即（ 2,3）
入栈,4,7,9,2；
栈,4,7,9,2；
（ 3） 出栈,2，即（ 1,3）
入栈,3,8
栈,4,7,9,3,8
（ 4） 出栈,8，即（ 1,4）
入栈：没有
栈,4,7,9,3
（ 5） 出栈,3，即（ 1,2）
入栈：没有
栈,4,7,9
（ 7） 出栈,7，即（ 3,3）
入栈,6
栈,4,6
（ 8） 出栈,6，即（ 3,2）
入栈：没有
栈,4
（ 9） 出栈,4，即（ 2,2）
入栈,5
栈,5
（ 10）出栈,5，即（ 2,1）
入栈：没有
栈：空
程序结束。
编写程序实现上述算法。可以定义一个大型数组来
模拟栈结构，如 stack[2000]。
简单种子填充算法把太多的像素压入堆栈，有些像素
甚至会如栈多次，这一方面降低了算法的效率，另一方
面还要求很大的存储空间以实现栈结构。其改进算法是：
在任意一条扫描线与多边形的相交区间（含若干个连续
像 素）中，只取一个种子像素，相应的算法称为扫描线
填充算法。算法原理如下：种子像素入栈，当栈非空时
作如下四步操作：
(1)栈顶像素出栈；
(2)沿扫描线对出栈像素的左右像素进行填充，
直至遇到边界像素为止，即每出栈一个像素，就
对包含该像素扫描线上的整个区间进行填充；
(3)上述扫描线区间内的最左、最右的像素分别
记为 xl和 xr；
（ 4） 在区间 [xl,xr]中检查与当前扫描线相邻
的上下两条扫描线的有关像素是否全为边界像
素或已填充的像素，若存在非边界、未填充的
像素，则把每一区间的最右像素取为种子像素
入栈。
扫描线填充算法程序描述如下：
scanline_seed_fill(polydef,color)
多边形定义 polydef;
int color;
{
int x,y,x0,xl,xr;
push(seed(x,y)); /*种子像素入栈 */
? while (像素栈非空 ) {
? pop(pixel(x,y)); /*栈顶像素出栈 */
? drawpixel(x,y,color);
? x0=x+1;
while (pixel(x0,y)的值不等于边界值 ) /*填充右
方像素 */
{
drawpixel(x0,y,color);
x0=x0+1;
}
xr=x0-1; /*记录最右像素 xr*/
x0=x-1; /*填充左方像素，像素起点 */
while (pixel(x0,y)的值不等于边界值 )
{
drawpixel(x0,y,color);
x0=x0-1;
}
xl=x0+1; /*记录最左像素到 xl中 */
/*种子像素的左右像素填充完毕，下面分别向上、
向下逐条扫描线填充 */
/*检查上一条扫描线，若存在非边界且未填充的像
素，则选取代表各连续区间的种子像素入栈 */
x0=xl; y=y+1;
while (x0<=xr)
{
flag=0;
while ((pixel(x0,y)的值不等于边界
值 )&&(pixel(x0,y)的值不等
于多边形色 )&&(x0<xr))
{
if (flag= =0) flag=1;
x0++;
}
if (flag= =1)
{
if ((x0= =xr)&&(pixel(x0,y)的值不等
于边界值 )&&(pixel(x0,y)的值不等于
多边形色 ))
push(pixel(x0,y));
else
push(pixel(x0-1,y));
flag=0;
} /*end if*/
xnextspan=x0;
while ((pixel(x0,y)等于边界
值 )||(pixel(x0,y)等于多边形色 )&&(x0<xr))
x0++;
if (xnextspan= =x0) x0++;
} /* end while (x0<=xr)*/
/*检查下一条扫描线，若存在非边界，未填充
的像素，则选取代表各连续区间的种子像素入栈；
算法与前面处理上一条扫描线算法完全一样，只
要把 y+1换成 y-1即可 */
} /*end while 像素栈非空 */
}
5.1.4 区域填充图案
在实际应用中，有时需要用一种图案来填充平面区域，
其原理是在上述扫描转换算法基础上稍作修改来实现：在
确定了区域内一个像素之后，不是马上往该像素填色，而
是先查询图案位图的对应位置。若是透明方式填充图案，
则当图案表的对应位置为 1时，用前景色写像素，否则，
不改变该像素的值。而若以不透明方式填充图案，则视图
案位图对应位置为 1或 0来决定是用前景色还是用背景色去
写像素。
1．位图（ bitmap）填充
假设填充图案是一个 MxN的位图，用 MxN数
组存放。 M,N一般比需要填充的区域的尺寸小得
多。所以图案总是设计成周期性的，使之能通过
重复使用，构成任意尺寸的图案。
当需要填充的区域与当前扫描线的相交区间确定
之后，假定相交区间上一个像素的坐标为（ x,y），
则图案位图上的对应位置为（ x%m,y%n），其
中 %为 C语言整除取余运算符。若采用不透明方
式填充图案，则应把算法 polygonfill中无条件地
使用前景色 color写像素操作
drawpixel(x,y,color)，改成当图案值为 1时，
用前景色 color写，否则，用背景色 background
写，即 if (pattern(x%m,y%n))
drawpixel(x,y,color);
Else
drawpixel(x,y,background);
如果采用透明方式填充图案时，只要去掉 else分
句即可。
2．填充图案的保存与重写
可以将已经填充图案的图形的各像素读到一
个数组中。设该图形的外接矩形宽为 wide，高为
height，矩形的左上角坐标为（ x0,y0），数组
为 symbol[]，则保存程序为：
for (i=0;i<wide; i++)
for (j=0;j<height; j++)
symbol[i,j]=getpixel(x0+i,y0+j);
填充图案的重写：当需要把保存在 Symbol[]数组
中的图形再次写到屏幕从（ i0,j0）开始的位置上
时，则重写程序如下：
for (i=0;i<wide; i++)
for (j=0;j<height; j++)
if (symbol[i,j])
putpixel(i0+i,j0+j,symbol[i,j]);
5.1.5 程序设计与实践（三）
一、实验内容：区域填充算法程序设计
二、实验任务：
1,多边形有序边表算法程序设计；
2,边填充算法和边标志填充算法；
3,简单的种子填充算法和扫描线填充算法；
4,区域填充图案程序设计；
三、实验步骤
要求完成：
（ 1）边标志填充算法；
（ 2） 简单种子填充算法或扫描线填充算法；
（ 3）区域填充图案算法
5,2 线型与线宽处理
5.2.1 直线线宽的处理
在实际应用中，除了使用单像素宽的线条，还经常使
用指定线宽和线型的直线与弧线。与产生具有线宽的线条，
可以顺着扫描线所生成的单像素线条轨迹，移动一把具有
一定宽度的, 刷子, 来获得。, 刷子, 的形状可以是一条
线段或一个正方形，也可以采用区域填充的办法间接地产
生有宽度的线。
线刷子的工作原理：假设直线斜率在 [-1,1]之间，
这时可以把刷子置成垂直方向，刷子的中点对准直线一端
点，然后让刷子中心往直线的另一端移动，即可, 刷出,
具有一定宽度的线段。当直线斜率不在 [-1,1]之间时，把
刷子置成水平方向。
在具体实现线刷子时，只要对直线扫描转换算法的内
循环稍作修改。例如，当直线斜率在 [-1,1]之间时，把
每步迭代所得的点上下方半线宽之内的像素全部置成直线
颜色。
图 5.2.1 线刷子产程的缺口
线刷子的优点是算法简单、效率高，但是，
由于线的始末端点总是水平或垂直的，因此，当
线宽较大时，看起来很不自然。当比较接近水平
线和比较接近垂直线汇合时，汇合处外角将有缺
口，如图 5.2.1所示。另外，线刷子的线条不一样
粗细。对于水平线和垂直线，刷子与线条垂直，
因而线最粗，其粗细等于线宽。而对于 45度斜线，
刷子与线成 45度角，线的粗细仅为指定线宽的
1/sqrt(2)=0.7倍。还有一个问题，当线宽为偶
数个像素时，用上述算法绘制的线条，要么粗一
个像素，要么细一个像素。
方形刷子工作原理是：把正方形中心对准单
像素宽线条上各个像素，并把方形内的像素全部
置成线条颜色。这种方法将会重复地写像素，这
是因为对应于相邻两个像素的方形会产生重迭。
用方刷子所得的线条比用线刷子所绘制的线
条要粗一些。用方刷子绘制的线条始末端也是水
平或垂直的，且线宽与线条方向有关，对于水平
与垂直线，线宽最小，而对于斜率为 1或 -1的线
条，线宽最大，为垂直线（水平）线宽度的
sqrt(2) 倍。
生成具有宽度的线条还可以采用区域填充的
算法。先算出线条各角点，再用直线段把相邻角
点连接起来，最后调用多边形填充算法把所得的
四边形进行填充，即得到具有宽度的线条。
5.2.2 圆弧线宽的处理
为了生成具有宽度的圆弧，可采用与直线情形类
似的方法。当采用线刷子时，在经过曲线斜率为 1
或 -1的点时，必须把线刷子在水平与垂直方向之
间切换。由于线刷子总是置成水平或垂直的，所
以在曲线接近水平与垂直的地方，线条更粗一些，
而在斜率接近 1或 -1的点附近，线条更细一些。
当采用正方形刷子时，无须移动刷子方向，只
需要顺着单像素宽的轨迹，把正方形中心对准轨
迹上的像素，把正方形内的像素全部用线条颜色
填充。用正方形刷子绘制的曲线条，在接近水平
与垂直的部分最细，而在斜率为 1或 -1点附近最
粗，这恰好与线刷子情形相反。
绘制具有宽度的圆弧线条也可以采用填充的
办法，先绘制圆弧线条的内边界和外边届，然后
在内外边界之间对其填充。可以让内外边界与单
像素弧线轨迹距离班线宽，或把内外边界之一对
准单像素弧线轨迹，另一边界线离开此线一个线
宽距离。
5.2.3 线型的处理
在绘图应用中，常用到不同线型的线条。如
实线、虚线、点划线等。
线型可以用一个布尔值的序列来存放。例如，
用一个 32位整数可以存放 32个布尔值。
用这样的整数存放线型定义时，线型必须以 32个像素
为周期进行重复。可以把扫描转换算法中的无条件写像素
语句改为：
if (位串 [i%32]) drawpixel(x,y,color);
其中 i为循环变量，在扫描转换算法的内循环中，每处理
一个像素递增 1，然后除以 32取余。
5,3 字符与字形技术
在计算机图形学中，处理对象不仅包括点、线、曲线
等基本图形的显示与处理，同时还包括字符和字形的处理
和显示技术。字符处理在计算机图形学中是必不可缺少的
一部分。本节主要讨论字符生成与输出技术，以及字形处
理技术。
在计算机图形学中的字符是指数字、字母、汉字等符
号，用于图形的标注和说明。国际上通用的字符集是
ASCII码。该字符集规定了 127个字符代码，其中代码
0~31用于表示控制字符； 32~127表示大、小写 26个英
文字母、标点符号、运算符以及特殊符号等。每个 ASCII
码用一个字节（实际只有 7位，最高位为 0）代码表示。
为了规范汉字的处理，我国也制定了汉字代
码的国际标准，最常用的汉字字符集是, 信息交
换用汉字编码字符集基本集, GB2312-80。 。
该字符集包含了六千多个常用汉字，以及英文字
母、数字及其它图形符号。 GB2312-80字符集
分成 94个区，每区 94个位。区码和位码各用一个
字节（实际只有 7位）来表示。为了区别 ASCII码
和汉字编码，用字节的最高位来标识。当最高位
为 0，表示 ASCII码，最高位为 1，表示汉字编码。
例如，
01000100 11001100 10011001 01100111
ASCII 汉字 ASCII
为了在显示器上生成字符，系统中必须装备
有相应的字符库。字符库中储存了每个字符的形
状信息。根据字符生成方式的不同，分为矢量型
和点阵型两种字库。矢量型字符库采用矢量代码
序列表示字符的各个笔画，当输出一个字符时，
通过输出该字符各矢量，以产生相应的字符。矢
量型字符易于放大、缩小等变换，矢量型字符也
适宜于笔式绘图仪等矢量设备上使用。点阵型字
符库是为每一个字符定义一个字符掩膜，即表示
该字符像素图案的一个点阵。在终端显示器上显
示字符，一般采用点阵型字库。
5.3.1 矢量字符
矢量字符是用一系列的矢量段表示的字符。
为了建立一个矢量字符库，必须为每一个字符定
义一个矢量代码序列。建立矢量字符库的方法很
多，下面以 AUTOCAD系统使用的矢量字符来说
明矢量字符建立的方法。
在 AUTOCAD中，使用一种称为形（ shape）的图形
实体来定义英文字母、汉字，甚至是一种简单的图形。形
定义中使用直线和圆弧作为基本笔划。
每个形的定义包括一个标题行和若干描述行，形式如
下：
*形编码，字节数，形名称
字节 1，字节 2,……, 0
注：
（ 1）标题行以 *号开始，形编号是 1到 255的整数值。字节
数表示定义描述行中包括结束符 0在内的字节数。形名称
用大写字母书写才能被调用，否则只能作为形的一种解释
性信息，不存入存储器，因而也不占用存储空间。
（ 2）描述行由若干个用逗号（，）隔开的字节组成，并以 0
作为形定义的结束字节。每个字节前缀为 0的字节是十六
进制数，而无前缀 0的字节是十进制数。
（ 3）描述行中的每个字节包含矢量长度和矢量方向两种信
息。字节的低四位表示矢量的方向，高四位表示矢量的长
度。矢量的方向编码如图 5.3.1所示。
所有矢量都具有, 相同, 的长度，即不同方向的矢量
长度不一样。例如,45度方向的矢量一个单位长是水平方
向矢量单位长的 sqrt(2)倍。
[例 1] 二极管符号的形定义
二极管符号的矢量走向如图 5.3.2所示。其形定义为：
*133,11,DIODE
040,044,04c,042,04c,040,048,04c,图 5.3.3 大写
字母 A矢量图 02404304d02c04704002e起点下一字符
起点
046,04c,0
[例 2] AUTOCAD所用 TXT字符库中大写字母 A的形定义。
大写字母 A的矢量走向如图 5.3.3所示。其形定义如下：
*65,11,uca
024,043,04d,02c,2,047,1,040,
2,02e,0
其中，字节 2和 1的高四位为 0，是专用码，其含义分别
是抬笔和落笔。图中的虚线表示抬笔，其实是不显示的。
[例 3]用形定义来描述汉字，如, 北京, 两个汉字的形定义
分别为：
*250,17,BEI
024,049,041,044,038,030,044,2,020,1,05c,031,0
39,05c,040,024,0
*251,23,JING
032,2,02c,1,02d,054,028,024,040,02c,028,2,01e
,1,03e,2,086,1,050,025,02d,040,0
请自己分析, 北京, 两个汉字的矢量走向，并验证形定
义的正确性。
可以把若干个形定义放在一个形定义文件中。用这种
方法可以建立 AUTOCAD所使用的各种字体的字符库以及
汉字库。在 AUTOCAD实际使用这种形文件所定义的字符
时，必须通过编译、装入、调用形文件三个步骤。详细使
用方法请参阅 AUTOCAD相关参考书籍。
5.3.2 点阵字符
在点阵字符库中，每个字符都定义成一个称为字符掩
膜的矩阵。矩阵中的每个元素都是一位二进制数，该位为
1时，表示对应此位的像素置成字符颜色，该位为 0时，表
示字符的笔划不经过此位，对应此位的像素为背景色或不
改变。图 5.3.4是字符掩膜的示意图。
一般西文字符的掩膜矩阵尺寸应不小于 5X7，而汉字
字符的掩膜矩阵尺寸应不小于 16X16。在我国早期
广泛使用的微机汉字系统，如 CCDOS等都是采用 16X16
点阵汉字作为显示用字符，打印时可以采用 24X24，
40X40,48X48，甚至 72X72点阵字符。
一个 5X7西文字符点阵包括 35个像素点，需要 35位
二进制数（占四个多字节）来表示。一个 16X16点阵的
汉字，占 16/8X16=32个字节，而一个 72X72点阵汉字，
徐图 5.3.4 字符掩膜矩阵
要 72/8X72=648个字节。
点阵字符库的制作方法。用于打印的高分辨
率点阵字符的掩膜位图，可以通过用扫描仪输入
放大的手写美术字符或印刷字符，然后用交互作
图程序对位图的个别像素进行修改和完善。用于
显示的或用于低分辨率打印机的位图可以使用交
互式绘图程序，通过手工建立。在微机上通常使
用几种不同分辨率的字符库，以满足不同的需要，
例如在 CCDOS4.0中就使用了 24种不同的字符库。
5.3.3 字型技术
当应用对输出字符的要求较高时（如排版印
刷），需要使用高质量的点阵字符。然而，直接
使用上述的点阵字符将浪费大量的存储空间。
对于 GB2312-80所规定的 6763个基本汉字，
假设每个汉字是 72X72点阵，那么一个字库就需
要 4.4M字节存储空间。在实际使用时，通常需要
多种字体，如基本体、宋体、仿宋体、黑提、楷
体等，而每种字体又需要数十种以上的字号。因
此，把每种字体、字号的字符都存储一个点阵，
在一般情况下是不可行的。
解决这个问题一般采用压缩技术。对字型数
据压缩后再存储，使用时，将压缩的数据还原为
字符位图点阵。压缩的方法通常有三种，一是简
单的黑白段压缩法，这种方法简单，还原快，不
失真，但压缩比较差，使用起来也不方便。二是
部件压缩法，这种方法压缩比大，缺点是字型质
量不能保证。三是轮廓字型法，这种方法压缩比
大，且能保证字符质量，是当今国际上最流行的
一种字符压缩方法，基本上也被认为是符合工业
标准的方法。
轮廓字型法采用直线、二次或三次 Bezier曲
线的集合来描述一个字符的轮廓线。轮廓线构成
一个或若干个封闭的平面区域。轮廓线定义加上
一些指示横宽、竖宽、基点、基线等控制信息，
就构成了字符的压缩数据。
下面介绍当前国际上流行的 TrueType字型技
术。它是由美国 Apple和 Microsoft公司联合开发
的，并且已被广泛用于 Windows系统中，可以生
成包括汉字字库在内的多种字库。 TrueType使
用二次 Bezier曲线来描述字符轮廓，对字符轮廓
线的控制点进行编号，其顺序是按照顺时针方向
走一圈，填充的部分始终在其右边。下面以大写
字母 H为例，说明 TrueType字库控制信息。
如图 5.3.5（ a）所示,X方向控制信息有：（ 1）字
身最左起点到字母主干的距离间隔；（ 2）字母主体部分
的宽度；（ 3）字身的宽度；（ 4）字母 H主干的宽度；
（ 5）字母 H的衬线（ Serif）。如图 5.3.5（ b）所示,y
方向的控制信息有：（ 6）字母 H横干的厚度；（ 7）字母
H衬线的厚度；（ 8）字母主体部分的高度；（ 9）字母 H
横干的高度。
上述 9个参数用于产生控制信息表。这个控制信息表
和曲线轮廓定义信息将在不同分辨率情况下产生字符的点
阵中起到关键作用。
字型技术有着广泛的应用，但是在字型数据生成上要
花费大量的人力物力。早期的生产方式是由写字专家写出
字符，然后把字符托到 96X96方格纸上，人为地画出矢量
节点，最后由操作员录入计算机。现在使用的一般方法是
用扫描仪把字符数字化，用程序自动地进行矢量轮廓的生
成，再由操作员对矢量结果进行调整优化，做成合格的字
型。可见，字型的生产是一个周期长，人力和物力消耗大
的工作，好的字型数据来之不易。
5.3.4 字符输出
矢量字符从绘图仪上输出，需要把有关的方向和位移
值转换成设备驱动指令。点阵字符输出到显示器屏幕或打
印机，只要指定字符掩膜的原点与帧缓冲器中的字符左下
角位置（ x0,y0）对应，就可以将字符掩膜中的值平移地
写入到帧缓冲器。伪算法如下：
Writechar(x0,y0,value)
int x0,y0,value;
{
for (j=0;j<=ymax; j++)
for (i=0; i<=xmax; i++)
if (Mask(i,j)<>0)
writepixel(x0+i,y0+j,value);
else
writepixel(x0+i,y0+j,background);
}
在上述算法中,Mask是存放掩膜位图的矩阵，
（ xmin,ymin）和（ xmax,ymax）是掩膜矩阵的左
下角位置和右下角位置的坐标,Value是字符的颜色。
在上述算法中，可以进行简单的修改来获得不同的字体，
如黑体字、斜体字和旋转字体等。例如，只要把掩膜中
每个非零值写入相邻两个单元：（ x0+i,y0+j）和
（ x0+i+1,y0+j），就可以实现黑体字。为了实现斜体
字，只要在写像素时，把原掩膜坐标位移之后，再对 x坐
标加上与 y坐标成比例的位移。
5.3.5 程序设计与实践（四）
一、实验内容：线型与线宽处理技术，字符处理技术
二、实验任务：
1,线刷子绘制直线和圆；
2,方形刷子绘制直线和圆；
3,虚线和点划线的绘制；
4,在 AUTOCAD环境中定义矢量字体（形文件），并使用
矢量字体；
1,点阵字体的读取与显示；
2,熟悉字符输出技术，生成黑体字和斜体字；
三、实验步骤：
（略）
5,4 图形裁剪
在使用计算机处理图形信息时，往往计算机
内部存储的图形比较大，而屏幕显示只是图形
的一部分。例如，虽然计算机内部可以存储全
国地图，但是，如果把全国地图整幅显示在屏
幕上，则看不清各地局部的细节。这是需要使
用缩放技术，把地图中的局部区域放大显示，
这时必须确定图形中那些部分落在显示区内，
那些部分落在显示区外，以便显示落在显示区
内的那部分图形。
这种在给定显示区域的条件下，将图形分为
可见部分与不可见部分，而仅将可见部分送往图
形系统以供显示的过程，称为裁剪（ Clipping）。
当显示窗口内的图形、图形变换以及图形覆盖等
操作时，都需要用到裁剪技术。
在进行裁剪时，对应于屏幕上显示图形的那
部分区域称为窗口。窗口可以是整个屏幕，也可
以是屏幕上的一个矩形，由上、下、左、右四条
边围成，即（ xl,yb），（ xr,yt）。裁剪的实质，
就是决定图形中那些点、线段、文字以及多边形
在窗口之内。
对于点（ x,y），只要判断两对不等式：
xl≤x≤ xr,yb≤y≤yt
若四个不等式均成立，则点在窗口之内；否
则，点在窗口之外。最简单的裁剪方法是把各种
图形扫描转换为点之后，再判断各点是否在窗口
内。
但该方法太费时，一般不可取。这是因为有些图形组
成部分全部在窗口外，可以完全排除，不必进行扫描转换。
所以，一般采用先裁剪，后扫描转换的方法。
本节先讨论线段的裁剪算法，然后再讨论多边形和字
符的裁剪技术。
5.4.1 线段裁剪
线段裁剪是决定线段那些部分在窗口内，那些部分在
窗口外，在直线段扫描转换过程中只考虑窗口内的各点像
素的显示。常用的线段裁剪算法有 Cohen-SutherLand
裁剪算法（编码裁剪法）、中点分割算法、梁友栋 -Brian
裁剪法和参数化方法等。
（一） Cohen-SutherLand裁剪算法
Cohen-SutherLand裁剪算法的思想：对于每条线段
P1P2，分为三种情况处理。（ 1）若 P1P2完全在窗口之
内，则显示该线段 P1P2，简称, 取, 之。（ 2）若 P1P2
明显在窗口外，则丢弃该线段不用考虑，简称, 弃, 之。
（ 3）若线段及不满足, 取, 的条件，也不满足, 弃, 的
条件，则把线段分为两段，其中一段完全在窗口外，可弃
之。然后对另一段重复上输处理。
如图 5.4.1所示，线段 AB两个端点均在窗口内，故整
条线段均可取之显示。线段 CD两个端点均在窗口外，且
两个端点均在窗口下边界的下方，即整个线段处于窗口延
长线的一侧，可弃之。线段 EF,GH,IJ只有一部分落在
窗口内，按第三种情况来处理。线段 KL虽然完全在窗口外，
但没有简单的判断条件，即没有在窗口一侧，故也按第三
种情况来处理。
为了使计算机能够快速判断一条线段与窗口之间的关
系，采用如下的编码方法。延长窗口的边，把未经裁剪的
图形区域分成九个区，如图 5.4.2所示。每个区用 4位二进
制数来表示，从左到右依次表示上、下、右、左。编码规
则如下：
第一位：左边界，端点在左边界的左边（外面）为 1，否则
为 0；
第二位：右边界，端点在右边界的右边（外面）为 1，否则
为 0；
第三位：下边界，端点在下边界的下边（外面）为 1，否则
为 0；
第四位：上边界，端点在上边界的上边（外面）为 1，否则
为 0；
根据编码规则可得到图 5.4.2所示的各区编码。
Cohen-SutherLand裁剪算法是通过编码方法来实现的，
因此，该算法也称为编码裁剪法。
假设要裁剪一条直线段 P1P2，首先求出两个端点 P1、
P2所在区域的编码 code1和 code2。编码裁剪算法藐视如
下：
（ 1）如果线段两个端点的四位编码均为 0，即 code1=0且
code2=0，则说明线段全部在窗口内，应取之；
（ 2）如果线段两个端点出的编码按位, 与, 运算后结果不
为零，即 code1&code2≠0，则说明直线段的两个端点在
窗口的一侧，整个线段不在窗口内，应弃之；
（ 3）如果上述两种条件均不成立，则按第三种情况处理。
求出线段与窗口某边的交点，在交点出把线段一分为二，
其中必有一段完全在窗口外，可以弃之。再对另一段重复
进行上述处理。
例如，图中线段 P1P2两端点处的编码分别为 code1=0001，
code2=0100。由于 code1&code2=0，故属于第三种
情况。由 code1=0001得知 P1在窗口的左边，计算线段
与窗口左边界的交点 P3。 P1P3比在窗口之外，可弃之。
对线段 P3P2重复上述处理。由于 P3处的编码
code3=0000，说明 P3已经在窗口内。由 code2=0100
可知 P2在窗口的下方，计算线段 P3P2与窗口下边界的交
点 P4，丢弃 P4P2，剩下的线段 P3P4就是裁剪的结果，即
在窗口中显示的部分。
在编写程序时，一般是按固定顺序检测区号编码的各
位是否为 0。可按从低位到高位的顺序，即左 -右 -下 -上，
也可以按照从高位到低位的顺序，即上 -下 -右 -左。另外，
程序中舍弃窗口外的子线段，只要用交点的坐标值代替被
舍弃的端点坐标即可实现。
Cohen-SutherLand裁剪算法伪程序如下：
#define LEFT 1 // 0001,左
#define RIGHT 2 // 0010，右
#define BOTTOM 4 //0100,下
#define TOP 8 //1000,上
// 已知端点坐标（ x,y），求其所在区的编码 code。
encode(x,y,code)
float x,y;
int * code;
{
int c; c=0;
if (x<XL) c=c|LEFT;
else if (x>XR) c=c|RIGHT;
if (y<YB) c=c|BOTTOM;
else if (y>YT) c=c|TOP;
*code=c;
return;
}
//Cohen-SutherLand裁剪函数,(x1,y1),(x2,y2)是线段
两个端点坐标，
//XL,XR,YB,YT是窗口的边界定义
C_S_Line(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
{
int code1,code2,code;
encode(x1,y1,&code1);
encode(x2,y2,&code2); // 求出两个端点处的编码
while (code1<>0 || code2<>0) //,||”或者运算，只
要有一个不为 0；
{
if (code1&code2<>0) return; // 表示 code1和
code2在窗口一侧，弃之；
//第三种情况，按照左 -右 -下 -上的顺序求交点
code=code1;
if (code1==0) code=code2;
if (LEFT&code<>0) //线段与左边界的交点
{
x=XL;
y=y1+(y2-y1)*(XL-x1)/(x2-x1);
}
else if (RIGHT&code<>0) //线段与右边界的交点
{
x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-x1);
}
else if (BOTTOM&code<>0) //线段与下边界的交点
{
y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1);
}
else if (TOP&code<>0) //线段与上边界的交点
{
x=YT;
y=x1+(x2-x1)*(YT-y1)/(y2-y1);
}
if (code==code1)
{x1=x;y1=y;encode(x,y,code1);}
else
{x2=x;y2=y;encode(x,y,code2);}
} //end-while
DisplayLine(x1,y1,x2,y2);
Return; } //End C_S_Clip()
（二）中点分割裁剪算法
中点分割裁剪法又称为对分法，其算法思想与编码裁
剪法类似，先对线段端点进行编码，并把线段与窗口的关
系分为三种情况，前两种情况算法处理相同，只是在第三
种情况下，既当一条线段既不能直接接收，也不能直接舍
弃，欲求其与窗口的交点时，不是直接计算线段与窗口边
界的交点，而是将线段等分为两段，并对两端再分别加以
测试。用这种二分法搜索方式一直进行下去，直到找到落
在窗口内显示的部分线段为止。
中点分割裁剪算法描述如下：
（ 1）判断线段是否在窗口内，如果两个端点均在窗口内，
则整个线段都在窗口内；如果线段的两个端点不再窗口内，
且在窗口的同一侧，则该整个线段在窗口外，舍弃之；如
果线段与窗口边界重合，则求出该线段在边框上的起点和
终点坐标。否则，转（ 2）
（ 2）找出该线段离窗口边框最远点和线段的中点，判断中
点是否在窗口内：
（ 1）如果中点不在窗口内，则把中点和离窗口边框最远
点构成的部分线段丢弃掉，以线段上的另一点和线段中点
再构成线段求其中点，重复第 (2)步；
（ 2）如果中点在窗口内，则又以中点和最远点构成线
段，并求其中点，直到中点与窗口边框的坐标值在规定误
差范围内，则该中点就是该线段在窗口内的一个端点，即
可见端点。
（ 3）如果另一点在窗口内，则经过第（ 2）步后即可确
定线段的可见部分。如果另一点不在窗口内，则该点和第
（ 2）求出的可见端点构成新的线段，重复第（ 2）步的过
程，求出另一个可见端点。
（ 4）两个可见端点之间的线段就是裁剪算法的结果，即可
显示部分的线段。图 5.4.3 中点分割裁剪算法示意图
P1P2Pm1Pm2Pm3BA
例如，如图 5.4.3所示，线段 P1P2不满足条件（ 1），转（ 2）
执行；
离窗口边框最远点是 P2,P1P2的中点是 Pm1。因
Pm1在窗口内，则再以 Pm1和 P2构成线段 Pm1P2，再求
中点得到中点 Pm2。由于 Pm2在窗口外，则舍弃
Pm1P2线段，再求 Pm1 Pm2线段的中点，得到 Pm3。
由于 Pm3在窗口内，再求 Pm3 Pm2 的中点,……,直
到 | Pmi+1-Pmi |≤е,е为误差精度。则 Pmi+1为一个可
见端点 A。
然后，执行第（ 3）步，同理求出另一段的可见端点 B。
因此，可以得到裁剪结果，即可视线段部分 AB。 A点称为
P1端点的最远可见端点,B点称为 P2端点的最远可见端点。
由于求线段中点（ x1+x2） /2，（ y1+y2） /2可以
由加法和位移来实现，避免了使用乘除法，所以易于硬件
来实现，算法处理速度很快。另外，采用二分法求可见端
点，查找时间复杂度是 log2M。对于 1024X1024（ 210）
的光栅显示器，则 M=210,log2M=log21024=10,即
最多 10次迭代步骤就可以找到最远的可视点。
（三）梁友栋 -Brian裁剪算法
梁友栋是浙江大学 CAD国家重点实验室
教授，他提出的裁剪算法在国内外也得到
广泛的承认。梁友栋 -Brian裁剪算法的基
本思想是将二维裁剪归结为一维裁剪，把
多边形的裁剪变成解一元不等式组的问题。
设一维直线上有, 窗口, Q1Q2，坐标
q1≤q2，考察该直线上线段 AB，其坐标
a≤b，则窗口内可见部分 VW=AB∩ Q1Q2。
AB与 Q1Q2的关系如表 5.3.1所示。
由上表可归结为下述结论,AB在 Q1Q2上可视线段存
在的充要条件为：
max(min(a,b),min(q1,q2)) ≤
min(max(a,b),max(q1,q2)) （公式 5-1）
可视部分为：
max(min(a,b),min(q1,q2)) ≤x≤
min(max(a,b),max(q1,q2)) （公式 5-2）
例如，图 5.4.4为一窗口和线段 AB，若 AB不平行于窗口边，
则 AB所在直线及其延长线与窗口四边有交点 L,R,T，
U。窗口部分 Q1Q2=LR∩ TU，线段 AB在窗口的部分为：
VW=AB∩ Q1Q2=AB∩ LR∩ TU。（ xl,yb）（ xr,yt）
ABQ1Q2ULTR图 5.4.4 梁友栋 -Brian裁剪算法示例
设窗口左下端点为（ xl,yb），右上端点坐标为
（ xr,yt）,该算法分以下几种情况：
（ 1）若 AB平行于上下窗口边，即 Ay=By,且在窗口其间，
则可视部分 VW=AB∩ LR;
(3) 当 Ax≠Bx，且 Ay≠By,VW存在的充要条件为：
max(xl,min(Ax,Bx),min(Tx,Ux))≤min(xr,max(Ax,
Bx),max(Tx,Ux)) （公式 5-3）
可视线段 VW的 x区间为：
max(xl,min(Ax,Bx),min(Tx,Ux))≤x≤min(xr,max(
Ax,Bx),max(Tx,Ux))
同理，可视线段 VW的 y区间为：
max(yb,min(Ay,By),min(Ly,Ry))≤y≤min(yt,max(Ay
,By),max(Ly,Ry))
(4)当 Ax=Bx时,VW存在的充要条件为：
max(yb,min(Ay,By)) ≤min(yt,max(Ay,By))
当 Ay=By时,VW存在的充要条件为：
max(xl,min(Ax,Bx)) ≤min(xr,max(Ax,Bx))
可视部分：
V=( max(xl,min(Ax,Bx)),max(yb,min(Ay,By)))
W=( min(xr,max(Ax,Bx)),min(yt,max(Ay,By)))
根据以上描述，算法描述（略）。
5.4.2 凸多边形对直线的裁剪
一般的窗口为矩形，但是如果窗口为其它凸多边形时，
裁剪算法描述如下。
（一）基础知识
1．点与直线的相对位置 XYP1P2P3P4A图 5.4.5 点与直线
的关系
设平面上有一直线段 P1P2，和一个点 A。当观察者从
P1走向 P2时,A点始终在观察者的右侧，称 A点在 P1P2
的右侧。如图 5.4.5所示,A点在 P1P2的右侧,A点在
P3P4的左侧。
定理 1：平面上给定直线 P1P2和点 A,A在 P1P2右
侧的充要 条件是：
其中,Det为行列式，点与直线段的齐次坐标分别
是 A(x,y,1),P1(x1,y1,1),P2(x2,y2,1)。
定理证明：略。参见文献：徐宏炳著, 计算机图形
学, P72-74。
根据定理 1可知，已知线段 P1P2和点 A，计算行
列式
若 S=0，则 A在 P1P2直线上；若 S>0，则 A点在
P1P2的左侧；若 S<0,A点在 P1P2的右侧。
推论：已知凸多边形 P1P2P3… Pn-1Pn，
按照顺时针方向走向。判断 A点是否凸多边
形内点的充要条件是：
和
恒成立，则 A为凸多边形内的点。
2．线段与线段相对位置的判断
已知线段 P1P2和 P3P4,它们的相对位置有
三种情况，如图 5.4.6所示。
分析三种位置的计算结果：
第（ 1）情况,S1>0,S2>0,S3>0,S4<0，即 S1S2>0，
S3S4<0；
第（ 2）情况,S1<0,S2>0,S3<0,S4<0，即 S1S2<0，
S3S4>0；
第（ 3）情况,S1<0,S2<0,S3>0,S4>0，即 S1S2<0，
S3S4<0；
结论：当 S1S2<0,S3S4<0时,P1P2 和 P3P4 两线段有
交点 P,则 P满足方程组：
(二 ) 线段与凸多边形相对位置的判断与裁剪
设平面上有线段 L=P1P2,凸多边形 ∏= A1A2A3… An-1An,L与
∏的关系可以通过判断多边形顶点 Pi与 L线段的关系来判断。
可得到如下几种情况：
（ 1）所有的 Si不为 0，且符号相同，说明多边形顶
点在 L的同一侧,∏与 L不相交；
P1P2L∏AjAj+1AKAK+1L1L2 图 5.4.7 线段与
凸多边形相对位置 (1)(2)(3)(4)(5)(6)
（ 2） Si中有 2个为 0，其余同号，说明 ∏在 L的一侧，
且有一条边与 L共线；
（ 3） Si中有 1个为 0，其余同号，说明 L与 ∏的一个
顶点相交,∏在 L的一侧；
（ 4） Si中有 1个或二个为 0，其余有正有
负，这说明 L与 ∏相交，且 L通过 ∏的一个或
二个顶点；
（ 5） Si均不为 0，且有正有负，这说明 L
与 ∏相交，且没有通过 ∏的顶点。
为了说明凸多边形对直线的裁剪算法，
分析第（ 5）种情况，如图 5.4.7所示。因
为 Si,Sj+1<0,SK, Sk+1<0，说明 L必
然通过 L1,AiAj+1和 L2,AkAk+1。分析
P1P2 和 AiAj+1,AkAk+1线段之间的关
系：
设凸多边形 ∏= A1A2A3… An-1An按
顺时针定向,L与 ∏的位置关系如图所示的
6种情况。针对上述情况，分别计算 U1 U2
U3 U4的取值，以及对 L与 ∏的交点可归结
为下表。表中 Q1,Q2表示 L与 ∏的交点，
即 Q1Q2为可视线段。
5.4.3 多边形裁剪
多边形的裁剪就是用矩形窗口来裁剪任意多边
形。对于一个任意多边形，当然可以把它分解成
多条边线段，并逐段裁剪。但是，这样做会使原
来封闭的多边形变成不封闭的或者一些离散的线
段。如果只考虑画线图形，问题还不大。
但是当多边形作为实区域考虑时，封闭多边形裁剪后
仍然应该是封闭多边形，以便进行填充。为了实现多边形
裁剪的目的，可以采用逐边裁剪法和双边裁剪法等算法。
（一）逐边裁剪法
逐边裁剪法（ Reentrant Polygon Clipping）是
1974年由 Sutherland和 Hodgman提出的多边形裁剪算
法。该算法的基本思想是：每次用窗口的一条边界对要裁
剪的多边形进行裁剪，保留包含在窗口内部分，丢掉窗外
部分。四条窗口边界裁剪完成后，所得到的图形就是保留
在窗口内的可视部分。
多边形裁剪会出现完整封闭的多边形裁剪后不再封闭
的问题。解决这个问题的方法是：需要用窗口边界的适当
部分来封闭多边形。
算法的输入是以顶点序列表示的多边形，用 P1
P2 … Pn来表示。算法的输出也是一个顶点序列，构成一
个或多个多边形。如图 5.4.8所示。
算法分析：考虑窗口的一条边及其延长线构成的裁剪
线。该线把平面分成两部分：一部分包含窗口，称为可见
一侧；另一部分为不可见一侧。依次考虑多边形各边的两
个端点 S,P，它们与裁剪线的位置关系只有四种。如图
5.4.9所示。
每条线段端点 S,P与裁剪线比较之后，可输出 0至 2个
顶点。对于情况（ 1）两端点 S,P都在可见一侧，则输出
P。情况（ 2）,S,P都在不可见一侧，则输出 0个顶点。
第（ 3）种情况,S在可见一侧,P在不可见一侧，则输出
线段 SP与裁剪线的交点 I。第（ 4）种情况,S在不可见一
侧,P在可见一侧，则输出线段 SP与裁剪线的交点 I和线
段终点 P。
按照上述算法，分析图 5.4.8的输入和输出结果。
（二）双边裁剪法
1977年 Weiler-Atherton提出了用主多边形 P（用户
图形）的边裁剪多边形 C（窗口），或在某种条件下用 C
的边去裁剪 P的算法，这种算法称为双边裁剪法。它适合
任意多边形的裁剪。
算法的基本思想：对于一个顶点集合 {Vi,i=1~n}有
序排列 的封闭多边形，从其任意一顶点出发，按照顶点
排列的顺序（如按照顺时针方向排列），跟踪检测 P的每
一条边，当 P的边和 C的有效边界相交时，按照如下两种
情况来处理,
若 P的边是进入 C，则算法继续沿着 P的边往下处理；
若 P的边是从 C中出来，则算法将从它们的交点开始，
沿着窗口边界向右检测 C的边，即用 C的有效边框去裁剪 P
的边。若 C的有效边框从交点向右前进遇到与 P的交点，
则返回到交点处继续处理 P的边。
这个过程一直处理到起点为止。被裁剪出来的
落在 C内（包括落在 C的有效边框上）的多边形的
边可以一边处理一边输出，也可以把裁剪出来的
顶点坐标存放起来，等 P处理完毕后一并输出。
如图 5.4.10所示的多边形 P=ABCDEFGA,其
顶点按照顺时针方向排列，从 A点出发，按照双
边裁剪法，分析如下：从 A点出发，首先是从外
向里进入 C，交点 H；从 H开始沿着直线 AB继续，
在交点 I处是从里向外出来，则沿着窗口边界向下，
并检测与 P是否有交点，没有交点直到 O2。同理，
继续沿窗口到 O1，然后到交点 J。由于 DE是从外
向里进入 C,所以从 J开始沿直线 DE到 E,然后到交
点 K。从 K点从里向外出去，所以应沿窗口边界向
右前进，从 K点向右前进到交点 H,然后返还到 K点
继续处理 P。
FG线段从外向里进入 C,交点为 L,所以从 L开始沿 FG线
段继续，到达 M交点。由于是从里向外，所以应沿窗口边
沿向右前进，由 M到 O4，再由 O4到交点 L。得到图
5.4.11的结果。
5.4.4 字符裁剪
前面介绍的字符和文本的输出都是以当前窗口可以容
纳整个字符或文本为前提的。当字符或文本整个不在窗口
时，不予显示就是了。然而，当字符或文本部分在窗口内，
部分在窗口外时，就提出了字符裁剪的问题。
最简单的字符裁剪方法就是把字符方框（即字符掩膜）
与窗口比较，若整个方框位于窗口内，则显示对应的字符，
否则不予显示。这用裁剪以字符为单位进行裁剪，要么全
部显示，要么全都不显示。
有些应用要求更精确的处理：即使字符只有一部分在
窗口内，也要把这部分显示出来。若字符为点阵字型，只
要在把字符掩膜各位写入像素之前，先判断该位对应的像
素是否在窗口内。若该位在窗口内则写，否则就不写。
对于矢量字符，这时就要对跨越窗口边界的笔划进行
裁剪，裁去笔划伸到窗外的部分，保留笔划在窗内的部分，
这个问题就转化为线段的裁剪。
字符串的裁剪，可以按三种精度来进行：串精确度、
字符精确度以及笔划 /像素精确度。采用串精确度进行裁
剪时，当字符串方框整个在窗口内予以显示，否则不显示。
采用字符精确度时，当字符串的某个字符方框整个在窗口
内时显示该字符，否则不显示。当采用笔划 /像素精度时，
要具体判断字符串中各字符的哪些像素、笔划的哪一部分
在窗口内，处理方法同字符裁剪。
5,5 反走样技术
在光栅图形显示器上绘制非水平和非垂直的线段时，
或多或少会出现锯齿状。这是由于直线段在光栅图形显示
器上对应的图形都是有一系列相同亮度的离散像素构成的。
这种用离散量表示连续量引起的失真，就叫做走样
（ aliasing）。
而用于减少或消除这种效果的技术，就称为反走样
（ antialiasing）。常用的反走样方法可分为两类：其中
一类基于提高分辨率，即增加采样点；另一类是把像素作
为一个有限区域，对区域采样。
5.5.1 提高分辨率
图 5.5.1 直线扫描转换像素示意图
在直线段扫描转换算法中，总是选择离理想直线最近
的一个像素，并置为直线颜色。每当前一列所选的像素与
后一列所选的像素不同行时，就会出现一个锯齿。如图
5.5.1（ a）所示。现在假设把显示器分辩率提高一倍，直
线经过的像素增加一倍，锯齿的个数也增加了一倍。但是，
由于每个锯齿在 x方向与 y方向都只有低分辨率的一半，锯
齿幅度比较小，所以效果看起来会好一些。这种改进是以
4倍的存储器代价和扫描转换时间获得的。因此，增加分
辨率是不经济的方法，它只能减轻而不能消除锯齿。
提高显示器分辨率属于 物理上增加显示像素,而显示
器的分辨率是由图形系统硬件所决定的。显示器分辨率越
高，图形显示的效果就越好。另一种方法是 通过数学插值
的方法,在较高的分辨率中进行计算，然后采用某种平均
算法，把结果转化到较低分辨率的显示器上进行显示。
101112202122图 5.5.2 数学插值子像素示意图
421212121
如图 5.5.2所示，实线表示低分辨率的像素位置，设
想将每个正方形像素区域分成九个等尺寸的子像素，用虚
线表示，阴影区域表示由 Bresnham算法选择的子像素位
置。由于这些子像素位置是不存在的，我们可以将子像素
所在的实际像素的亮度等级设置为正比于这些子像素数目
的值，用不同的灰度显示来提高显示的质量。因为任何像
素中可供选择的子像素最大个数为 3，这种方法提供零以
上三种亮度设置。在例子中，位置（ 10,20）处的像素包
括了三个子像素，设置为最高亮度（级别 3）；位置
(11,21)和（ 12,21）两处的像素包括两个像素，设置为
次亮度（级别 2）；位置（ 11,20）和（ 12,22）两处都
包含了一个子像素，设置为最低亮度（级别 1）。
这样处理以后，线亮度分布在较大数目像素上，
并且通过在阶梯状台阶（水平长度间）附近显示
有些模糊的线路经使阶梯形状得到光顺。如果用
更多的亮度等级来利用反走样线，就需要增加每
个像素中的取样位置数，例如 16个子像素给出 4
个亮度级； 25个子像素给出 5个等级。
另外，可以采用 像素加权掩膜技术 来计算实际
像素的灰度。图 5.5.2中位置 (10,22)处给出了
3х3子像素的加权值方案。中心子像素取最大的
权值，因为这些子像素在确定像素的整体亮度中
起更重要的作用。根据子像素的个数和位置计算
每个实际像素的平均亮度。这样的结果是：中心
子像素的加权系数为 1/4，上、下、左、右四个
子像素的加权系数为 1/8，而四角的四个子像素
的加权系数为 1/16。指定子像素相对重要性值的
数组称为子像素的加权, 掩膜, （ mask）。
101112202122图 5.5.3 宽度线内部相关子
像素的位置
5.5.2 简单的区域取样
下面考虑显示线宽的情况。在前面的例子中，
我们都是把线当作具有零宽度的数学实体。实际
上，显示的线具有约与像素等宽的宽度。假如把
线的宽度考虑进去，可通过将每个像素的亮度设
置成正比于在表示线区域多边形内的像素数目来
完成。若子像素的左下角在多边形内，那么可把
此子像素当作在线内。这样做的好处是：每个像
素可能的亮度等级等于像素区域内子像素的总数。
如图 5.5.3所示，可以通过对平行于线路径的多边
形边界定位，以有限的宽度来表示这样的线。并
且每个像素现在可以设置成零以上九个亮度级别
之一。
在具有多级灰度的显示器上绘制一条直线段时，
若一个像素整个落在线区域的长方形内，则将它
设置为直线颜色。如果一个像素与线段相交，根
据相交部分的大小来选择不同的灰度。相交部分
多的像素颜色更深一些，相交部分少的像素颜色
相对浅一些。这种方法将产生模糊的边界，以此
来减轻锯齿效应。
5.5.3 过滤技术
反走样更精确的方法是采用过滤技术。这种
方法类似于应用加权像素掩膜，只是现在假想一
个连续的加权曲面（或称过滤函数）覆盖像素。
包括正方形、圆锥形和高斯过滤函数等，如图
5.5.4所示。应用过滤函数的方法类似于应用加权
掩膜，但现在是将像素曲面集成来得到加权的平
均亮度。为减少计算量，常采用查表法求整数值。
5,6 程序设计与实践（五）
一、实验内容：线段裁剪和多边形裁剪算法
二、实验任务：
编码裁剪算法的程序设计，要求用鼠标
画线技术；
三、实验步骤：
作业与练习
提纲：
? 1,区域填充；
? 2,线宽与线型处理
? 3,字符显示与处理
? 4,裁剪处理
? 5,反走样技术
5.1 区域填充
区域填充的任务是在一个封闭的区域
中的所有像素，用一种颜色或图案位图来
显示。区域填充可以分两步进行，第一步
先确定填充的区域，第二步确定用什么颜
色值来填充。 在本节中，我们首先讨论如
何用单一颜色填充多边形与图形区域，然
后再讨论图案填充。
5.1.1 多边形域的填充
1．原理描述
这里讨论的是任意多边形，多边形域可以是
凸的、凹的或带孔的。一种常用的填充方法是按
扫描线顺序，计算扫描线与多边形的相交区间，
再用要求的颜色显示这些区间的像素，即可以完
成填充工作。区间的端点可以通过计算扫描线与
多边形边界线的交点获得。
如图 5.1.1所示，扫描线 6与多边形的边界线
交于四点 A,B,C,D。这四点把扫描线分为五
个区间 [0,2],[2,3.5],[3.5,7],[7,11]、
[11,12]。其中 AB[2,3.5],CD[7,11]两个区间
落在多边形内，该区间内的像素应取多边形填充
色，其他区间内的像素取背景色。
P1(2,2)
P2(5,1)
P3(11,3)
P5(5,5)
P4(11,8)P
6(2,7)
E
A B C DD
GF
0 1 2 3 4 5 6 7 8 9 10 11 x
1
2
3
4
5
6
7
8
y
图 5.1.1 一个多边形与若干扫描线
这里的四个交点在计算时未必是按从左到右
顺序获得。例如，当多边形采用顶点序列
P1P2P3P4P5P6表示时，把扫描线 6分别与 P1P2、
P2P3, P3P4, P4P5, P5P6, P6P1 六条边
相交，得到交点序列为 D,C,B,A，必须经过
排序，按 x递增的顺序排列交点顺序，才能得到从
左到右排列的交点序列。
一般多边形的填充过程，对于一条扫描线，
可以分为四个步骤：
(1)求交：计算扫描线与多边形各边的交点；
(2)排序：把所有交点按 x递增顺序进行排序；
(3)交点配对：第一个与第二个，第三个与第四
个,…,第 2i-1与第 2i个交点配对，其中,i取
1~n。每对交点就代表扫描线与多边形的一个相
交区间。
(4)区间填色：把这些相交区间内的像素置成多边
形填充色，把区间外的像素置成背景色。
在多边形填充算法中，必须解决两个特殊的问题：一
是当扫描线与多边形顶点相交时，交点的取舍问题。二是
多边形边界上像素的取舍问题。前者用于保证交点正确配
对，后者用于避免填充扩大化。
先讨论第一个问题。当扫描线与多边形顶点相交时，
会出现异常情况。例如图 5.1.1中过的与 P1,P2,P5、
P6点的扫描线，算几个交点，如果取舍不正确，交点配对
和填充就会出现错误。
为了正确地进行交点取舍，必须按照下面的规则对交
点进行取舍：
(1)扫描线交于一顶点，而共享该顶点的两条边分别落在
扫描线的两边，则交点只算一个。如图 5.1.2(a)。
(2)扫描线交于一顶点，而共享该顶点的两条边在扫描线
的同一边，这时交点作为零个或两个，这取决于该顶点是
多边形的局部最高点（ 0个）还是局部最低点（ 2个）。如
图 5.1.2(b)和如图 5.1.2(c)。
A
B C A
B
C
C
B
A
(a)
取
一
个
(b)
取
零
个
(c)
取
二
个
图 5.1.2 扫描线与多边形顶点相交时交点的取舍
具体实现时，只需检查顶点的两体条边的另外两个端
点的 y值，如果两个 y值中大于交点出 y值的个数是 0,1、
2，那么交点分别取零个、一个或二个。
按照上述规则，图 5.1.1中的顶点 P2,算两个交点，
这样 P2 像素用多边形颜色设置。在顶点 P1 处，只算一个
交点。而在 P6 处，交点算零个，即该点不予填充。
下面讨论第二个问题，即边界上像素的取舍问题。例
如，对左下角为 (1,1)，右上角为 (3,3)的正方形填充时，
若对边界上所有的像素均进行填充，就得到如图 5.1.3的
结果，被填充的像素覆盖的面积为 3х3单位，而正方形的
实际面积只有 2х2单位。这种现象称为边界扩大化问题。
为了克服这个问题，规定落在右 /上边界的像素不予填充，
而落在左 /下边界的像素予以填充。在具体实现时，只要
对扫描线与多边形的相交区间取左闭右开。容易看出，在
解决第一个问题时，对交点的取舍方法保证了多边形的
,下闭上开,,即丢弃上方水平边以及上方非水平边上作
为局部最高点的顶点。
1 2 3 4 x
1
2
3
4
y
图 5.1.3 边界上像素的填充
2．采用的数据结构
（ 1）活性边表
为了计算每条扫描线与多边形各边的交点，最简单的
方法是把多边形的所有边放在一个表中。在处理每条扫描
线时，按顺序从表中取出所有的边，分别与扫描线求交。
这样处理效率很低，这是因为一条扫描线往往只与少数几
条边相交，甚至与整个多边形都不相交。为了提高效率，
在处理一条扫描线时，仅对与它相交的多边形的边进行求
交运算。我们把与当前扫描线相交的边称为活性边，并把
它们按与扫描线交点 x坐标递增的顺序存放在一个链表中，
称此链表为活性边表。
活性边表的每个结点存放对应边的有关信息，如扫描
线与该边的交点 x，边所跨的扫描线条数等。由于边的连
贯性（即当某条边与当前扫描线相交时，它很可能也与下
一条扫描线相交），以及扫描线的连贯性（即当前扫描线
与各边的交点顺序与下一条扫描线与各边的交点顺序很可
能相同或非常类似），在当前扫描线处理完毕之后，不必
为下一条扫描线从头开始构造活性边表，而只要对当前扫
描线的活性边表稍作修改和更新，就可以得到下一条扫描
线的活性边表。具体原理讨论如下：
假设当前扫描线与多边形的某一条边的交点坐标为 x，
那么下一条扫描线与该边的交点不必从头计算，只要加上
一个增量即可。设边的直线方成为
ax+by+c=0
若 y=yi时,x=xi，则当 y=yi+1时，
xi+1=(-byi+1-c)/a=(-b(yi+1)-c)/a=(-b yi -
c)/a-b/a=xi-b/a
其中△ x=-b/a为常量。△ x可以存放在对应边的活性
边表结点中。另外，使用增量法计算时，我们需要知道一
条边何时不再与下一条扫描线相交，以便及时把它从活性
表中删除，避免下一步无谓的计算。
综上所述，活性边表的结点中至少应为对应边保存如
下内容：
x,当前扫描线与边的交点；
△ x：从当前扫描线到下一条扫描线之间的 x增量；
ymax,边所交的最高扫描线号。
若规定多边形的边不自交，则从当前扫描线
延续到下一条扫描线，边与下一条扫描线的交点
顺序保持不变。否则，到下一条扫描线，必须重
新排序。由于扫描线的连贯性，新交点序列与旧
交点序列基本一致，最多只有个别需要调整。因
此，采用冒泡排序法可获得较好效果。对于下一
条扫描线新交上的边，则必须在当前扫描线处理
完之后的更新过程中，插入到活性边表的适当位
置，并保持有序性。这个过程采用插入排序最适
宜。另外，在上述的交点 x坐标更新和新边插入之
前，必须把那些与当前扫描线有交，而与下一条
扫描线不再相交的边，从活性边表中删除。图
5.1.4中，扫描线 6的活性边表如图（ a）所示，
扫描线 7的活性边表如图（ b）所示。
2 0 7 3.5 -1.5 7 7 2 8 11 0 8
9 2 8 11 0 8 Λ
通过活性边表，可以充分利用边的连贯性
和扫描线的连贯性，减少求交计算量与提高排
序效率。
（ 2）新边表
为了方便活性边表的建立与更新，为
每一条扫描线建立一个新边表，存放在该
扫描线上第一次出现的边。也就是说，若
某边的较低端点为 ymin，则该边就放在扫
描线 ymin的新边表中。这样，当我们按扫
描线号从小到大顺序处理扫描线时，该边
在该扫描线第一次出现。新边表的每个结
点存放对应边的初始信息。如该扫描线与
该边的初始交点 x（即较低端点的 x值）,x
的增量△ x以及该边的最大 y值 ymax。新边
表的边结点不必排序。图 5.1.5是各扫描线
的新边表。
Λ
Λ
Λ
Λ
5 2 8
5 -1.5 7 Λ
（ 3）多边形区域填充算法
在活性边表的基础上，进行交点配对和区间填充是很
容易的事。只要设置一个布尔量 b，规定在多边形内时,b
取真值，在多边形外时,b取假。令指针从活性边表中第
一个结点（交点）到最后一个结点遍历一次，每访问一个
结点，把 b取反一次。若 b为真，则把从当前结点的 x值开
始到下一结点的 x值结束的左闭右开区间用多边形填充色
进行填充。这样就可以完成多边形内的像素取多边形色，
多边形外的像素取背景色。
多边形区域填充算法描述如下：
Polygonfill(polydef,color)
int color;
多边形定义 polydef;
{
for (各条扫描线 i)
{
初始化新边表表头指针 NET[i];
把 ymin=i的边放进边表 NET[i];
}
y=最低扫描线号；
初始化活性边表 AET为空；
for (各条扫描线 i)
{
把新边表 NET[i]中的边结点用插入排序法插入 AET表，
使之按 x坐标递增顺序排列；
遍历 AET表，把配对交点之间的区域（左闭右开）上的
各像素 (x,y)，用 DrawPixel(x,y,color)设置填充颜色；
遍历 AET表，把 ymax=i的结点从 AET表中删除，并把
ymax>i结点的 x值递增△ x；
若允许多边形的边子相交，则用冒泡排序法对 AET
表重新排序；
}
} /* End Polygonfill */
多边形区域填充算法又称为有序边表
算法，该算法对显示的每个像素只访问一
次，这样，输入 /输出的要求可降低为最少。
有由于该算法与输入 /输出的细节无关，因
而它也是与设备无关的。该算法的主要缺
点是对各种表的维持和排序开销太大，适
合软件实现而不适合硬件实现。
5.1.2 边填充算法
1．原理描述
边填充算法的基本思想：对于每一条
扫描线和每条多边形边的交点（ x1,y1），
将该扫描线上交点右方的所有像素取补。
对多边形的每条边作此处理，多边形的顺
序随意。如图 5.1.6是一个简单边填充算法
的示意图。
P1 P2
P3
P4
P5
P2P3 P3P4
P4P5 P5P1
图 5.1.6 边填充算法示意图
边填充算法最适用于具有帧缓冲器的图形系
统，按任意顺序处理多边形的边。在处理每条边
时，仅访问与该边有交的扫描线上交点右方的像
素。当所有的边都被处理之后，按扫描线顺序读
出帧缓冲器的内容，送入显示设备。该算法的优
点是简单，缺点是对于复杂图形，每一像素可能
被访问多次，输入输出的量也比较大。
为了减少边填充算法访问像素的次数，可引
入栅栏。所谓栅栏指的是一条与扫描线垂直的直
线，栅栏位置通常取过多边形顶点、且把多边形
分为左右两半。栅栏填充算法的基本思想是：对
于每条扫描线与多边形边的交点，就将交点与栅
栏之间的像素取补。若交点位于栅栏左边，则将
交点置右，栅栏之左的所有像素取补；若交点位
于栅栏右边，则将栅栏置右，交点之左的像素取
补。图 5.1.7是采用栅栏填充算法的示意图。栅栏
填充算法只是减少了被重复访问像素的次数，但
仍有一些像素会被重复访问。
P1 P2
P3
P4
P5
P2P3 P3P4
P5P1
栅栏线
P4P5
图 5.1.7 栅栏填充算法示意图
边标志算法分为两个步骤：
第一步，对多边形的每条边进行直线扫描转换，即
对多边形边界所经过的像素打上边标志。
第二步，填充。对每条与多边形相交的扫描线，依
从左到右顺序，逐个访问该扫描线上像素。使用一个布
尔量 inside来指示当前点的状态，若点在多边形内，则
inside为真。若点在多边形外，则 inside为假。
Inside的初值为假，每当当前访问像素为被打上边标
志的点，就把 inside取反。对未打标志的像素，
inside不变。若访问当前像素时，对 inside作必要操
作之后,inside为真，则把该像素置为多边形色。
边标志算法描述如下：
#define FALSE 0
edge_mark_fill (polydef,color)
多边形定义 polydef;
int color;
{
对多边形 polydef每条边进行直线扫描转换；
inside=FALSE;
for (每条与多边形 polydef相交的扫描线 y)
for (扫描线上每个像素 x)
{
if (像素 x被打上边标志 )
inside= !(inside);
if (inside !=FALSE)
drawpixel(x,y,color);
else
drawpixel(x,y,background);
}
}
用软件实现时，有序边表算法与边标志算法执行速度
几乎相同，但由于在帧缓冲器中应用边标志算法时，不必
建立和维护边表以及对它进行排序，所以边标志算法更适
合硬件实现。
5.1.3 种子填充算法
1．原理和方法
种子填充算法是假设在多边形区域内部取一点（像
素），由此出发找到区域内所有像素。该算法要求区域采
用边界定义，即区域边界上所有像素均具有某个特定值，
而区域内部所有像素均不取这一特定值。
区域可以分为四向连通和八向连通两种。四向连通区
域指的是从区域上一点出发，可通过四个方向，即上、下、
左、右移动的组合，在不越出区域的前提下，到达区域内
的任意像素。八向连通区域指的是区域内每一个像素，可
以通过左、右、上、下、左上、右上、左下、右下这八个
方向的移动组合来达到。
种子填充算法中允许从四个方向寻找下一个像素者，
称为四向算法；允许从八个方向搜索下一像素者，称为八
向算法。八向算法既可以填充八向连通区域，也可以填充
四向连通区域。但是，四向算法只能填充四向连通区域，
而不能填充八向填充区域。
下面只考虑四向算法。
可以使用栈结构来实现简单的种子填充算法，
其原理如下：种子像素如栈，当栈非空时，重复
如下三步操作：
1,栈顶像素出栈；
2,将出栈像素置成多边形色，即填充色；
3,按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素不在边界且未被置成
多边形色，则把该像素入栈。
举例，如图 5.1.9所示，为一个用边界表示
的区域，其中 s1(2,3)为种子像素，用简单的种
子填充算法对该区域进行填充，各像素的出栈顺
序分析如下：
步骤：
（ 1） s1入栈，
栈,s1;
（ 2） 出栈,s1，即（ 2,3）
入栈,4,7,9,2；
栈,4,7,9,2；
（ 3） 出栈,2，即（ 1,3）
入栈,3,8
栈,4,7,9,3,8
（ 4） 出栈,8，即（ 1,4）
入栈：没有
栈,4,7,9,3
（ 5） 出栈,3，即（ 1,2）
入栈：没有
栈,4,7,9
（ 7） 出栈,7，即（ 3,3）
入栈,6
栈,4,6
（ 8） 出栈,6，即（ 3,2）
入栈：没有
栈,4
（ 9） 出栈,4，即（ 2,2）
入栈,5
栈,5
（ 10）出栈,5，即（ 2,1）
入栈：没有
栈：空
程序结束。
编写程序实现上述算法。可以定义一个大型数组来
模拟栈结构，如 stack[2000]。
简单种子填充算法把太多的像素压入堆栈，有些像素
甚至会如栈多次，这一方面降低了算法的效率，另一方
面还要求很大的存储空间以实现栈结构。其改进算法是：
在任意一条扫描线与多边形的相交区间（含若干个连续
像 素）中，只取一个种子像素，相应的算法称为扫描线
填充算法。算法原理如下：种子像素入栈，当栈非空时
作如下四步操作：
(1)栈顶像素出栈；
(2)沿扫描线对出栈像素的左右像素进行填充，
直至遇到边界像素为止，即每出栈一个像素，就
对包含该像素扫描线上的整个区间进行填充；
(3)上述扫描线区间内的最左、最右的像素分别
记为 xl和 xr；
（ 4） 在区间 [xl,xr]中检查与当前扫描线相邻
的上下两条扫描线的有关像素是否全为边界像
素或已填充的像素，若存在非边界、未填充的
像素，则把每一区间的最右像素取为种子像素
入栈。
扫描线填充算法程序描述如下：
scanline_seed_fill(polydef,color)
多边形定义 polydef;
int color;
{
int x,y,x0,xl,xr;
push(seed(x,y)); /*种子像素入栈 */
? while (像素栈非空 ) {
? pop(pixel(x,y)); /*栈顶像素出栈 */
? drawpixel(x,y,color);
? x0=x+1;
while (pixel(x0,y)的值不等于边界值 ) /*填充右
方像素 */
{
drawpixel(x0,y,color);
x0=x0+1;
}
xr=x0-1; /*记录最右像素 xr*/
x0=x-1; /*填充左方像素，像素起点 */
while (pixel(x0,y)的值不等于边界值 )
{
drawpixel(x0,y,color);
x0=x0-1;
}
xl=x0+1; /*记录最左像素到 xl中 */
/*种子像素的左右像素填充完毕，下面分别向上、
向下逐条扫描线填充 */
/*检查上一条扫描线，若存在非边界且未填充的像
素，则选取代表各连续区间的种子像素入栈 */
x0=xl; y=y+1;
while (x0<=xr)
{
flag=0;
while ((pixel(x0,y)的值不等于边界
值 )&&(pixel(x0,y)的值不等
于多边形色 )&&(x0<xr))
{
if (flag= =0) flag=1;
x0++;
}
if (flag= =1)
{
if ((x0= =xr)&&(pixel(x0,y)的值不等
于边界值 )&&(pixel(x0,y)的值不等于
多边形色 ))
push(pixel(x0,y));
else
push(pixel(x0-1,y));
flag=0;
} /*end if*/
xnextspan=x0;
while ((pixel(x0,y)等于边界
值 )||(pixel(x0,y)等于多边形色 )&&(x0<xr))
x0++;
if (xnextspan= =x0) x0++;
} /* end while (x0<=xr)*/
/*检查下一条扫描线，若存在非边界，未填充
的像素，则选取代表各连续区间的种子像素入栈；
算法与前面处理上一条扫描线算法完全一样，只
要把 y+1换成 y-1即可 */
} /*end while 像素栈非空 */
}
5.1.4 区域填充图案
在实际应用中，有时需要用一种图案来填充平面区域，
其原理是在上述扫描转换算法基础上稍作修改来实现：在
确定了区域内一个像素之后，不是马上往该像素填色，而
是先查询图案位图的对应位置。若是透明方式填充图案，
则当图案表的对应位置为 1时，用前景色写像素，否则，
不改变该像素的值。而若以不透明方式填充图案，则视图
案位图对应位置为 1或 0来决定是用前景色还是用背景色去
写像素。
1．位图（ bitmap）填充
假设填充图案是一个 MxN的位图，用 MxN数
组存放。 M,N一般比需要填充的区域的尺寸小得
多。所以图案总是设计成周期性的，使之能通过
重复使用，构成任意尺寸的图案。
当需要填充的区域与当前扫描线的相交区间确定
之后，假定相交区间上一个像素的坐标为（ x,y），
则图案位图上的对应位置为（ x%m,y%n），其
中 %为 C语言整除取余运算符。若采用不透明方
式填充图案，则应把算法 polygonfill中无条件地
使用前景色 color写像素操作
drawpixel(x,y,color)，改成当图案值为 1时，
用前景色 color写，否则，用背景色 background
写，即 if (pattern(x%m,y%n))
drawpixel(x,y,color);
Else
drawpixel(x,y,background);
如果采用透明方式填充图案时，只要去掉 else分
句即可。
2．填充图案的保存与重写
可以将已经填充图案的图形的各像素读到一
个数组中。设该图形的外接矩形宽为 wide，高为
height，矩形的左上角坐标为（ x0,y0），数组
为 symbol[]，则保存程序为：
for (i=0;i<wide; i++)
for (j=0;j<height; j++)
symbol[i,j]=getpixel(x0+i,y0+j);
填充图案的重写：当需要把保存在 Symbol[]数组
中的图形再次写到屏幕从（ i0,j0）开始的位置上
时，则重写程序如下：
for (i=0;i<wide; i++)
for (j=0;j<height; j++)
if (symbol[i,j])
putpixel(i0+i,j0+j,symbol[i,j]);
5.1.5 程序设计与实践（三）
一、实验内容：区域填充算法程序设计
二、实验任务：
1,多边形有序边表算法程序设计；
2,边填充算法和边标志填充算法；
3,简单的种子填充算法和扫描线填充算法；
4,区域填充图案程序设计；
三、实验步骤
要求完成：
（ 1）边标志填充算法；
（ 2） 简单种子填充算法或扫描线填充算法；
（ 3）区域填充图案算法
5,2 线型与线宽处理
5.2.1 直线线宽的处理
在实际应用中，除了使用单像素宽的线条，还经常使
用指定线宽和线型的直线与弧线。与产生具有线宽的线条，
可以顺着扫描线所生成的单像素线条轨迹，移动一把具有
一定宽度的, 刷子, 来获得。, 刷子, 的形状可以是一条
线段或一个正方形，也可以采用区域填充的办法间接地产
生有宽度的线。
线刷子的工作原理：假设直线斜率在 [-1,1]之间，
这时可以把刷子置成垂直方向，刷子的中点对准直线一端
点，然后让刷子中心往直线的另一端移动，即可, 刷出,
具有一定宽度的线段。当直线斜率不在 [-1,1]之间时，把
刷子置成水平方向。
在具体实现线刷子时，只要对直线扫描转换算法的内
循环稍作修改。例如，当直线斜率在 [-1,1]之间时，把
每步迭代所得的点上下方半线宽之内的像素全部置成直线
颜色。
图 5.2.1 线刷子产程的缺口
线刷子的优点是算法简单、效率高，但是，
由于线的始末端点总是水平或垂直的，因此，当
线宽较大时，看起来很不自然。当比较接近水平
线和比较接近垂直线汇合时，汇合处外角将有缺
口，如图 5.2.1所示。另外，线刷子的线条不一样
粗细。对于水平线和垂直线，刷子与线条垂直，
因而线最粗，其粗细等于线宽。而对于 45度斜线，
刷子与线成 45度角，线的粗细仅为指定线宽的
1/sqrt(2)=0.7倍。还有一个问题，当线宽为偶
数个像素时，用上述算法绘制的线条，要么粗一
个像素，要么细一个像素。
方形刷子工作原理是：把正方形中心对准单
像素宽线条上各个像素，并把方形内的像素全部
置成线条颜色。这种方法将会重复地写像素，这
是因为对应于相邻两个像素的方形会产生重迭。
用方刷子所得的线条比用线刷子所绘制的线
条要粗一些。用方刷子绘制的线条始末端也是水
平或垂直的，且线宽与线条方向有关，对于水平
与垂直线，线宽最小，而对于斜率为 1或 -1的线
条，线宽最大，为垂直线（水平）线宽度的
sqrt(2) 倍。
生成具有宽度的线条还可以采用区域填充的
算法。先算出线条各角点，再用直线段把相邻角
点连接起来，最后调用多边形填充算法把所得的
四边形进行填充，即得到具有宽度的线条。
5.2.2 圆弧线宽的处理
为了生成具有宽度的圆弧，可采用与直线情形类
似的方法。当采用线刷子时，在经过曲线斜率为 1
或 -1的点时，必须把线刷子在水平与垂直方向之
间切换。由于线刷子总是置成水平或垂直的，所
以在曲线接近水平与垂直的地方，线条更粗一些，
而在斜率接近 1或 -1的点附近，线条更细一些。
当采用正方形刷子时，无须移动刷子方向，只
需要顺着单像素宽的轨迹，把正方形中心对准轨
迹上的像素，把正方形内的像素全部用线条颜色
填充。用正方形刷子绘制的曲线条，在接近水平
与垂直的部分最细，而在斜率为 1或 -1点附近最
粗，这恰好与线刷子情形相反。
绘制具有宽度的圆弧线条也可以采用填充的
办法，先绘制圆弧线条的内边界和外边届，然后
在内外边界之间对其填充。可以让内外边界与单
像素弧线轨迹距离班线宽，或把内外边界之一对
准单像素弧线轨迹，另一边界线离开此线一个线
宽距离。
5.2.3 线型的处理
在绘图应用中，常用到不同线型的线条。如
实线、虚线、点划线等。
线型可以用一个布尔值的序列来存放。例如，
用一个 32位整数可以存放 32个布尔值。
用这样的整数存放线型定义时，线型必须以 32个像素
为周期进行重复。可以把扫描转换算法中的无条件写像素
语句改为：
if (位串 [i%32]) drawpixel(x,y,color);
其中 i为循环变量，在扫描转换算法的内循环中，每处理
一个像素递增 1，然后除以 32取余。
5,3 字符与字形技术
在计算机图形学中，处理对象不仅包括点、线、曲线
等基本图形的显示与处理，同时还包括字符和字形的处理
和显示技术。字符处理在计算机图形学中是必不可缺少的
一部分。本节主要讨论字符生成与输出技术，以及字形处
理技术。
在计算机图形学中的字符是指数字、字母、汉字等符
号，用于图形的标注和说明。国际上通用的字符集是
ASCII码。该字符集规定了 127个字符代码，其中代码
0~31用于表示控制字符； 32~127表示大、小写 26个英
文字母、标点符号、运算符以及特殊符号等。每个 ASCII
码用一个字节（实际只有 7位，最高位为 0）代码表示。
为了规范汉字的处理，我国也制定了汉字代
码的国际标准，最常用的汉字字符集是, 信息交
换用汉字编码字符集基本集, GB2312-80。 。
该字符集包含了六千多个常用汉字，以及英文字
母、数字及其它图形符号。 GB2312-80字符集
分成 94个区，每区 94个位。区码和位码各用一个
字节（实际只有 7位）来表示。为了区别 ASCII码
和汉字编码，用字节的最高位来标识。当最高位
为 0，表示 ASCII码，最高位为 1，表示汉字编码。
例如，
01000100 11001100 10011001 01100111
ASCII 汉字 ASCII
为了在显示器上生成字符，系统中必须装备
有相应的字符库。字符库中储存了每个字符的形
状信息。根据字符生成方式的不同，分为矢量型
和点阵型两种字库。矢量型字符库采用矢量代码
序列表示字符的各个笔画，当输出一个字符时，
通过输出该字符各矢量，以产生相应的字符。矢
量型字符易于放大、缩小等变换，矢量型字符也
适宜于笔式绘图仪等矢量设备上使用。点阵型字
符库是为每一个字符定义一个字符掩膜，即表示
该字符像素图案的一个点阵。在终端显示器上显
示字符，一般采用点阵型字库。
5.3.1 矢量字符
矢量字符是用一系列的矢量段表示的字符。
为了建立一个矢量字符库，必须为每一个字符定
义一个矢量代码序列。建立矢量字符库的方法很
多，下面以 AUTOCAD系统使用的矢量字符来说
明矢量字符建立的方法。
在 AUTOCAD中，使用一种称为形（ shape）的图形
实体来定义英文字母、汉字，甚至是一种简单的图形。形
定义中使用直线和圆弧作为基本笔划。
每个形的定义包括一个标题行和若干描述行，形式如
下：
*形编码，字节数，形名称
字节 1，字节 2,……, 0
注：
（ 1）标题行以 *号开始，形编号是 1到 255的整数值。字节
数表示定义描述行中包括结束符 0在内的字节数。形名称
用大写字母书写才能被调用，否则只能作为形的一种解释
性信息，不存入存储器，因而也不占用存储空间。
（ 2）描述行由若干个用逗号（，）隔开的字节组成，并以 0
作为形定义的结束字节。每个字节前缀为 0的字节是十六
进制数，而无前缀 0的字节是十进制数。
（ 3）描述行中的每个字节包含矢量长度和矢量方向两种信
息。字节的低四位表示矢量的方向，高四位表示矢量的长
度。矢量的方向编码如图 5.3.1所示。
所有矢量都具有, 相同, 的长度，即不同方向的矢量
长度不一样。例如,45度方向的矢量一个单位长是水平方
向矢量单位长的 sqrt(2)倍。
[例 1] 二极管符号的形定义
二极管符号的矢量走向如图 5.3.2所示。其形定义为：
*133,11,DIODE
040,044,04c,042,04c,040,048,04c,图 5.3.3 大写
字母 A矢量图 02404304d02c04704002e起点下一字符
起点
046,04c,0
[例 2] AUTOCAD所用 TXT字符库中大写字母 A的形定义。
大写字母 A的矢量走向如图 5.3.3所示。其形定义如下：
*65,11,uca
024,043,04d,02c,2,047,1,040,
2,02e,0
其中，字节 2和 1的高四位为 0，是专用码，其含义分别
是抬笔和落笔。图中的虚线表示抬笔，其实是不显示的。
[例 3]用形定义来描述汉字，如, 北京, 两个汉字的形定义
分别为：
*250,17,BEI
024,049,041,044,038,030,044,2,020,1,05c,031,0
39,05c,040,024,0
*251,23,JING
032,2,02c,1,02d,054,028,024,040,02c,028,2,01e
,1,03e,2,086,1,050,025,02d,040,0
请自己分析, 北京, 两个汉字的矢量走向，并验证形定
义的正确性。
可以把若干个形定义放在一个形定义文件中。用这种
方法可以建立 AUTOCAD所使用的各种字体的字符库以及
汉字库。在 AUTOCAD实际使用这种形文件所定义的字符
时，必须通过编译、装入、调用形文件三个步骤。详细使
用方法请参阅 AUTOCAD相关参考书籍。
5.3.2 点阵字符
在点阵字符库中，每个字符都定义成一个称为字符掩
膜的矩阵。矩阵中的每个元素都是一位二进制数，该位为
1时，表示对应此位的像素置成字符颜色，该位为 0时，表
示字符的笔划不经过此位，对应此位的像素为背景色或不
改变。图 5.3.4是字符掩膜的示意图。
一般西文字符的掩膜矩阵尺寸应不小于 5X7，而汉字
字符的掩膜矩阵尺寸应不小于 16X16。在我国早期
广泛使用的微机汉字系统，如 CCDOS等都是采用 16X16
点阵汉字作为显示用字符，打印时可以采用 24X24，
40X40,48X48，甚至 72X72点阵字符。
一个 5X7西文字符点阵包括 35个像素点，需要 35位
二进制数（占四个多字节）来表示。一个 16X16点阵的
汉字，占 16/8X16=32个字节，而一个 72X72点阵汉字，
徐图 5.3.4 字符掩膜矩阵
要 72/8X72=648个字节。
点阵字符库的制作方法。用于打印的高分辨
率点阵字符的掩膜位图，可以通过用扫描仪输入
放大的手写美术字符或印刷字符，然后用交互作
图程序对位图的个别像素进行修改和完善。用于
显示的或用于低分辨率打印机的位图可以使用交
互式绘图程序，通过手工建立。在微机上通常使
用几种不同分辨率的字符库，以满足不同的需要，
例如在 CCDOS4.0中就使用了 24种不同的字符库。
5.3.3 字型技术
当应用对输出字符的要求较高时（如排版印
刷），需要使用高质量的点阵字符。然而，直接
使用上述的点阵字符将浪费大量的存储空间。
对于 GB2312-80所规定的 6763个基本汉字，
假设每个汉字是 72X72点阵，那么一个字库就需
要 4.4M字节存储空间。在实际使用时，通常需要
多种字体，如基本体、宋体、仿宋体、黑提、楷
体等，而每种字体又需要数十种以上的字号。因
此，把每种字体、字号的字符都存储一个点阵，
在一般情况下是不可行的。
解决这个问题一般采用压缩技术。对字型数
据压缩后再存储，使用时，将压缩的数据还原为
字符位图点阵。压缩的方法通常有三种，一是简
单的黑白段压缩法，这种方法简单，还原快，不
失真，但压缩比较差，使用起来也不方便。二是
部件压缩法，这种方法压缩比大，缺点是字型质
量不能保证。三是轮廓字型法，这种方法压缩比
大，且能保证字符质量，是当今国际上最流行的
一种字符压缩方法，基本上也被认为是符合工业
标准的方法。
轮廓字型法采用直线、二次或三次 Bezier曲
线的集合来描述一个字符的轮廓线。轮廓线构成
一个或若干个封闭的平面区域。轮廓线定义加上
一些指示横宽、竖宽、基点、基线等控制信息，
就构成了字符的压缩数据。
下面介绍当前国际上流行的 TrueType字型技
术。它是由美国 Apple和 Microsoft公司联合开发
的，并且已被广泛用于 Windows系统中，可以生
成包括汉字字库在内的多种字库。 TrueType使
用二次 Bezier曲线来描述字符轮廓，对字符轮廓
线的控制点进行编号，其顺序是按照顺时针方向
走一圈，填充的部分始终在其右边。下面以大写
字母 H为例，说明 TrueType字库控制信息。
如图 5.3.5（ a）所示,X方向控制信息有：（ 1）字
身最左起点到字母主干的距离间隔；（ 2）字母主体部分
的宽度；（ 3）字身的宽度；（ 4）字母 H主干的宽度；
（ 5）字母 H的衬线（ Serif）。如图 5.3.5（ b）所示,y
方向的控制信息有：（ 6）字母 H横干的厚度；（ 7）字母
H衬线的厚度；（ 8）字母主体部分的高度；（ 9）字母 H
横干的高度。
上述 9个参数用于产生控制信息表。这个控制信息表
和曲线轮廓定义信息将在不同分辨率情况下产生字符的点
阵中起到关键作用。
字型技术有着广泛的应用，但是在字型数据生成上要
花费大量的人力物力。早期的生产方式是由写字专家写出
字符，然后把字符托到 96X96方格纸上，人为地画出矢量
节点，最后由操作员录入计算机。现在使用的一般方法是
用扫描仪把字符数字化，用程序自动地进行矢量轮廓的生
成，再由操作员对矢量结果进行调整优化，做成合格的字
型。可见，字型的生产是一个周期长，人力和物力消耗大
的工作，好的字型数据来之不易。
5.3.4 字符输出
矢量字符从绘图仪上输出，需要把有关的方向和位移
值转换成设备驱动指令。点阵字符输出到显示器屏幕或打
印机，只要指定字符掩膜的原点与帧缓冲器中的字符左下
角位置（ x0,y0）对应，就可以将字符掩膜中的值平移地
写入到帧缓冲器。伪算法如下：
Writechar(x0,y0,value)
int x0,y0,value;
{
for (j=0;j<=ymax; j++)
for (i=0; i<=xmax; i++)
if (Mask(i,j)<>0)
writepixel(x0+i,y0+j,value);
else
writepixel(x0+i,y0+j,background);
}
在上述算法中,Mask是存放掩膜位图的矩阵，
（ xmin,ymin）和（ xmax,ymax）是掩膜矩阵的左
下角位置和右下角位置的坐标,Value是字符的颜色。
在上述算法中，可以进行简单的修改来获得不同的字体，
如黑体字、斜体字和旋转字体等。例如，只要把掩膜中
每个非零值写入相邻两个单元：（ x0+i,y0+j）和
（ x0+i+1,y0+j），就可以实现黑体字。为了实现斜体
字，只要在写像素时，把原掩膜坐标位移之后，再对 x坐
标加上与 y坐标成比例的位移。
5.3.5 程序设计与实践（四）
一、实验内容：线型与线宽处理技术，字符处理技术
二、实验任务：
1,线刷子绘制直线和圆；
2,方形刷子绘制直线和圆；
3,虚线和点划线的绘制；
4,在 AUTOCAD环境中定义矢量字体（形文件），并使用
矢量字体；
1,点阵字体的读取与显示；
2,熟悉字符输出技术，生成黑体字和斜体字；
三、实验步骤：
（略）
5,4 图形裁剪
在使用计算机处理图形信息时，往往计算机
内部存储的图形比较大，而屏幕显示只是图形
的一部分。例如，虽然计算机内部可以存储全
国地图，但是，如果把全国地图整幅显示在屏
幕上，则看不清各地局部的细节。这是需要使
用缩放技术，把地图中的局部区域放大显示，
这时必须确定图形中那些部分落在显示区内，
那些部分落在显示区外，以便显示落在显示区
内的那部分图形。
这种在给定显示区域的条件下，将图形分为
可见部分与不可见部分，而仅将可见部分送往图
形系统以供显示的过程，称为裁剪（ Clipping）。
当显示窗口内的图形、图形变换以及图形覆盖等
操作时，都需要用到裁剪技术。
在进行裁剪时，对应于屏幕上显示图形的那
部分区域称为窗口。窗口可以是整个屏幕，也可
以是屏幕上的一个矩形，由上、下、左、右四条
边围成，即（ xl,yb），（ xr,yt）。裁剪的实质，
就是决定图形中那些点、线段、文字以及多边形
在窗口之内。
对于点（ x,y），只要判断两对不等式：
xl≤x≤ xr,yb≤y≤yt
若四个不等式均成立，则点在窗口之内；否
则，点在窗口之外。最简单的裁剪方法是把各种
图形扫描转换为点之后，再判断各点是否在窗口
内。
但该方法太费时，一般不可取。这是因为有些图形组
成部分全部在窗口外，可以完全排除，不必进行扫描转换。
所以，一般采用先裁剪，后扫描转换的方法。
本节先讨论线段的裁剪算法，然后再讨论多边形和字
符的裁剪技术。
5.4.1 线段裁剪
线段裁剪是决定线段那些部分在窗口内，那些部分在
窗口外，在直线段扫描转换过程中只考虑窗口内的各点像
素的显示。常用的线段裁剪算法有 Cohen-SutherLand
裁剪算法（编码裁剪法）、中点分割算法、梁友栋 -Brian
裁剪法和参数化方法等。
（一） Cohen-SutherLand裁剪算法
Cohen-SutherLand裁剪算法的思想：对于每条线段
P1P2，分为三种情况处理。（ 1）若 P1P2完全在窗口之
内，则显示该线段 P1P2，简称, 取, 之。（ 2）若 P1P2
明显在窗口外，则丢弃该线段不用考虑，简称, 弃, 之。
（ 3）若线段及不满足, 取, 的条件，也不满足, 弃, 的
条件，则把线段分为两段，其中一段完全在窗口外，可弃
之。然后对另一段重复上输处理。
如图 5.4.1所示，线段 AB两个端点均在窗口内，故整
条线段均可取之显示。线段 CD两个端点均在窗口外，且
两个端点均在窗口下边界的下方，即整个线段处于窗口延
长线的一侧，可弃之。线段 EF,GH,IJ只有一部分落在
窗口内，按第三种情况来处理。线段 KL虽然完全在窗口外，
但没有简单的判断条件，即没有在窗口一侧，故也按第三
种情况来处理。
为了使计算机能够快速判断一条线段与窗口之间的关
系，采用如下的编码方法。延长窗口的边，把未经裁剪的
图形区域分成九个区，如图 5.4.2所示。每个区用 4位二进
制数来表示，从左到右依次表示上、下、右、左。编码规
则如下：
第一位：左边界，端点在左边界的左边（外面）为 1，否则
为 0；
第二位：右边界，端点在右边界的右边（外面）为 1，否则
为 0；
第三位：下边界，端点在下边界的下边（外面）为 1，否则
为 0；
第四位：上边界，端点在上边界的上边（外面）为 1，否则
为 0；
根据编码规则可得到图 5.4.2所示的各区编码。
Cohen-SutherLand裁剪算法是通过编码方法来实现的，
因此，该算法也称为编码裁剪法。
假设要裁剪一条直线段 P1P2，首先求出两个端点 P1、
P2所在区域的编码 code1和 code2。编码裁剪算法藐视如
下：
（ 1）如果线段两个端点的四位编码均为 0，即 code1=0且
code2=0，则说明线段全部在窗口内，应取之；
（ 2）如果线段两个端点出的编码按位, 与, 运算后结果不
为零，即 code1&code2≠0，则说明直线段的两个端点在
窗口的一侧，整个线段不在窗口内，应弃之；
（ 3）如果上述两种条件均不成立，则按第三种情况处理。
求出线段与窗口某边的交点，在交点出把线段一分为二，
其中必有一段完全在窗口外，可以弃之。再对另一段重复
进行上述处理。
例如，图中线段 P1P2两端点处的编码分别为 code1=0001，
code2=0100。由于 code1&code2=0，故属于第三种
情况。由 code1=0001得知 P1在窗口的左边，计算线段
与窗口左边界的交点 P3。 P1P3比在窗口之外，可弃之。
对线段 P3P2重复上述处理。由于 P3处的编码
code3=0000，说明 P3已经在窗口内。由 code2=0100
可知 P2在窗口的下方，计算线段 P3P2与窗口下边界的交
点 P4，丢弃 P4P2，剩下的线段 P3P4就是裁剪的结果，即
在窗口中显示的部分。
在编写程序时，一般是按固定顺序检测区号编码的各
位是否为 0。可按从低位到高位的顺序，即左 -右 -下 -上，
也可以按照从高位到低位的顺序，即上 -下 -右 -左。另外，
程序中舍弃窗口外的子线段，只要用交点的坐标值代替被
舍弃的端点坐标即可实现。
Cohen-SutherLand裁剪算法伪程序如下：
#define LEFT 1 // 0001,左
#define RIGHT 2 // 0010，右
#define BOTTOM 4 //0100,下
#define TOP 8 //1000,上
// 已知端点坐标（ x,y），求其所在区的编码 code。
encode(x,y,code)
float x,y;
int * code;
{
int c; c=0;
if (x<XL) c=c|LEFT;
else if (x>XR) c=c|RIGHT;
if (y<YB) c=c|BOTTOM;
else if (y>YT) c=c|TOP;
*code=c;
return;
}
//Cohen-SutherLand裁剪函数,(x1,y1),(x2,y2)是线段
两个端点坐标，
//XL,XR,YB,YT是窗口的边界定义
C_S_Line(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
{
int code1,code2,code;
encode(x1,y1,&code1);
encode(x2,y2,&code2); // 求出两个端点处的编码
while (code1<>0 || code2<>0) //,||”或者运算，只
要有一个不为 0；
{
if (code1&code2<>0) return; // 表示 code1和
code2在窗口一侧，弃之；
//第三种情况，按照左 -右 -下 -上的顺序求交点
code=code1;
if (code1==0) code=code2;
if (LEFT&code<>0) //线段与左边界的交点
{
x=XL;
y=y1+(y2-y1)*(XL-x1)/(x2-x1);
}
else if (RIGHT&code<>0) //线段与右边界的交点
{
x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-x1);
}
else if (BOTTOM&code<>0) //线段与下边界的交点
{
y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1);
}
else if (TOP&code<>0) //线段与上边界的交点
{
x=YT;
y=x1+(x2-x1)*(YT-y1)/(y2-y1);
}
if (code==code1)
{x1=x;y1=y;encode(x,y,code1);}
else
{x2=x;y2=y;encode(x,y,code2);}
} //end-while
DisplayLine(x1,y1,x2,y2);
Return; } //End C_S_Clip()
（二）中点分割裁剪算法
中点分割裁剪法又称为对分法，其算法思想与编码裁
剪法类似，先对线段端点进行编码，并把线段与窗口的关
系分为三种情况，前两种情况算法处理相同，只是在第三
种情况下，既当一条线段既不能直接接收，也不能直接舍
弃，欲求其与窗口的交点时，不是直接计算线段与窗口边
界的交点，而是将线段等分为两段，并对两端再分别加以
测试。用这种二分法搜索方式一直进行下去，直到找到落
在窗口内显示的部分线段为止。
中点分割裁剪算法描述如下：
（ 1）判断线段是否在窗口内，如果两个端点均在窗口内，
则整个线段都在窗口内；如果线段的两个端点不再窗口内，
且在窗口的同一侧，则该整个线段在窗口外，舍弃之；如
果线段与窗口边界重合，则求出该线段在边框上的起点和
终点坐标。否则，转（ 2）
（ 2）找出该线段离窗口边框最远点和线段的中点，判断中
点是否在窗口内：
（ 1）如果中点不在窗口内，则把中点和离窗口边框最远
点构成的部分线段丢弃掉，以线段上的另一点和线段中点
再构成线段求其中点，重复第 (2)步；
（ 2）如果中点在窗口内，则又以中点和最远点构成线
段，并求其中点，直到中点与窗口边框的坐标值在规定误
差范围内，则该中点就是该线段在窗口内的一个端点，即
可见端点。
（ 3）如果另一点在窗口内，则经过第（ 2）步后即可确
定线段的可见部分。如果另一点不在窗口内，则该点和第
（ 2）求出的可见端点构成新的线段，重复第（ 2）步的过
程，求出另一个可见端点。
（ 4）两个可见端点之间的线段就是裁剪算法的结果，即可
显示部分的线段。图 5.4.3 中点分割裁剪算法示意图
P1P2Pm1Pm2Pm3BA
例如，如图 5.4.3所示，线段 P1P2不满足条件（ 1），转（ 2）
执行；
离窗口边框最远点是 P2,P1P2的中点是 Pm1。因
Pm1在窗口内，则再以 Pm1和 P2构成线段 Pm1P2，再求
中点得到中点 Pm2。由于 Pm2在窗口外，则舍弃
Pm1P2线段，再求 Pm1 Pm2线段的中点，得到 Pm3。
由于 Pm3在窗口内，再求 Pm3 Pm2 的中点,……,直
到 | Pmi+1-Pmi |≤е,е为误差精度。则 Pmi+1为一个可
见端点 A。
然后，执行第（ 3）步，同理求出另一段的可见端点 B。
因此，可以得到裁剪结果，即可视线段部分 AB。 A点称为
P1端点的最远可见端点,B点称为 P2端点的最远可见端点。
由于求线段中点（ x1+x2） /2，（ y1+y2） /2可以
由加法和位移来实现，避免了使用乘除法，所以易于硬件
来实现，算法处理速度很快。另外，采用二分法求可见端
点，查找时间复杂度是 log2M。对于 1024X1024（ 210）
的光栅显示器，则 M=210,log2M=log21024=10,即
最多 10次迭代步骤就可以找到最远的可视点。
（三）梁友栋 -Brian裁剪算法
梁友栋是浙江大学 CAD国家重点实验室
教授，他提出的裁剪算法在国内外也得到
广泛的承认。梁友栋 -Brian裁剪算法的基
本思想是将二维裁剪归结为一维裁剪，把
多边形的裁剪变成解一元不等式组的问题。
设一维直线上有, 窗口, Q1Q2，坐标
q1≤q2，考察该直线上线段 AB，其坐标
a≤b，则窗口内可见部分 VW=AB∩ Q1Q2。
AB与 Q1Q2的关系如表 5.3.1所示。
由上表可归结为下述结论,AB在 Q1Q2上可视线段存
在的充要条件为：
max(min(a,b),min(q1,q2)) ≤
min(max(a,b),max(q1,q2)) （公式 5-1）
可视部分为：
max(min(a,b),min(q1,q2)) ≤x≤
min(max(a,b),max(q1,q2)) （公式 5-2）
例如，图 5.4.4为一窗口和线段 AB，若 AB不平行于窗口边，
则 AB所在直线及其延长线与窗口四边有交点 L,R,T，
U。窗口部分 Q1Q2=LR∩ TU，线段 AB在窗口的部分为：
VW=AB∩ Q1Q2=AB∩ LR∩ TU。（ xl,yb）（ xr,yt）
ABQ1Q2ULTR图 5.4.4 梁友栋 -Brian裁剪算法示例
设窗口左下端点为（ xl,yb），右上端点坐标为
（ xr,yt）,该算法分以下几种情况：
（ 1）若 AB平行于上下窗口边，即 Ay=By,且在窗口其间，
则可视部分 VW=AB∩ LR;
(3) 当 Ax≠Bx，且 Ay≠By,VW存在的充要条件为：
max(xl,min(Ax,Bx),min(Tx,Ux))≤min(xr,max(Ax,
Bx),max(Tx,Ux)) （公式 5-3）
可视线段 VW的 x区间为：
max(xl,min(Ax,Bx),min(Tx,Ux))≤x≤min(xr,max(
Ax,Bx),max(Tx,Ux))
同理，可视线段 VW的 y区间为：
max(yb,min(Ay,By),min(Ly,Ry))≤y≤min(yt,max(Ay
,By),max(Ly,Ry))
(4)当 Ax=Bx时,VW存在的充要条件为：
max(yb,min(Ay,By)) ≤min(yt,max(Ay,By))
当 Ay=By时,VW存在的充要条件为：
max(xl,min(Ax,Bx)) ≤min(xr,max(Ax,Bx))
可视部分：
V=( max(xl,min(Ax,Bx)),max(yb,min(Ay,By)))
W=( min(xr,max(Ax,Bx)),min(yt,max(Ay,By)))
根据以上描述，算法描述（略）。
5.4.2 凸多边形对直线的裁剪
一般的窗口为矩形，但是如果窗口为其它凸多边形时，
裁剪算法描述如下。
（一）基础知识
1．点与直线的相对位置 XYP1P2P3P4A图 5.4.5 点与直线
的关系
设平面上有一直线段 P1P2，和一个点 A。当观察者从
P1走向 P2时,A点始终在观察者的右侧，称 A点在 P1P2
的右侧。如图 5.4.5所示,A点在 P1P2的右侧,A点在
P3P4的左侧。
定理 1：平面上给定直线 P1P2和点 A,A在 P1P2右
侧的充要 条件是：
其中,Det为行列式，点与直线段的齐次坐标分别
是 A(x,y,1),P1(x1,y1,1),P2(x2,y2,1)。
定理证明：略。参见文献：徐宏炳著, 计算机图形
学, P72-74。
根据定理 1可知，已知线段 P1P2和点 A，计算行
列式
若 S=0，则 A在 P1P2直线上；若 S>0，则 A点在
P1P2的左侧；若 S<0,A点在 P1P2的右侧。
推论：已知凸多边形 P1P2P3… Pn-1Pn，
按照顺时针方向走向。判断 A点是否凸多边
形内点的充要条件是：
和
恒成立，则 A为凸多边形内的点。
2．线段与线段相对位置的判断
已知线段 P1P2和 P3P4,它们的相对位置有
三种情况，如图 5.4.6所示。
分析三种位置的计算结果：
第（ 1）情况,S1>0,S2>0,S3>0,S4<0，即 S1S2>0，
S3S4<0；
第（ 2）情况,S1<0,S2>0,S3<0,S4<0，即 S1S2<0，
S3S4>0；
第（ 3）情况,S1<0,S2<0,S3>0,S4>0，即 S1S2<0，
S3S4<0；
结论：当 S1S2<0,S3S4<0时,P1P2 和 P3P4 两线段有
交点 P,则 P满足方程组：
(二 ) 线段与凸多边形相对位置的判断与裁剪
设平面上有线段 L=P1P2,凸多边形 ∏= A1A2A3… An-1An,L与
∏的关系可以通过判断多边形顶点 Pi与 L线段的关系来判断。
可得到如下几种情况：
（ 1）所有的 Si不为 0，且符号相同，说明多边形顶
点在 L的同一侧,∏与 L不相交；
P1P2L∏AjAj+1AKAK+1L1L2 图 5.4.7 线段与
凸多边形相对位置 (1)(2)(3)(4)(5)(6)
（ 2） Si中有 2个为 0，其余同号，说明 ∏在 L的一侧，
且有一条边与 L共线；
（ 3） Si中有 1个为 0，其余同号，说明 L与 ∏的一个
顶点相交,∏在 L的一侧；
（ 4） Si中有 1个或二个为 0，其余有正有
负，这说明 L与 ∏相交，且 L通过 ∏的一个或
二个顶点；
（ 5） Si均不为 0，且有正有负，这说明 L
与 ∏相交，且没有通过 ∏的顶点。
为了说明凸多边形对直线的裁剪算法，
分析第（ 5）种情况，如图 5.4.7所示。因
为 Si,Sj+1<0,SK, Sk+1<0，说明 L必
然通过 L1,AiAj+1和 L2,AkAk+1。分析
P1P2 和 AiAj+1,AkAk+1线段之间的关
系：
设凸多边形 ∏= A1A2A3… An-1An按
顺时针定向,L与 ∏的位置关系如图所示的
6种情况。针对上述情况，分别计算 U1 U2
U3 U4的取值，以及对 L与 ∏的交点可归结
为下表。表中 Q1,Q2表示 L与 ∏的交点，
即 Q1Q2为可视线段。
5.4.3 多边形裁剪
多边形的裁剪就是用矩形窗口来裁剪任意多边
形。对于一个任意多边形，当然可以把它分解成
多条边线段，并逐段裁剪。但是，这样做会使原
来封闭的多边形变成不封闭的或者一些离散的线
段。如果只考虑画线图形，问题还不大。
但是当多边形作为实区域考虑时，封闭多边形裁剪后
仍然应该是封闭多边形，以便进行填充。为了实现多边形
裁剪的目的，可以采用逐边裁剪法和双边裁剪法等算法。
（一）逐边裁剪法
逐边裁剪法（ Reentrant Polygon Clipping）是
1974年由 Sutherland和 Hodgman提出的多边形裁剪算
法。该算法的基本思想是：每次用窗口的一条边界对要裁
剪的多边形进行裁剪，保留包含在窗口内部分，丢掉窗外
部分。四条窗口边界裁剪完成后，所得到的图形就是保留
在窗口内的可视部分。
多边形裁剪会出现完整封闭的多边形裁剪后不再封闭
的问题。解决这个问题的方法是：需要用窗口边界的适当
部分来封闭多边形。
算法的输入是以顶点序列表示的多边形，用 P1
P2 … Pn来表示。算法的输出也是一个顶点序列，构成一
个或多个多边形。如图 5.4.8所示。
算法分析：考虑窗口的一条边及其延长线构成的裁剪
线。该线把平面分成两部分：一部分包含窗口，称为可见
一侧；另一部分为不可见一侧。依次考虑多边形各边的两
个端点 S,P，它们与裁剪线的位置关系只有四种。如图
5.4.9所示。
每条线段端点 S,P与裁剪线比较之后，可输出 0至 2个
顶点。对于情况（ 1）两端点 S,P都在可见一侧，则输出
P。情况（ 2）,S,P都在不可见一侧，则输出 0个顶点。
第（ 3）种情况,S在可见一侧,P在不可见一侧，则输出
线段 SP与裁剪线的交点 I。第（ 4）种情况,S在不可见一
侧,P在可见一侧，则输出线段 SP与裁剪线的交点 I和线
段终点 P。
按照上述算法，分析图 5.4.8的输入和输出结果。
（二）双边裁剪法
1977年 Weiler-Atherton提出了用主多边形 P（用户
图形）的边裁剪多边形 C（窗口），或在某种条件下用 C
的边去裁剪 P的算法，这种算法称为双边裁剪法。它适合
任意多边形的裁剪。
算法的基本思想：对于一个顶点集合 {Vi,i=1~n}有
序排列 的封闭多边形，从其任意一顶点出发，按照顶点
排列的顺序（如按照顺时针方向排列），跟踪检测 P的每
一条边，当 P的边和 C的有效边界相交时，按照如下两种
情况来处理,
若 P的边是进入 C，则算法继续沿着 P的边往下处理；
若 P的边是从 C中出来，则算法将从它们的交点开始，
沿着窗口边界向右检测 C的边，即用 C的有效边框去裁剪 P
的边。若 C的有效边框从交点向右前进遇到与 P的交点，
则返回到交点处继续处理 P的边。
这个过程一直处理到起点为止。被裁剪出来的
落在 C内（包括落在 C的有效边框上）的多边形的
边可以一边处理一边输出，也可以把裁剪出来的
顶点坐标存放起来，等 P处理完毕后一并输出。
如图 5.4.10所示的多边形 P=ABCDEFGA,其
顶点按照顺时针方向排列，从 A点出发，按照双
边裁剪法，分析如下：从 A点出发，首先是从外
向里进入 C，交点 H；从 H开始沿着直线 AB继续，
在交点 I处是从里向外出来，则沿着窗口边界向下，
并检测与 P是否有交点，没有交点直到 O2。同理，
继续沿窗口到 O1，然后到交点 J。由于 DE是从外
向里进入 C,所以从 J开始沿直线 DE到 E,然后到交
点 K。从 K点从里向外出去，所以应沿窗口边界向
右前进，从 K点向右前进到交点 H,然后返还到 K点
继续处理 P。
FG线段从外向里进入 C,交点为 L,所以从 L开始沿 FG线
段继续，到达 M交点。由于是从里向外，所以应沿窗口边
沿向右前进，由 M到 O4，再由 O4到交点 L。得到图
5.4.11的结果。
5.4.4 字符裁剪
前面介绍的字符和文本的输出都是以当前窗口可以容
纳整个字符或文本为前提的。当字符或文本整个不在窗口
时，不予显示就是了。然而，当字符或文本部分在窗口内，
部分在窗口外时，就提出了字符裁剪的问题。
最简单的字符裁剪方法就是把字符方框（即字符掩膜）
与窗口比较，若整个方框位于窗口内，则显示对应的字符，
否则不予显示。这用裁剪以字符为单位进行裁剪，要么全
部显示，要么全都不显示。
有些应用要求更精确的处理：即使字符只有一部分在
窗口内，也要把这部分显示出来。若字符为点阵字型，只
要在把字符掩膜各位写入像素之前，先判断该位对应的像
素是否在窗口内。若该位在窗口内则写，否则就不写。
对于矢量字符，这时就要对跨越窗口边界的笔划进行
裁剪，裁去笔划伸到窗外的部分，保留笔划在窗内的部分，
这个问题就转化为线段的裁剪。
字符串的裁剪，可以按三种精度来进行：串精确度、
字符精确度以及笔划 /像素精确度。采用串精确度进行裁
剪时，当字符串方框整个在窗口内予以显示，否则不显示。
采用字符精确度时，当字符串的某个字符方框整个在窗口
内时显示该字符，否则不显示。当采用笔划 /像素精度时，
要具体判断字符串中各字符的哪些像素、笔划的哪一部分
在窗口内，处理方法同字符裁剪。
5,5 反走样技术
在光栅图形显示器上绘制非水平和非垂直的线段时，
或多或少会出现锯齿状。这是由于直线段在光栅图形显示
器上对应的图形都是有一系列相同亮度的离散像素构成的。
这种用离散量表示连续量引起的失真，就叫做走样
（ aliasing）。
而用于减少或消除这种效果的技术，就称为反走样
（ antialiasing）。常用的反走样方法可分为两类：其中
一类基于提高分辨率，即增加采样点；另一类是把像素作
为一个有限区域，对区域采样。
5.5.1 提高分辨率
图 5.5.1 直线扫描转换像素示意图
在直线段扫描转换算法中，总是选择离理想直线最近
的一个像素，并置为直线颜色。每当前一列所选的像素与
后一列所选的像素不同行时，就会出现一个锯齿。如图
5.5.1（ a）所示。现在假设把显示器分辩率提高一倍，直
线经过的像素增加一倍，锯齿的个数也增加了一倍。但是，
由于每个锯齿在 x方向与 y方向都只有低分辨率的一半，锯
齿幅度比较小，所以效果看起来会好一些。这种改进是以
4倍的存储器代价和扫描转换时间获得的。因此，增加分
辨率是不经济的方法，它只能减轻而不能消除锯齿。
提高显示器分辨率属于 物理上增加显示像素,而显示
器的分辨率是由图形系统硬件所决定的。显示器分辨率越
高，图形显示的效果就越好。另一种方法是 通过数学插值
的方法,在较高的分辨率中进行计算，然后采用某种平均
算法，把结果转化到较低分辨率的显示器上进行显示。
101112202122图 5.5.2 数学插值子像素示意图
421212121
如图 5.5.2所示，实线表示低分辨率的像素位置，设
想将每个正方形像素区域分成九个等尺寸的子像素，用虚
线表示，阴影区域表示由 Bresnham算法选择的子像素位
置。由于这些子像素位置是不存在的，我们可以将子像素
所在的实际像素的亮度等级设置为正比于这些子像素数目
的值，用不同的灰度显示来提高显示的质量。因为任何像
素中可供选择的子像素最大个数为 3，这种方法提供零以
上三种亮度设置。在例子中，位置（ 10,20）处的像素包
括了三个子像素，设置为最高亮度（级别 3）；位置
(11,21)和（ 12,21）两处的像素包括两个像素，设置为
次亮度（级别 2）；位置（ 11,20）和（ 12,22）两处都
包含了一个子像素，设置为最低亮度（级别 1）。
这样处理以后，线亮度分布在较大数目像素上，
并且通过在阶梯状台阶（水平长度间）附近显示
有些模糊的线路经使阶梯形状得到光顺。如果用
更多的亮度等级来利用反走样线，就需要增加每
个像素中的取样位置数，例如 16个子像素给出 4
个亮度级； 25个子像素给出 5个等级。
另外，可以采用 像素加权掩膜技术 来计算实际
像素的灰度。图 5.5.2中位置 (10,22)处给出了
3х3子像素的加权值方案。中心子像素取最大的
权值，因为这些子像素在确定像素的整体亮度中
起更重要的作用。根据子像素的个数和位置计算
每个实际像素的平均亮度。这样的结果是：中心
子像素的加权系数为 1/4，上、下、左、右四个
子像素的加权系数为 1/8，而四角的四个子像素
的加权系数为 1/16。指定子像素相对重要性值的
数组称为子像素的加权, 掩膜, （ mask）。
101112202122图 5.5.3 宽度线内部相关子
像素的位置
5.5.2 简单的区域取样
下面考虑显示线宽的情况。在前面的例子中，
我们都是把线当作具有零宽度的数学实体。实际
上，显示的线具有约与像素等宽的宽度。假如把
线的宽度考虑进去，可通过将每个像素的亮度设
置成正比于在表示线区域多边形内的像素数目来
完成。若子像素的左下角在多边形内，那么可把
此子像素当作在线内。这样做的好处是：每个像
素可能的亮度等级等于像素区域内子像素的总数。
如图 5.5.3所示，可以通过对平行于线路径的多边
形边界定位，以有限的宽度来表示这样的线。并
且每个像素现在可以设置成零以上九个亮度级别
之一。
在具有多级灰度的显示器上绘制一条直线段时，
若一个像素整个落在线区域的长方形内，则将它
设置为直线颜色。如果一个像素与线段相交，根
据相交部分的大小来选择不同的灰度。相交部分
多的像素颜色更深一些，相交部分少的像素颜色
相对浅一些。这种方法将产生模糊的边界，以此
来减轻锯齿效应。
5.5.3 过滤技术
反走样更精确的方法是采用过滤技术。这种
方法类似于应用加权像素掩膜，只是现在假想一
个连续的加权曲面（或称过滤函数）覆盖像素。
包括正方形、圆锥形和高斯过滤函数等，如图
5.5.4所示。应用过滤函数的方法类似于应用加权
掩膜，但现在是将像素曲面集成来得到加权的平
均亮度。为减少计算量，常采用查表法求整数值。
5,6 程序设计与实践（五）
一、实验内容：线段裁剪和多边形裁剪算法
二、实验任务：
编码裁剪算法的程序设计，要求用鼠标
画线技术；
三、实验步骤：
作业与练习
