第 3章 基本图形
生成算法
第 3章 基本图形生成算法
3.1 生成直线的常用算法
均假定所画直线的斜率 k∈ [0,1]。
3.1.1 DDA画线算法
DDA（ Digital Differential Analyzer）画线
算法也称数值微分法，是一种增量算法。它的算
法实质是用数值方法解微分方程，通过同时对 x和
y各增加一个小增量，计算下一步的 x,y值。
第 3章 基本图形生成算法
已知一条直线段 L（ P0,P1）,其端点坐标为：
P0 (x0,y0),P1(x1,y1)。可计算出直线的斜率 k
为：
假定端点坐标均为整数，取直线起点 P0 (x0,
y0)作为初始坐标。画线过程从 x的左端点 x0开始，
向 x右端点步进，每步 x递增 1,y递增 k（即直线
斜率）；取像素点（ x,round（ y））作为当前
点的坐标。
01
01
xx
yyk
?
??
第 3章 基本图形生成算法
3.1.2 中点画线算法
假设 x坐标为 xp的各像素点中，与直线最近者已
确定，为 P（ xp,yp），那么，下一个与直线最近的像
素只能是正右方的 P1(xp+1,yp)，或右上方的 P2
（ xp+1,yp+1）两者之一。令 M为 P1和 P2的中点，
易知 M的坐标为（ xp+1,yp+0.5）。
设 Q是理想直线与垂直线 x=xp+1
的交点。显然，若 M在 Q的下方，则 P2
离直线近，应取为下一个像素；否则应
取 P1。
第 3章 基本图形生成算法
令 a=y0-y1,b=x1-x0,c=x0y1-x1y0。
构造判别式：
d=a(xp+1)+b(yp+0.5)+c
d的初始值 d0 = a+0.5b
在 d≥0的情况下，取正右方像素 P1，
d1=a(xp+2)+b(yp+0.5)+c =d+a
在 d<0的情况下，取右上方像素 P2，
d2=a(xp+2)+b(yp+1.5) = d+a+b
第 3章 基本图形生成算法
由于我们使用的只是 d的符号，而且 d的增量
都是整数，只是其初始值包含小数。因此，我们
可以用 2d代替 d，来摆脱小数。
如果进一步把算法中 2*a改为 a+a等等，那
么这个算法不仅只包含整数变量，而且不包含乘
除法，适合硬件实现。
第 3章 基本图形生成算法
3.1.3 Bresenham画线算法
过各行各列像素中心构造一组虚拟网格线，按直
线从起点到终点的顺序计算直线与各垂直网格线的交
点，然后确定该列像素中与此交点最近的像素。
由图 3-5不难看出：若 s<t，
则 Si比较靠近理想直线，应
选 Si;若 s≥t，则 Ti比较靠近
理想直线，应选 Ti。
第 3章 基本图形生成算法
令 dx=x2-x1,dy=y2-y1
递推公式,
di的初值：
当 di≥0时，选 Ti，
当 di<0时，选 Si，
由于只包含加、减法和左移（乘 2）的运算，
而且下一个像素点的选择只需检查 di的符号，因此
Bresenham画线算法很简单，速度也相当快。
)(22 11 ?? ???? iiii yydxdydd
dxdyd ?? 21
)(21 dxdydd ii ????
dydd ii 21 ???
第 3章 基本图形生成算法
3.1.4 直线属性
1,线型
2,线宽
3,线色
第 3章 基本图形生成算法
3.2 生成圆弧的常用算法
3.2.1 圆的特性
圆心位于原点的圆有四条对称轴,x=0,y=0，
x=y和 x=-y直线。若已知圆弧上一点（ x,y），可
以得到其关于四条对称轴的其它 7个点，这种性质
称为八对称性，如下图所示。
本节讨论的圆的生成算法
均只计算从 x=0到 x=y分段内
（ 1b区域）的像素点，其余的
像素位置利用八对称性即可得
出。
第 3章 基本图形生成算法
3.2.2 中点画圆算法
假设 x坐标为 xp的各像素点中，与该圆弧最近者
已确定，为 P（ xp,yp），那么，下一个与圆弧最近的
像素只能是正右方的 P1(xp+1,yp)，或右下方的 P2
（ xp+1,yp-1）两者之一。
令 M为 P1和 P2的中点，易知
M的坐标为（ xp+1,yp-0.5）。
显然，若 M在圆内，则 P1离圆弧
近，应取为下一个像素；否则应
取 P2。
第 3章 基本图形生成算法
判别式 d：
d的初始值为：
在 d≥0的情况下，取右下方像素 P2，
在 d<0的情况下，取正右方像素 P1，
RRRRFd ???????? 25.1)5.0(1)5.0,1( 220
第 3章 基本图形生成算法
3.2.3 Bresenham画圆算法
假设生成圆心在坐标原点，半径为 r，从 x=0到
x=y的 1/8圆弧。
xi+1=xi +1
相应的 y则在两种可能中选择：
y=yi，或者 y=yi-1
选择的原则是考察理想的 y值
是靠近 yi还是靠近 yi-1。
第 3章 基本图形生成算法
判别式：
d i+1=2(xi+1)2+yi2+(yi-1)2-2r2
判断式 d的初始值为：
d0= 3-2r。
如果 d i+1>=0，则 y=yi-1，
di+2 =d i+1 + 4(xi- yi)+10
如果 d i+1<0，则 y=yi，
d i+2 =d i+1+ 4x i+6
第 3章 基本图形生成算法
3.3 区域填充
3.3.1 区域的表示和类型
顶点表示：也称为几何表示，是用区域的顶
点序列来表示区域。
点阵表示：也称为像素表示，是用位于多边
形内的像素集合来刻画多边形。
内点表示：区域内的所有像素着同一颜色，
而区域外的所有像素具有另一种颜色；
边界表示：区域边界上的所有像素点具有特
定的颜色（可以是填充色），在区域内的所有像
素均不能具有这一特定色，而且边界外的像素不
能具有与边界相同的颜色。
第 3章 基本图形生成算法
区域填充算法要求区域是连通的，因为只有
在连通区域中，才可能将种子点的颜色扩展到区
域内的其它点。
区域按连通情况又可分为四连通区域和八连
通区域。
四连通区域指的是从区域上一点出发，可通
过四个方向，即上、下、左、右移动的组合，在
不越出区域的前提下，到达区域内的任意像素。
八连通区域指的是从区域内每一像素出发，
可通过八个方向，即上、下、左、右、左上、右
上、左下、右下移动的组合，在不越出区域的前
提下，到达区域内的任意像素。
第 3章 基本图形生成算法
3.3.2 扫描线多边形填充算法
扫描线多边形填充算法是按扫描线顺序，计
算扫描线与多边形的相交区间，再用要求的颜色
显示这些区间的像素，即完成填充工作。
对于一条扫描线，多边形的填充过程可以分
为四个步骤：
?求交
?排序
?配对
?填色
第 3章 基本图形生成算法
边表（ ET）：边表一般是由一系列的存储桶
构成的，桶的数目与扫描线数一样多，按扫描线
递增（减）顺序存放。
边表的建立：先按下端点的 y坐标值对所有的
边进行分组，若某边的下低端点 y值为 ymin，则该
边就放在 ymin所对应的桶中；然后用排序方法，
按下端点的 x坐标值递增的顺序将同一组中的边排
列成行。
活化链表（ AEL）：我们把与当前扫描线相交
的边称为活性边，并把它们按与扫描线交点 x坐标
递增的顺序存放在一个链表中，称此链表为活化
链表（ AEL）。
第 3章 基本图形生成算法
ET和 AEL中的基本元素为多边形的边。边表示
成结点的形式，每个边结点由以下四个域组成：
其中，各符号的含义为：
? ymax,边的上端点的 y坐标
? x：在 ET中表示边的下端点的 x坐标，在 AEL中表示边
与扫描线的交点的 x坐标
? 1/k：边的斜率的倒数
? next：指向下一条边的指针
第 3章 基本图形生成算法
当建立了边表 ET后，扫描线多边形填充算法可按如下
步骤进行：
（ 1）初始化 AEL，使之为空，取扫描线纵坐标 y的初
始值为 ET中非空元素的最小序号。
（ 2）按从下到上的顺序对每条扫描线重复以下各步，
直至 AEL和 ET为空 。
① 将 ET中与当前 y有关的结点加入至 AEL，同时保存
AEL中按 x值从小到大实现的排序序列
② 对于 AEL中的扫描线 y，在一对交点之间填充所需要
的像素值
③ 从 AEL中删掉 y>=ymax的结点
④ 对于留在 AEL中的每个结点，执行 xi+1=xi + 1/k
⑤ 对 AEL中的各结点按 x值从小到大排序
⑥ y =y+1，成为下一条扫描线的坐标
第 3章 基本图形生成算法
3.3.3 边填充算法
基本原理：对每一条扫描线，依次求与多边形
各边的交点，将该扫描线上交点右边的所有像素
求补。
算法虽然简单易行，但对于复杂图形而言，一
些像素的颜色值需反复改变多次，且多边形外的
像素处理过多，输入、输出的量比有序边表大的
多。
第 3章 基本图形生成算法
栅栏填充算法：
对于每条扫描线与多边形的交点，将交点与栅
栏之间的扫描线上的像素取补，也就是说，若交
点位于栅栏左边，则将交点之右、栅栏之左的所
有像素取补；若交点位于栅栏右边，则将栅栏之
右、交点之左的所有像素取补。
多边形外的像素处理大大减少，被重复取补的
像素数目也有减少，但仍有一些像素被重复取补。
第 3章 基本图形生成算法
边标志算法：
对多边形边界所在像素置一个特殊标志；对于
每条与多边形相交的扫描线，从左至右逐个访问
该扫描线上的像素。使用一个布尔变量 inside来
指示当前点的状态，若点在多边形内，则 inside
为真。若点在多边形外，则 inside为假。 inside
的初始值为假，每当当前访问像素为被打上标志
的点，就把 inside取反。对未打标志的点，
inside不变。若访问当前像素时，对 inside作必
要操作之后,inside为真，则把该像素置为多边
形要填充的颜色。
对每个像素只访问一次，硬件执行速度快。
第 3章 基本图形生成算法
3.3.4 种子填充算法
基本思想：假设在多边形区域内部至少有一个
像素是已知的（此像素称为种子像素），由此出
发找到区域内所有其他像素，并对其进行填充。
由于区域可采用边界定义和内点定义两种方式，
区域按连通性又可分为四连通区域和八连通区域
两类，所以常用的种子填充算法有：
?边界表示的四连通区域种子填充算法
?内点表示的四连通区域种子填充算法
?边界表示的八连通区域种子填充算法
?内点表示的八连通区域种子填充算法
第 3章 基本图形生成算法
1．边界表示的四连通区域种子填充算法
基本思想：从多边形内部任一点（像素）出发，依, 左
上右下, 顺序判断相邻像素，若其不是边界像素且没有被填
充过，对其填充，并重复上述过程，直到所有像素填充完毕。
可以使用栈结构来实现该算法，算法的执行步骤如下：
种子像素入栈，当栈非空时，重复执行如下三步操作：
（ 1）栈顶像素出栈；
（ 2）将出栈像素置成多边形填充的颜色；
（ 3）按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素不在边界上且未置成多边形色，
则把该像素入栈。
第 3章 基本图形生成算法
2．内点表示的四连通区域种子填充算法
基本思想：从多边形内部任一点（像素）出发，依, 左
上右下, 顺序判断相邻像素，如果是区域内的像素，则对其
填充，并重复上述过程，直到所有像素填充完毕。它也常称
为漫水法。
可以使用栈结构来实现该算法，算法的执行步骤如下：
种子像素入栈，当栈非空时，重复执行如下三步操作：
（ 1）栈顶像素出栈；
（ 2）将出栈像素置成多边形填充的颜色；
（ 3）按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素是区域内的像素，则把该像素入
栈。
第 3章 基本图形生成算法
3,扫描线种子填充算法
算法思想：在任意不间断区间中只取一个种子像素
（不间断区间指在一条扫描线上一组相邻元素），填充当
前扫描线上的该段区间；然后确定与这一区段相邻的上下
两条扫描线上位于区域内的区段，并依次把它们保存起来，
反复进行这个过程，直到所保存的每个区段都填充完毕。
可以填充有孔区域，对于每一个待填充区段，只需入
栈一次，因此提高了区域填充的效率。
第 3章 基本图形生成算法
3.3.5 圆域的填充
对每条扫描线，计算它与圆域的相交区间。接
着，为每一条扫描线建立一个新圆表，存放在该
行第一次出现的圆的有关信息。然后，为当前扫
描线设置一个活化圆表。由于一条线与一个圆只
能相交一个区间，所以在活性圆表中，每个圆只
需一个结点即可。结点内存放当前扫描线的区间
端点，以及用于计算下一条扫描线与圆相交的区
间端点所需的增量。该增量用于在当前扫描线处
理完毕之后，对端点坐标进行更新计算，以便得
到下一条扫描线的区间端点。
第 3章 基本图形生成算法
3.3.6 区域填充属性
1．填充样式
2．填充颜色
3．填充图案
第 3章 基本图形生成算法
3.4 字符
3.4.1 字符存储与显示
1．点阵字符
每个字符都是利用掩膜来定义，并将其写入帧缓存保
存和显示。
点阵字符的显示：首先从字库中将它的位图检索出来，
然后将检索到的位图写到帧缓冲器中。读取帧缓存中这些
像素值，就可以在屏幕上显示此字符。如果将保存在帧缓
存中某字符掩膜相应像素值均置成背景色或背景光强，就
可以擦除帧缓存中的该字符。
第 3章 基本图形生成算法
2．矢量字符
矢量字符被表达为一个点坐标的序列，相邻两点表示
一条矢量，字符的形状便由矢量序列刻划。
矢量字符的显示：首先从字库中读它的字符信息。然
后取出端点坐标，对其进行适当的几何变换，再根据各端
点的标志显示出字符。
第 3章 基本图形生成算法
3.4.2 字符属性
显示的字符的外观由字体、字形、字号、字间
距、行间距等属性控制。一般来说，字体确定风
格，字形确定外观，字号确定尺寸。
1,单个字符属性
2,文本属性
第 3章 基本图形生成算法
3.5 裁剪
3.5.1 点的裁剪
对于一点 P（ x,y），要判断其是否可见，可
利用下面的不等式组来判断此点是否落在窗口范
围内：
满足上述不等式组的点则在窗口范围内，可见，
予以保留；反之，该点落在窗口外，不可见，舍
弃（裁剪）。
? xrxxl ytyyb ?? ??
第 3章 基本图形生成算法
3.5.2 直线裁剪
1,Cohen-Sutherland裁剪算法（编码裁剪法）
基本思想：对于每条待裁剪的线段 P1P2分为三种情况
处理：（ 1）若 P1P2完全在窗口内，则显示该线段 P1P2，
简称, 取, 之；（ 2）若 P1P2完全在窗口外，则丢弃该线
段，简称, 舍, 之；（ 3）若线段既不满足, 取, 的条件，
也不满足, 舍, 的条件，则求线段与窗口边界的交点，在
交点处把线段分为两段，其中一段完全在窗口外，可舍弃
之，然后对另一段重复上述处理。
第 3章 基本图形生成算法
Cohen-Sutherland直线剪裁算法以区域编码为基础，
将窗口及其周围的八个方向以 4 bit的二进制数进行编码，
如图 3-42所示。具体编码过程为：
延长窗口的四条边线（ yt,yb,xr,xl），将二维平
面分成九个区域。任何一条线段的端点都按其所处区域赋
予 4位编码 CtCbCrCl。
??
? ??
??
? ??
??
? ??
??
? ??
o t h e r
xlxc
o t h e r
xrxc
o t h e r
ybyc
o t h e r
ytyc
lrbt 0
1
0
1
0
1
0
1
第 3章 基本图形生成算法
?如果某线段的两个端点的四位
二进制编码全为, 0000”，可直
接保留；
?如果对两端点的四位二进制编码进行逻辑与（按位乘）
运算，结果不为零，可直接舍弃；
?否则，这一线段可能与窗口相交。此时，需要对线段
进行再分割，即找到与窗口边线的一个交点，根据交
点位置，也赋予四位二进制编码，并对分割后的线段
重复进行检查，直到全部线段均被舍弃或被保留为止。
裁剪窗口
第 3章 基本图形生成算法
2．中点分割算法
基本思想：当一条直线段既不能直接保留也不能直接
舍弃，需要求其与区域的交点时，不断地用对分方法，舍
去线段的不可见部分，用中点去逼近线段与窗口边界的交
点。
第 3章 基本图形生成算法
3．梁友栋 -barsky裁剪算法
定义直线的参数化方程为：
首先按参数化形式写出裁剪条件：
这四个不等式可以表示为形式：
??
?
?????
???
101
1
uyuyy
xuxx
4,3,2,1?? kqup kk
第 3章 基本图形生成算法
其中，参数 pk,qk定义为：
任何平行于裁剪边界之一的直线 pk=0，其中 k对应于裁
剪边界（ k=1,2,3,4对应于左、右、下、上边界），如果还满
足 qk<0，则线段完全在边界外，舍弃该线段。如果 qk≥0，则
该线段平行于裁剪边界并且在窗口内。
?当 pk<0，线段从裁剪边界延长线的外部延伸到内部。
?当 pk>0时，线段从裁剪边界延长线的内部延伸到外部。
?当 pk≠0时，可以计算出线段与边界 k的延长线的交点的
u值,u=qk/pk。
第 3章 基本图形生成算法
梁友栋 -Barsky裁剪算法在寻找线段可见部分（如果
有可见线段）时可以归结为四个步骤：
（ 1）如果对所有的 k都有 pk=0和 qk<0，删除线段并
结束。否则继续执行下一步。
（ 2）对所有 pk<0的 k，计算 rk=qk/pk,将 0和各个
rk值之中的最大值赋给 u1。
（ 3）对所有 pk>0的 k，计算 rk=qk/pk,将 1和各个
rk值之中的最小值赋给 u2。
（ 4）如果 u1>u2，则线段完全落在裁剪窗口之外，
不可见，可直接舍弃。否则，裁剪后线段的端点由参数 u
的两个值 u1,u2计算出来。
第 3章 基本图形生成算法
3.5.3 多边形裁剪
1,Sutherland-Hodgman算法
基本思想：每次用窗口的一条边界对多边形进行裁剪，
把落在窗口外部的图形去掉，落在窗口内部的图形保留，
并把它作为下一次待裁剪的多边形。这样，当连续用窗口
的四条边界对原始多边形进行裁剪后，最后得到的就是裁
剪后的结果多边形。
第 3章 基本图形生成算法
2,Weiler-Atherton裁剪算法
基本思想：将待裁剪多边形（简写为 P1）和裁剪矩形
窗口（简写为 P2）均设定为按顺时针方向排列。算法从 P1
的任一顶点出发，沿着它的边向下处理，当 P1和 P2相交时
（假定交点为 I）：
（ 1）若 P1的边是进入 P2，则继续沿 P1的边往下处理，
同时输出该线段；
（ 2）若 P1的边是从 P2中出来，则从此交点 I开始，沿
着窗口边框向右检测 P2的边，即用 P2的有效边框去裁剪 P1
的边，找到 P1和 P2最靠近交点 I的新交点，同时输出由 I到
S之间窗边上的线段；
（ 3）返回交点 I，再沿着 P1处理各条边，直到处理完
P1的每一条边，回到起点为止。
第 3章 基本图形生成算法
3.5.4 曲线裁剪
对于被裁剪的曲线所围成的区域，找出包围
（外接）此区域的最小矩形，称其为曲线边界对
象的包围矩形（或包围盒），然后测试包围矩形
是否与矩形裁剪窗口有重叠。
如果包围矩形完全落在裁剪窗口内，则全部保
留该对象；
如果包围矩形完全落在裁剪窗口外，则全部舍
弃该对象；
如果不满足上述矩形测试的条件，则要求解直
线 -曲线联立方程组，得出裁剪窗口与曲线边界线
的交点，即裁剪交点，再进行判断。
第 3章 基本图形生成算法
3.5.5 字符裁剪
1．字符串裁剪
把整个字符串作为整体来对待。
2．字符裁剪
分别对每个字符来处理。
3．矢量 \像素裁剪
每个字符都看作是由一系列矢量（线段）或像素构成
的，故对每一个矢量或像素都必须个别地进行裁剪。
第 3章 基本图形生成算法
3.5.6 三维图形的裁剪
把二维线段的 Cohen-Sutherland裁剪算法稍加改进，
就能推广到三维平行投影的裁剪算法中。
对空间任意一点 P（ x,y,z）按其所处位置赋予 6位二
进制编码。
（ 1）两个端点的编码全为, 0000”，直接保留；
（ 2）对两端点的编码进行逻辑与运算，结果不为零，
可直接舍弃；
（ 3）否则，计算出线段与窗口表面的交点，并将线
段分段后继续处理，直到余下的线段符合前两种简单情况
为止。
第 3章 基本图形生成算法
3.6 反走样
对图形进行光栅化时，是用离散的像素显示在
连续空间定义的对象。这种用离散量表示连续量
时引起的失真现象称为走样。
用于减少或消除走样的技术称为反走样。
第 3章 基本图形生成算法
3.6.1 光栅图形的走样现象
1．阶梯形走样
2．狭小图形遗失
3．细节失真
第 3章 基本图形生成算法
3.6.2 常用反走样技术
1．提高分辨率
2,简单的区域取样
3,加权区域取样
生成算法
第 3章 基本图形生成算法
3.1 生成直线的常用算法
均假定所画直线的斜率 k∈ [0,1]。
3.1.1 DDA画线算法
DDA（ Digital Differential Analyzer）画线
算法也称数值微分法，是一种增量算法。它的算
法实质是用数值方法解微分方程，通过同时对 x和
y各增加一个小增量，计算下一步的 x,y值。
第 3章 基本图形生成算法
已知一条直线段 L（ P0,P1）,其端点坐标为：
P0 (x0,y0),P1(x1,y1)。可计算出直线的斜率 k
为：
假定端点坐标均为整数，取直线起点 P0 (x0,
y0)作为初始坐标。画线过程从 x的左端点 x0开始，
向 x右端点步进，每步 x递增 1,y递增 k（即直线
斜率）；取像素点（ x,round（ y））作为当前
点的坐标。
01
01
xx
yyk
?
??
第 3章 基本图形生成算法
3.1.2 中点画线算法
假设 x坐标为 xp的各像素点中，与直线最近者已
确定，为 P（ xp,yp），那么，下一个与直线最近的像
素只能是正右方的 P1(xp+1,yp)，或右上方的 P2
（ xp+1,yp+1）两者之一。令 M为 P1和 P2的中点，
易知 M的坐标为（ xp+1,yp+0.5）。
设 Q是理想直线与垂直线 x=xp+1
的交点。显然，若 M在 Q的下方，则 P2
离直线近，应取为下一个像素；否则应
取 P1。
第 3章 基本图形生成算法
令 a=y0-y1,b=x1-x0,c=x0y1-x1y0。
构造判别式：
d=a(xp+1)+b(yp+0.5)+c
d的初始值 d0 = a+0.5b
在 d≥0的情况下，取正右方像素 P1，
d1=a(xp+2)+b(yp+0.5)+c =d+a
在 d<0的情况下，取右上方像素 P2，
d2=a(xp+2)+b(yp+1.5) = d+a+b
第 3章 基本图形生成算法
由于我们使用的只是 d的符号，而且 d的增量
都是整数，只是其初始值包含小数。因此，我们
可以用 2d代替 d，来摆脱小数。
如果进一步把算法中 2*a改为 a+a等等，那
么这个算法不仅只包含整数变量，而且不包含乘
除法，适合硬件实现。
第 3章 基本图形生成算法
3.1.3 Bresenham画线算法
过各行各列像素中心构造一组虚拟网格线，按直
线从起点到终点的顺序计算直线与各垂直网格线的交
点，然后确定该列像素中与此交点最近的像素。
由图 3-5不难看出：若 s<t，
则 Si比较靠近理想直线，应
选 Si;若 s≥t，则 Ti比较靠近
理想直线，应选 Ti。
第 3章 基本图形生成算法
令 dx=x2-x1,dy=y2-y1
递推公式,
di的初值：
当 di≥0时，选 Ti，
当 di<0时，选 Si，
由于只包含加、减法和左移（乘 2）的运算，
而且下一个像素点的选择只需检查 di的符号，因此
Bresenham画线算法很简单，速度也相当快。
)(22 11 ?? ???? iiii yydxdydd
dxdyd ?? 21
)(21 dxdydd ii ????
dydd ii 21 ???
第 3章 基本图形生成算法
3.1.4 直线属性
1,线型
2,线宽
3,线色
第 3章 基本图形生成算法
3.2 生成圆弧的常用算法
3.2.1 圆的特性
圆心位于原点的圆有四条对称轴,x=0,y=0，
x=y和 x=-y直线。若已知圆弧上一点（ x,y），可
以得到其关于四条对称轴的其它 7个点，这种性质
称为八对称性，如下图所示。
本节讨论的圆的生成算法
均只计算从 x=0到 x=y分段内
（ 1b区域）的像素点，其余的
像素位置利用八对称性即可得
出。
第 3章 基本图形生成算法
3.2.2 中点画圆算法
假设 x坐标为 xp的各像素点中，与该圆弧最近者
已确定，为 P（ xp,yp），那么，下一个与圆弧最近的
像素只能是正右方的 P1(xp+1,yp)，或右下方的 P2
（ xp+1,yp-1）两者之一。
令 M为 P1和 P2的中点，易知
M的坐标为（ xp+1,yp-0.5）。
显然，若 M在圆内，则 P1离圆弧
近，应取为下一个像素；否则应
取 P2。
第 3章 基本图形生成算法
判别式 d：
d的初始值为：
在 d≥0的情况下，取右下方像素 P2，
在 d<0的情况下，取正右方像素 P1，
RRRRFd ???????? 25.1)5.0(1)5.0,1( 220
第 3章 基本图形生成算法
3.2.3 Bresenham画圆算法
假设生成圆心在坐标原点，半径为 r，从 x=0到
x=y的 1/8圆弧。
xi+1=xi +1
相应的 y则在两种可能中选择：
y=yi，或者 y=yi-1
选择的原则是考察理想的 y值
是靠近 yi还是靠近 yi-1。
第 3章 基本图形生成算法
判别式：
d i+1=2(xi+1)2+yi2+(yi-1)2-2r2
判断式 d的初始值为：
d0= 3-2r。
如果 d i+1>=0，则 y=yi-1，
di+2 =d i+1 + 4(xi- yi)+10
如果 d i+1<0，则 y=yi，
d i+2 =d i+1+ 4x i+6
第 3章 基本图形生成算法
3.3 区域填充
3.3.1 区域的表示和类型
顶点表示：也称为几何表示，是用区域的顶
点序列来表示区域。
点阵表示：也称为像素表示，是用位于多边
形内的像素集合来刻画多边形。
内点表示：区域内的所有像素着同一颜色，
而区域外的所有像素具有另一种颜色；
边界表示：区域边界上的所有像素点具有特
定的颜色（可以是填充色），在区域内的所有像
素均不能具有这一特定色，而且边界外的像素不
能具有与边界相同的颜色。
第 3章 基本图形生成算法
区域填充算法要求区域是连通的，因为只有
在连通区域中，才可能将种子点的颜色扩展到区
域内的其它点。
区域按连通情况又可分为四连通区域和八连
通区域。
四连通区域指的是从区域上一点出发，可通
过四个方向，即上、下、左、右移动的组合，在
不越出区域的前提下，到达区域内的任意像素。
八连通区域指的是从区域内每一像素出发，
可通过八个方向，即上、下、左、右、左上、右
上、左下、右下移动的组合，在不越出区域的前
提下，到达区域内的任意像素。
第 3章 基本图形生成算法
3.3.2 扫描线多边形填充算法
扫描线多边形填充算法是按扫描线顺序，计
算扫描线与多边形的相交区间，再用要求的颜色
显示这些区间的像素，即完成填充工作。
对于一条扫描线，多边形的填充过程可以分
为四个步骤：
?求交
?排序
?配对
?填色
第 3章 基本图形生成算法
边表（ ET）：边表一般是由一系列的存储桶
构成的，桶的数目与扫描线数一样多，按扫描线
递增（减）顺序存放。
边表的建立：先按下端点的 y坐标值对所有的
边进行分组，若某边的下低端点 y值为 ymin，则该
边就放在 ymin所对应的桶中；然后用排序方法，
按下端点的 x坐标值递增的顺序将同一组中的边排
列成行。
活化链表（ AEL）：我们把与当前扫描线相交
的边称为活性边，并把它们按与扫描线交点 x坐标
递增的顺序存放在一个链表中，称此链表为活化
链表（ AEL）。
第 3章 基本图形生成算法
ET和 AEL中的基本元素为多边形的边。边表示
成结点的形式，每个边结点由以下四个域组成：
其中，各符号的含义为：
? ymax,边的上端点的 y坐标
? x：在 ET中表示边的下端点的 x坐标，在 AEL中表示边
与扫描线的交点的 x坐标
? 1/k：边的斜率的倒数
? next：指向下一条边的指针
第 3章 基本图形生成算法
当建立了边表 ET后，扫描线多边形填充算法可按如下
步骤进行：
（ 1）初始化 AEL，使之为空，取扫描线纵坐标 y的初
始值为 ET中非空元素的最小序号。
（ 2）按从下到上的顺序对每条扫描线重复以下各步，
直至 AEL和 ET为空 。
① 将 ET中与当前 y有关的结点加入至 AEL，同时保存
AEL中按 x值从小到大实现的排序序列
② 对于 AEL中的扫描线 y，在一对交点之间填充所需要
的像素值
③ 从 AEL中删掉 y>=ymax的结点
④ 对于留在 AEL中的每个结点，执行 xi+1=xi + 1/k
⑤ 对 AEL中的各结点按 x值从小到大排序
⑥ y =y+1，成为下一条扫描线的坐标
第 3章 基本图形生成算法
3.3.3 边填充算法
基本原理：对每一条扫描线，依次求与多边形
各边的交点，将该扫描线上交点右边的所有像素
求补。
算法虽然简单易行，但对于复杂图形而言，一
些像素的颜色值需反复改变多次，且多边形外的
像素处理过多，输入、输出的量比有序边表大的
多。
第 3章 基本图形生成算法
栅栏填充算法：
对于每条扫描线与多边形的交点，将交点与栅
栏之间的扫描线上的像素取补，也就是说，若交
点位于栅栏左边，则将交点之右、栅栏之左的所
有像素取补；若交点位于栅栏右边，则将栅栏之
右、交点之左的所有像素取补。
多边形外的像素处理大大减少，被重复取补的
像素数目也有减少，但仍有一些像素被重复取补。
第 3章 基本图形生成算法
边标志算法：
对多边形边界所在像素置一个特殊标志；对于
每条与多边形相交的扫描线，从左至右逐个访问
该扫描线上的像素。使用一个布尔变量 inside来
指示当前点的状态，若点在多边形内，则 inside
为真。若点在多边形外，则 inside为假。 inside
的初始值为假，每当当前访问像素为被打上标志
的点，就把 inside取反。对未打标志的点，
inside不变。若访问当前像素时，对 inside作必
要操作之后,inside为真，则把该像素置为多边
形要填充的颜色。
对每个像素只访问一次，硬件执行速度快。
第 3章 基本图形生成算法
3.3.4 种子填充算法
基本思想：假设在多边形区域内部至少有一个
像素是已知的（此像素称为种子像素），由此出
发找到区域内所有其他像素，并对其进行填充。
由于区域可采用边界定义和内点定义两种方式，
区域按连通性又可分为四连通区域和八连通区域
两类，所以常用的种子填充算法有：
?边界表示的四连通区域种子填充算法
?内点表示的四连通区域种子填充算法
?边界表示的八连通区域种子填充算法
?内点表示的八连通区域种子填充算法
第 3章 基本图形生成算法
1．边界表示的四连通区域种子填充算法
基本思想：从多边形内部任一点（像素）出发，依, 左
上右下, 顺序判断相邻像素，若其不是边界像素且没有被填
充过，对其填充，并重复上述过程，直到所有像素填充完毕。
可以使用栈结构来实现该算法，算法的执行步骤如下：
种子像素入栈，当栈非空时，重复执行如下三步操作：
（ 1）栈顶像素出栈；
（ 2）将出栈像素置成多边形填充的颜色；
（ 3）按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素不在边界上且未置成多边形色，
则把该像素入栈。
第 3章 基本图形生成算法
2．内点表示的四连通区域种子填充算法
基本思想：从多边形内部任一点（像素）出发，依, 左
上右下, 顺序判断相邻像素，如果是区域内的像素，则对其
填充，并重复上述过程，直到所有像素填充完毕。它也常称
为漫水法。
可以使用栈结构来实现该算法，算法的执行步骤如下：
种子像素入栈，当栈非空时，重复执行如下三步操作：
（ 1）栈顶像素出栈；
（ 2）将出栈像素置成多边形填充的颜色；
（ 3）按左、上、右、下的顺序检查与出栈像素相邻的
四个像素，若其中某个像素是区域内的像素，则把该像素入
栈。
第 3章 基本图形生成算法
3,扫描线种子填充算法
算法思想：在任意不间断区间中只取一个种子像素
（不间断区间指在一条扫描线上一组相邻元素），填充当
前扫描线上的该段区间；然后确定与这一区段相邻的上下
两条扫描线上位于区域内的区段，并依次把它们保存起来，
反复进行这个过程，直到所保存的每个区段都填充完毕。
可以填充有孔区域，对于每一个待填充区段，只需入
栈一次，因此提高了区域填充的效率。
第 3章 基本图形生成算法
3.3.5 圆域的填充
对每条扫描线，计算它与圆域的相交区间。接
着，为每一条扫描线建立一个新圆表，存放在该
行第一次出现的圆的有关信息。然后，为当前扫
描线设置一个活化圆表。由于一条线与一个圆只
能相交一个区间，所以在活性圆表中，每个圆只
需一个结点即可。结点内存放当前扫描线的区间
端点，以及用于计算下一条扫描线与圆相交的区
间端点所需的增量。该增量用于在当前扫描线处
理完毕之后，对端点坐标进行更新计算，以便得
到下一条扫描线的区间端点。
第 3章 基本图形生成算法
3.3.6 区域填充属性
1．填充样式
2．填充颜色
3．填充图案
第 3章 基本图形生成算法
3.4 字符
3.4.1 字符存储与显示
1．点阵字符
每个字符都是利用掩膜来定义，并将其写入帧缓存保
存和显示。
点阵字符的显示：首先从字库中将它的位图检索出来，
然后将检索到的位图写到帧缓冲器中。读取帧缓存中这些
像素值，就可以在屏幕上显示此字符。如果将保存在帧缓
存中某字符掩膜相应像素值均置成背景色或背景光强，就
可以擦除帧缓存中的该字符。
第 3章 基本图形生成算法
2．矢量字符
矢量字符被表达为一个点坐标的序列，相邻两点表示
一条矢量，字符的形状便由矢量序列刻划。
矢量字符的显示：首先从字库中读它的字符信息。然
后取出端点坐标，对其进行适当的几何变换，再根据各端
点的标志显示出字符。
第 3章 基本图形生成算法
3.4.2 字符属性
显示的字符的外观由字体、字形、字号、字间
距、行间距等属性控制。一般来说，字体确定风
格，字形确定外观，字号确定尺寸。
1,单个字符属性
2,文本属性
第 3章 基本图形生成算法
3.5 裁剪
3.5.1 点的裁剪
对于一点 P（ x,y），要判断其是否可见，可
利用下面的不等式组来判断此点是否落在窗口范
围内：
满足上述不等式组的点则在窗口范围内，可见，
予以保留；反之，该点落在窗口外，不可见，舍
弃（裁剪）。
? xrxxl ytyyb ?? ??
第 3章 基本图形生成算法
3.5.2 直线裁剪
1,Cohen-Sutherland裁剪算法（编码裁剪法）
基本思想：对于每条待裁剪的线段 P1P2分为三种情况
处理：（ 1）若 P1P2完全在窗口内，则显示该线段 P1P2，
简称, 取, 之；（ 2）若 P1P2完全在窗口外，则丢弃该线
段，简称, 舍, 之；（ 3）若线段既不满足, 取, 的条件，
也不满足, 舍, 的条件，则求线段与窗口边界的交点，在
交点处把线段分为两段，其中一段完全在窗口外，可舍弃
之，然后对另一段重复上述处理。
第 3章 基本图形生成算法
Cohen-Sutherland直线剪裁算法以区域编码为基础，
将窗口及其周围的八个方向以 4 bit的二进制数进行编码，
如图 3-42所示。具体编码过程为：
延长窗口的四条边线（ yt,yb,xr,xl），将二维平
面分成九个区域。任何一条线段的端点都按其所处区域赋
予 4位编码 CtCbCrCl。
??
? ??
??
? ??
??
? ??
??
? ??
o t h e r
xlxc
o t h e r
xrxc
o t h e r
ybyc
o t h e r
ytyc
lrbt 0
1
0
1
0
1
0
1
第 3章 基本图形生成算法
?如果某线段的两个端点的四位
二进制编码全为, 0000”，可直
接保留；
?如果对两端点的四位二进制编码进行逻辑与（按位乘）
运算，结果不为零，可直接舍弃；
?否则，这一线段可能与窗口相交。此时，需要对线段
进行再分割，即找到与窗口边线的一个交点，根据交
点位置，也赋予四位二进制编码，并对分割后的线段
重复进行检查，直到全部线段均被舍弃或被保留为止。
裁剪窗口
第 3章 基本图形生成算法
2．中点分割算法
基本思想：当一条直线段既不能直接保留也不能直接
舍弃，需要求其与区域的交点时，不断地用对分方法，舍
去线段的不可见部分，用中点去逼近线段与窗口边界的交
点。
第 3章 基本图形生成算法
3．梁友栋 -barsky裁剪算法
定义直线的参数化方程为：
首先按参数化形式写出裁剪条件：
这四个不等式可以表示为形式：
??
?
?????
???
101
1
uyuyy
xuxx
4,3,2,1?? kqup kk
第 3章 基本图形生成算法
其中，参数 pk,qk定义为：
任何平行于裁剪边界之一的直线 pk=0，其中 k对应于裁
剪边界（ k=1,2,3,4对应于左、右、下、上边界），如果还满
足 qk<0，则线段完全在边界外，舍弃该线段。如果 qk≥0，则
该线段平行于裁剪边界并且在窗口内。
?当 pk<0，线段从裁剪边界延长线的外部延伸到内部。
?当 pk>0时，线段从裁剪边界延长线的内部延伸到外部。
?当 pk≠0时，可以计算出线段与边界 k的延长线的交点的
u值,u=qk/pk。
第 3章 基本图形生成算法
梁友栋 -Barsky裁剪算法在寻找线段可见部分（如果
有可见线段）时可以归结为四个步骤：
（ 1）如果对所有的 k都有 pk=0和 qk<0，删除线段并
结束。否则继续执行下一步。
（ 2）对所有 pk<0的 k，计算 rk=qk/pk,将 0和各个
rk值之中的最大值赋给 u1。
（ 3）对所有 pk>0的 k，计算 rk=qk/pk,将 1和各个
rk值之中的最小值赋给 u2。
（ 4）如果 u1>u2，则线段完全落在裁剪窗口之外，
不可见，可直接舍弃。否则，裁剪后线段的端点由参数 u
的两个值 u1,u2计算出来。
第 3章 基本图形生成算法
3.5.3 多边形裁剪
1,Sutherland-Hodgman算法
基本思想：每次用窗口的一条边界对多边形进行裁剪，
把落在窗口外部的图形去掉，落在窗口内部的图形保留，
并把它作为下一次待裁剪的多边形。这样，当连续用窗口
的四条边界对原始多边形进行裁剪后，最后得到的就是裁
剪后的结果多边形。
第 3章 基本图形生成算法
2,Weiler-Atherton裁剪算法
基本思想：将待裁剪多边形（简写为 P1）和裁剪矩形
窗口（简写为 P2）均设定为按顺时针方向排列。算法从 P1
的任一顶点出发，沿着它的边向下处理，当 P1和 P2相交时
（假定交点为 I）：
（ 1）若 P1的边是进入 P2，则继续沿 P1的边往下处理，
同时输出该线段；
（ 2）若 P1的边是从 P2中出来，则从此交点 I开始，沿
着窗口边框向右检测 P2的边，即用 P2的有效边框去裁剪 P1
的边，找到 P1和 P2最靠近交点 I的新交点，同时输出由 I到
S之间窗边上的线段；
（ 3）返回交点 I，再沿着 P1处理各条边，直到处理完
P1的每一条边，回到起点为止。
第 3章 基本图形生成算法
3.5.4 曲线裁剪
对于被裁剪的曲线所围成的区域，找出包围
（外接）此区域的最小矩形，称其为曲线边界对
象的包围矩形（或包围盒），然后测试包围矩形
是否与矩形裁剪窗口有重叠。
如果包围矩形完全落在裁剪窗口内，则全部保
留该对象；
如果包围矩形完全落在裁剪窗口外，则全部舍
弃该对象；
如果不满足上述矩形测试的条件，则要求解直
线 -曲线联立方程组，得出裁剪窗口与曲线边界线
的交点，即裁剪交点，再进行判断。
第 3章 基本图形生成算法
3.5.5 字符裁剪
1．字符串裁剪
把整个字符串作为整体来对待。
2．字符裁剪
分别对每个字符来处理。
3．矢量 \像素裁剪
每个字符都看作是由一系列矢量（线段）或像素构成
的，故对每一个矢量或像素都必须个别地进行裁剪。
第 3章 基本图形生成算法
3.5.6 三维图形的裁剪
把二维线段的 Cohen-Sutherland裁剪算法稍加改进，
就能推广到三维平行投影的裁剪算法中。
对空间任意一点 P（ x,y,z）按其所处位置赋予 6位二
进制编码。
（ 1）两个端点的编码全为, 0000”，直接保留；
（ 2）对两端点的编码进行逻辑与运算，结果不为零，
可直接舍弃；
（ 3）否则，计算出线段与窗口表面的交点，并将线
段分段后继续处理，直到余下的线段符合前两种简单情况
为止。
第 3章 基本图形生成算法
3.6 反走样
对图形进行光栅化时，是用离散的像素显示在
连续空间定义的对象。这种用离散量表示连续量
时引起的失真现象称为走样。
用于减少或消除走样的技术称为反走样。
第 3章 基本图形生成算法
3.6.1 光栅图形的走样现象
1．阶梯形走样
2．狭小图形遗失
3．细节失真
第 3章 基本图形生成算法
3.6.2 常用反走样技术
1．提高分辨率
2,简单的区域取样
3,加权区域取样
