计算机图形学常用算法及代码大全

2.1.1 生成直线的DDA 算法

数值微分法即DDA 法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。

一、直线DDA 算法描述：

设(x1，y 1) 和(x2，y 2) 分别为所求直线的起点和终点坐标，由直线的微分方程得

可通过计算由x 方向的增量△x 引起y 的改变来生成直线：

也可通过计算由y 方向的增量△y 引起x

的改变来生成直线：

式(2－2) 至(2－5) 是递推的。

二、直线DDA 算法思想：

选定x 2－x 1和y 2－y 1中较大者作为步进方向(假设x 2－x 1较大) ，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1) 计算另一个方向的增量(△y=△x ·m=m)。通过递推公式(2－2) 至(2－5) ，把每次计算出的(xi+1，y i+1) 经取整后送到显示器输出，则得到扫描转换后的直线。 之所以取x 2－x 1和y 2－y 1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。

另外，算法实现中还应注意直线的生成方向，以决定Δx 及Δy 是取正值还是负值。

三、直线DDA 算法实现：

1、已知直线的两端点坐标：(x1，y1) ，(x2，y2) 2、已知画线的颜色：color

3、计算两个方向的变化量：dx=x2－x1 dy=y2－y1 4、求出两个方向最大变化量的绝对值：

steps=max(|dx|，|dy|) 5、计算两个方向的增量(考虑了生成方向) ： xin=dx/steps

yin=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i

{ putpixel(x，y ，color) ；/*在(x，y) 处，以color 色画点*/ x=x+xin； y=y+yin； }

五、直线DDA 算法特点：

该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 //@brief 浮点数转整数的宏 实现代码

#define FloatToInteger(fNum)

((fNum>0)?static_cast(fNum+0.5):static_cast(fNum-0.5))

/*!

* @brief DDA画线函数 *

* @param pDC [in]窗口DC * @param BeginPt [in]直线起点 * @param EndPt [in]直线终点 * @param LineCor [in]直线颜色 * @return 无 */

void CDrawMsg::DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)

{

l ong YDis = (EndPt.y - BeginPt.y); l ong XDis = (EndPt.x-BeginPt.x);

l ong MaxStep = max(abs(XDis),abs(YDis)); // 步进的步数 f loat fXUnitLen = 1.0f; // X方向的单位步进 f loat fYUnitLen = 1.0f; // Y方向的单位步进

f YUnitLen = static_cast(YDis)/static_cast(MaxStep); f XUnitLen = static_cast(XDis)/static_cast(MaxStep); // 设置起点像素颜色

p DC->SetPixel(BeginPt.x,BeginPt.y,LineCor); f loat x = static_cast(BeginPt.x); f loat y = static_cast(BeginPt.y); // 循环步进

f or (long i = 1;i

x = x + fXUnitLen; y = y + fYUnitLen;

pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);

2.1.2 生成直线的B resenham 算法

从上面介绍的DDA 算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。

在生成直线的算法中，B resenham 算法是最有效的算法之一。B resenham 算法是一种基于误差判别式来生成直线的方法。

一、直线Bresenham 算法描述：

它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。

我们首先讨论m =△y/△x ，当0≤m ≤1且x 1

有两种B resenham 算法思想，它们各自从不同角度介绍了B resenham 算法思想，得出的误差判别式都是一样的。

二、直线B resenham 算法思想之一：

由于显示直线的象素点只能取整数值坐标，可以假设直线上第i 个象素点坐标为(x i ，y i ) ，它是直线上点(xi ，y i ) 的最佳近似，并且x i =xi (假设m

由图中可以知道，在x=x i +1处，直线上点的y 值是y =m(x i +1)+b，该点离象素点(x i +1，y i ) 和象素点(x i +1，y i +1)的距离分别是d 1和d 2：

这两个距离差是

我们来分析公式(2-10)：

(1)当此值为正时，d 1>d2，说明直线上理论点离(x i +1，y i +1)象素较近，下一个象素点应取(x i +1，y i +1)。

(2)当此值为负时，d 1

(3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相等，取哪个点都行，假设算法规定这种情况下取(x i +1，y i +1)作为下一个象素点。

因此只要利用(d1-d 2) 的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式：

式(2-11)中的△x=(x2-x 1)>0，因此p i 与(d1-d 2) 有相同的符号；

这里△y=y2-y 1，m =△y/△x ；c=2△y+△x(2b-1)。

下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c 。 将式(2-11)中的下标i 改写成i+1，得到：

将式(2-12)减去(2-11)，并利用x i +1=x i +1，可得：

再假设直线的初始端点恰好是其象素点的坐标，即满足：

由式(2-11)和式(2-14)得到p 1的初始值：

这样，我们可利用误差判别变量，得到如下算法表示：

从式(2-16)可以看出，第i+1步的判别变量p i+1仅与第i 步的判别变量p i 、直线的两个端点坐标分量差△x 和△y 有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。

三、直线B resenham 算法思想之二：

由于象素坐标的整数性，数学点(xi ，y i ) 与所取象素点(xi ，y ir ) 间会引起误差(εi ) ，当x i 列上已用象素坐标(xi ，y ir ) 表示直线上的点(xi ，y i ) ，下一直线点B (xi+1，y i+1) ，是取象素点C (xi+1，y ir )，还是D (xi ＋1，y (i+1)r) 呢？

设A 为CD 边的中点，正确的选择：

若B 点在A 点上方，选择D 点； 否则，选C 点。

用误差式描述为：

求递推公式：

当ε(xi+1)≥0时，选D 点，y (i+1)r = yir +1

当ε(xi+1) ﹤0时，选C 点，y (i+1)r = yir

初始时：

为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。 令方程两边同乘2·Δx ，即d=2·Δx

·ε，则： 初始时：

递推式：

实现代码

void Bresenhamline (int x0,int y0,int x1, int y1,int color) {

int x, y, dx, dy; float k, e;

dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i

{ drawpixel (x, y, color); x=x+1，e=e+k; if (e>=0)

{ y++, e=e-1;} } }

或者将e 扩大2dx 倍；

void Bresenhamline (int x0,int y0,int x1, int y1,int color) {

int x, y, dx, dy; float k, e;

dx = x1-x0, dy = y1- y0, k=dy/dx; e=-dx, x=x0, y=y0; for (i=0; i=0)

{ y++, e=e-2dx;} } }

四、直线B resenham 算法实现：

条件：0≤m ≤1且x 1

1、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color ； 2、设置象素坐标初值：x=x1，y=y1； 3、设置初始误差判别值：p=2·Δy -Δx ； 4、分别计算：Δx=x2-x1、Δy=y2-y1； 5、循环实现直线的生成： for(x=x1；x=0) { y=y+1； p=p+2·(Δy -Δx) ； } else

{ p=p+2·Δy ； } }

五、直线B resenham 算法完善：

现在我们修正(2-16)公式，以适应对任何方向及任何斜率线段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定x i+1和y i+1的变换规律。

容易证明：当线段处于①、④、⑧、⑤区时，以|△x|和|△y|代替前面公式中的△x 和△y ，当线段处于②、③、⑥、⑦区时，将公式中的|△x|和|△y|对换，则上述两公式仍有效。

在线段起点区分线段方向

七、直线B resenham 算法特点：

由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。

2.2.2 中点算法生成圆

中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中，用决策变量的符号来确定象素点的选择，因此算法效率较高。

一、中点画圆算法描述

设要显示圆的圆心在原点(0，0) ，半径为R ，起点在(0，R ) 处，终点在

(处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。 为了应用中点画圆法，我们定义一个圆函数

任何点(x，y) 的相对位置可由圆函数的符号来检测：

，)

如下图所示，图中有两条圆弧A 和B ，假定当前取点为P i (xi ，y i ) ，如果顺时针生成圆，那么下一点只能取正右方的点E (xi +1，y i ) 或右下方的点SE (xi +1，y i -1) 两者之一。

中点画线算法

假设M 是E 和SE 的中点，即

，则：

1、当F(M)

2、当F(M)>0时，M 在圆外(圆弧B ) ，表明SE 点离圆更近，应取SE 点； 3、当F(M)=0时，在E 点与SE 点之中随便取一个即可，我们约定取SE 点。

二、中点画圆算法思想

因此，我们用中点M 的圆函数作为决策变量d i ，同时用增量法来迭代计算下一个中点M

的决策变量d i+1。

下面分两种情况来讨论在迭代计算中决策变量d i+1的推导。 1、见图（a ），若d i

，这时

（a ）(di

式(2－22) 减去(2－21) 得：

2、见图（b ），若d i ≥0，则选择SE

点，接着下一个中点就是时新的决策变量为：

，这

（b ）(di ≥0) 中点画线算法

式(2－24) 减去(2－21) 得：

我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两步处理：

（1

）用前一次迭代算出的决策变量的符号来决定本次选择的点。 （2）对本次选择的点，重新递推计算得出新的决策变量的值。

剩下的问题是计算初始决策变量d 0，如下图所示。对于初始点(0，R ) ，顺时针生成八分之一圆，下一个中点M

的坐标是

，所以：

生成圆的初始条件和圆的生成方向

三、中点画圆算法实现

1、输入：圆半径r 、圆心(x0，y 0) ； 2、确定初值：x=0，y=r、d=5/4-r；

3、While(x

·利用八分对称性，用规定的颜色color 画八个象素点(x，y) ； · 若d≥0 {

y=y-1；

d=d+2(x-y)+5)； } 否则

d=d+2x+3； ·x=x+1； }

五、中点画圆算法完善

在上述算法中，使用了浮点数来表示决策变量d 。为了简化算法，摆脱浮点数，在算法中全部使用整数，我们使用e=d-1/4代替d 。显然，初值d=5/4-r对应于e=1-r。决策变量d

要求：写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果。

六、中点画圆算法程序

2.2.3 正负算法生成圆

正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧。

一、正负画圆算法描述

设要显示圆的圆心在原点(0，0) ，半径为R ，初始点的坐标为(0，R ) ，顺时针生成八分之一圆，令：F (x，

y)=x2+y2-R 2

则圆的方程为：

当点(x，y) 在圆内时，则F (x，y) 0； 当点(x，y) 在圆上时，则F (x，y) =0；

二、正负画圆算法思想

现以下图的AB 弧为例，来说明正负画圆法(顺时针生成圆) 。

假设当前点为P i (xi ，y i ) ，取下一个点P i+1(xi+1，y i+1) 的原则是：

1、当F (xi ，y i )≤0时：取x i+1= xi +1，y i+1= yi 。即向右走一步，从圆内走向圆外。对应图(a)中的从P i 到P i+1。

2、当F (xi ，y i ) >0时：取x i+1= xi ，y i+1= yi -1。即向下走一步，从圆外走向圆内。对应图(b)中的从P i 到P i+1。

由于向圆内或向圆外走取决于F (xi ，y i ) 的正负，因此称为正负法。 下面分两种情况求出F (xi ，y i ) 的递推公式：

(1) 当F (xi ，y i )≤0时，向右走，取x i+1=xi +1，y i+1=yi ，则

(2) 当F (xi ，y i ) >0时，向下走，取x i+1=xi ，y i+1=yi -1，则

初始时，x=0，y=R ，故

公式(2-28)、(2-29)和(2-30)就构成正负画圆算法的核心。 给象素坐标(x，y) 及F 赋初始值后，进入循环画点；

画点后，根据F 的符号进行F 值的递推和下一个点的获取，直到x >y 为止。 同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。

三、正负画圆算法实现

注意：初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下图。

例如，初始点(R ，0) ，逆时针生成圆，从图（b ）可知： 若当前点P i 在圆内，则下一点P i+1(xi ，y i +1)，即向上走一步； 若当前点P i 在圆外，则下一点P i+1(xi -1，y i ) ，即向左走一步；

(a) 顺时针生成圆 (b) 逆时针生成圆

五、正负画圆算法特点

物理意义清楚，程序中只含整数运算，因此算法速度快。

六、正负画圆算法程序

2.3 区域填充

前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。 区域填充一般分两类：多边形填充和种子填充。 一、多边形填充

1、填充条件

多边形的顶点序列(P i ，i=0，1，…，n) 、填充色。

2、多边形内点的判别准则

对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？

从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线) ，因为多边形是闭合的，那么：

若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图中测试点4

引出的射线) ； 反之，交点个数为偶数时，则该点为外点。(例：测试点2引出的射线) 。

多边形内点的判别准则和奇异点

3、奇异点的处理：

上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。

而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。

多边形内点的判别准则和奇异点

综合以上情况，我们将多边形的顶点分为两大类：

(1) 局部极值点：如图中的点P 1、P 2、P 4和P 6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。

(2)非极值点：如图中的点P 3、P 5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。 处理奇异点规则：

（1）对于局部极值点，应看成两个点； （2）对于非极值点，应看成一个点。

4、逐点判别算法步骤：

(1)求出多边形的最小包围盒：从P i (xi ，y i ) 中求极值，x min 、y min 、x max 、y max 。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点置为背景色。

逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。 二、种子填充

种子填充是将区域内的一点(种子) 赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。

1、填充条件

区域内一点的坐标即种子坐标、边界色、填充色。

2、连通方式

区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。

四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部的任意象素。

八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。

注意：

（1） 八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图(a)；

（2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图(b)。

(a) 八连通区域四连通边界 (b) 四连通区域八连通(或四连通) 边界

3、内点(x,y)的检测条件

(1) if(getpixel(x,y)!=边界色 && getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色)

这两个条件任何一个都可以用来检测象素点(x,y)是不是尚未填充。推荐使用条件(1)进行

象素点检测。

2.3.1 边相关扫描线多边形填充算法 2.3.2 扫描线种子填充算法 2.3.3 边标志填充算法

2.3.1 边相关扫描线多边形填充算法

边相关扫描线填充算法属于多边形填充类。它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。

该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。

一、边相关扫描线填充算法描述

扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。

边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线y i 与该边的交点为x i ，而后一条扫描线y i+1=yi +1与该边的交点则为x i+1=xi +1/m ，利用这种相关性可以省去大量的求交运算。见下图(b)所示。

(a) 扫描线的相关性 (b) 边的相关性

边相关扫描线填充算法的实现需要建立两个表：边表（ET ）和活动边表（AET ）。 1、边表（ET ：Edge Table）

用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：

扫描线 y 对应的ET 表

第一项：某边的最大y 值（y max ）。注意要进行奇异点处理：对于非极值点应该y max =ymax -1。 第二项：某边的最小的y 对应的x 值。 第三项：某边斜率的倒数:1/m 。

第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空。 2、活动边表（AET ：Active Edge Table）

ET 表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。

二、边相关扫描线填充算法思想

1、根据给出的多边形顶点坐标，建立ET 表； 求出顶点坐标中最大y 值y max 和最小y 值y min 。 2、初始化AET 表指针，使它为空。

3、使用扫描线的y j 值作为循环变量，使其初值为y min 。

对于循环变量y j 的每一整数值，重复作以下事情，直到y j 大于y max ，或ET 表与AET 表都为空为止：

(1) 如果ET 表中y j 桶非空，则将y j 桶中的全部记录合并到AET 表中。 (2) 对AET 表链中的记录按x 的大小从小到大排序。

(3) 依次取出AET 表各记录中的x i 坐标值，两两配对填充，即将每对x i 之间的象素填上所要求的颜色。

(4) 如果AET 表中某记录的y max =yj ，则删除该记录。

(5) 对于仍留在AET 表中的每个记录，用x i +1/m代替x i 进行修改，这就是该记录的边线与下一条扫描线y j +1的交点。

(6) 使y j 加1，以便进入下一轮循环。

三、边相关扫描线填充算法举例

对下图(a)的多边形利用边相关扫描线填充算法进行处理： 1、首先建立ET 表。

注意：在做奇异点处理时，当该边最大y 值对应的顶点为非极值点时，边记录的第一项：y max =ymax -1。例如：P 3P 4边、P 3P 2边、P 4P 5边，见下图(b)。

2、接着建立AET 表。AET 表的建立过程就是有效地进行填充的操作，在这个期间不断地做以下工作：

（1）合并ET 表； （2）x 递增排序； （3）实施填充； （4）删除y max ＝y j 的边； （5）修改边记录x i =xi +1/m ； （6）y j +1进入下一轮循环。 结果见下图(c)。

(a) 多边形 (b) ET表 (c) AET表

四、边相关扫描线填充算法实现

1、根据给定的多边形顶点坐标，建立ET 表。 2、AET 表初始化，每个桶置空。 3、for(y=y min ;y

合并当前扫描线y 的ET 表； 将y 桶中每个记录按x 项升序排列；

在当前y 值下，将两两记录的x 值之间的象素进行填充； 删除y =y max 的边记录； 修改边记录x =x +1/m ； }

六、边相关扫描线填充算法特点

该算法充分利用多边形的边相关性和扫描线的相关性，使用ET 表对多边形的非水平边进行登记；用AET 表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。

2.3.2 扫描线种子填充算法

该算法属于种子填充算法，它是以扫描线上的区段为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。

一、扫描线种子填充算法思想

扫描线种子填充算法的基本思想是：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。

二、扫描线种子填充算法实现

借助于堆栈，上述算法实现步骤如下： 1、初始化堆栈。 2、种子压入堆栈。 3、while （堆栈非空） {

(1)从堆栈弹出种子象素。 (2)如果种子象素尚未填充，则： a. 求出种子区段：x left 、x right ; b. 填充整个区段。

c. 检查相邻的上扫描线的x left ≤x≤xright 区间内, 是否存在需要填充的新区段，如果存在的话，则把每个新区段在x left ≤x≤xright 范围内的最右边的象素，作为新的种子象素依次压入堆栈。

d. 检查相邻的下扫描线的x left ≤x≤xright 区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在 x left ≤x≤xright 范围内的最右边的象素，作为新的种子象素依次压入堆栈。

}

四、扫描线种子填充算法特点

1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。

2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。

3、种子出栈时，则填充整个区段。

4、这样有机的结合：一边对尚未填充象素的登记（素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。

2.3.3 边标志填充算法

在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边标志填充算法就是在逐行处理时，利用边界色作为标志来进行填充的。例如某扫描线从左到右扫描时碰到边界色，立刻改变标志的状态，接下来再根据标志的状态决定某象素点是否填充。

一、边标志填充算法思想

扫描线具有连贯性，这种连贯性只有在扫描线与多边形相交处才会发生变化，而每次的变化结果：无非是在前景色和背景色之间相互“切换”。

边标志填充算法正是基于这一发现，先在屏幕上生成多边形轮廓线，然后逐条扫描处理。处理中：逐点读取象素值，若为边界色，则对该象素值进行颜色切换。

二、边标志填充算法实现

1、用边界色画出多边形轮廓线，也就是将多边形边界所经过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找出多边形的最小包围盒：x min 、y min 、x max 、y max 。如下图所示。

边标志填充算法

3、逐条扫描线进行处理，对每条扫描线依从左往右的顺序，逐个访问该扫描线上的象素。每遇到边界象素，标志取反。然后，按照标志是否为真，决定象素是否为填充色。

四、边标志填充算法特点

该算法思想简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。

五、边标志填充算法程序

六、边标志填充算法错误处理

1、该算法虽然简单，但程序运行后会出现局部错误。从下图可以发现，对于多边形顶点为局部极值点时，扫描线与多边形的相交次数不再是偶数，而是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。

解决的办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志。

2、特别当心多边形边界的扫描转换。在这里就不能考虑：不同的斜率产生的直线要亮度均匀，如下图(a)所示。否则当扫描线y 遇到斜率小于1的边界线时，碰到几个边界点，会引起标志的无序改变，将导致填充的错误。

解决的办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y 方向增长一步，x 方向增长1/m步距，以保证扫描线y 遇到斜率小于1的边界时，只能遇到一个点。请看下图(b)。

在边标志填充算法中要注意多边形边界的扫描转换

3.2 线段的裁剪

直线段的裁剪比点复杂，其裁剪方法又是多边形裁剪和三维图形裁剪的基础。

一、直线裁剪的基本思想

判断直线与窗口的位置关系： 1．确定直线是完全可见； 2．部分可见； 3．还是完全不可见。

对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。

二、裁剪线段和窗口的关系

假定窗口左下角坐标为(xmin ，y min ) ，右上角坐标为(xmax ，y max ) ，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况： 1、直线的两个端点均在窗口内，如图中AB 线。这时直线完全可见，可被简单接受。 2、直线的两个端点都在窗口外，并且位于窗口某一边界的同一外侧，如图中EF 线。则直线完全不可见，可被简单舍弃。

3、除此之外需要求交点，以确定直线在窗口某一边界内是否有可见部分, 并裁掉外部线段，

显示

内部线段。如CD 、GH 、IJ 线。

为了提高裁剪效率，算法设计一般可从下面两方面作出考虑： (1) 快速判断情况1和情况2。

(2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。

三、直线求交计算

当线段P 1P 2穿过某边界L 时，交点P 的计算如图中所示。

根据直线两点式方程：

整理后得通用交点公式：

1、与上边界的求交公式：

2、与下边界的求交公式：

3、与右边界的求交公式：

4、与左边界的求交公式：

四、直线裁剪的常用算法 1．Cohen －Sutherland 算法 2．中点分割算法

3．梁友栋-Barsky 裁剪算法

3.2.1 Cohen－Sutherland 算法

一、Cohen －Sutherland 算法思想：

该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。

对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。

二、Cohen －Sutherland 算法步骤：

1、分区编码

延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。 四位二进制代码的编码规则是：

(1)第一位置1：区域在左边界外侧

(2)第二位置1：区域在右边界外侧 (3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧

裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。

设线段的两个端点为P 1（x 1，y 1）和P 2（x 2，y 2），根据上述规则，可以求出P 1和P 2所在区域的分区代码C 1和C 2。 2、判别

根据C 1和C 2的具体值，可以有三种情况：

（1）C 1=C 2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C 1&C 2≠0（两端点代码按位作逻辑乘不为0），即C 1和C 2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。 3、求交点

假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。

为了规范算法，令线段的端点P 1为外端点，如果不是这样，就需要P 1和P 2交换端点。 当条件(C 1&0001≠0)成立时，表示端点P 1位于窗口左边界外侧，按照前面介绍的求交公式，进行对左边界的求交运算。

依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。

求出交点P 后，用P 1=P 来舍去线段的窗外部分，并对P 1重新编码得到C 1，接下来算法转回第2步继续对其它边界进行判别。

三、Cohen －Sutherland 算法分区编码程序：

四、Cohen －Sutherland 算法的流程图：

3.2.2 中点分割算法

Cohen －Sutherland 直线裁剪算法，充分利用了直线段与裁剪边框的相关性，使裁剪速度大大提高，但在求交过程中仍采用了乘除运算，裁剪速度受到影响。而中点分割法的特点，就在于它是用连续平分线段最终求得交点的方法代替用乘除法实现求交运算。这样只需进行整数的加法和用运算器右移一位来实现除法运算，从而避免去做大量的乘除法。

一、中点分割算法思想：

1、中点公式

2、中点分割法求交点的规则

如图中所示，当线段P 1P 2求出中点P 后，舍弃线段的哪部分，由下面两条规则决定：

中点分割法求交点规则

（1）如果P 1与P 同侧，移动P 1点；（即可能的交点只能出现在PP 2段） if((C 1&C )!=0) P 1=P ;

（2）如果P 1与P 不同侧，移动P 2点。（即可能的交点只能出现在P 1P 段） if((C 1&C )= =0) P 2=P ;

二、中点分割算法实现：

1、将直线的两端点P 1、P 2编码得：C 1、C 2； 2、判别

根据C 1和C 2的具体值，可以有三种情况：

（1）C 1＝C 2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C 1&C 2≠0（两端点代码按位作逻辑乘不为0），即C 1和C 2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。 3、求交点

（1）令窗外端点为P 1，如果窗外点不是P 1，则P 1和P 2交换端点； （2）保留窗内端点P 2到暂存器里； （3）对P 1编码为C 1； （4

）用中点公式求出中点 （5）按照中点算法的求交规则：

若P 1和P 同侧，移动P 1点； if((C 1&C )!=0) P 1=P ; 否则，移动P 2点。 else P 2=P ;

，并编码得C ；

（6）流程转（3），直到P 1和P 2相差一个单位时：令交点为P 2，取出暂存器的端点赋给P 1，然后转向流程1。

三、中点分割算法特点：

1、求交点的次数（n ）与线段长度（L ）有关，其关系为：L =2n 。

例如：线段长度为256，则求交点的次数为8。

2、中点分割法求出的交点是边界上的有效交点，而不是边界及其延长线上的交点。

（而Cohen －Sutherland 直线裁剪算法求出的则是边界上或者边界的延长线上的交点。）

3.2.3 梁友栋-Barsky 裁剪算法

Cyrus 和Beck 用参数化方法提出了比Cohen-Sutherland 更有效的算法。后来梁友栋和Barsky 独立地提出了更快的参数化线段裁剪算法，也称为Liany-Barsky （LB ）算法。

一、梁友栋-Barsky 裁剪算法思想：

我们知道，一条两端点为P 1（x 1，y 1）、P 2（x 2，y 2）的线段可以用参数方程形式表示：

式中，Δx=x2-x 1，Δy=y2-y 1，参数u 在0～1之间取值，P （x ，y ）代表了该线段上的一个点，其值由参数u 确定，由公式可知，当u=0时，该点为P 1（x 1，y 1），当u=1时，该点为P 2（x 2，y 2）。如果点

P （x ，y ）位于由坐标（xw min ，yw min ）和（xw max ，yw max ）所确定的窗口内，那么下式成立：

这四个不等式可以表示为：

其中，p 、q 定义为：

从（3-12）式可以知道：任何平行于窗口某边界的直线，其p k =0，k 值对应于相应

的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足q k

1、当p k

2、当p k >0时，线段从裁剪边界延长线的内部延伸到外部；

例如，当Δx≥0时，对于左边界p 10（p 2=Δx ），线段从右边界的内部到外部。 当Δy0（p 3=-Δy ），线段从下边界的内部到外部； 对于上边界p 4

对于每条直线，可以计算出参数u 1和u 2，该值定义了位于窗口内的线段部分：

1、u 1的值由线段从外到内遇到的矩形边界所决定（p k

2、u 2的值由线段从内到外遇到的矩形边界所决定（p k >0），对这些边界计算r k =qk /pk ，u 2取0和各个r 值之中的最小值。

3、如果u 1>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u 1和u 2计算出来。

二、梁友栋-Barsky 裁剪算法实现：

1、初始化线段交点的参数：u 1=0，u 2=1；

2、计算出各个裁剪边界的p 、q 值；

3、调用函数clipTest()，在函数中根据p 、q 来判断：是舍弃线段还是改变交点的参数。

（1） 当p

（u 1=max{u1，…，r k }）

（2） 当p>0时，参数r 用于更新u 2。

（u 2=min{u2，…，r k }）

（3）如果更新了u 1或u 2后，使u 1>u2，则舍弃该线段。

（4）当p=0且q

4、p 、q 的四个值经判断后，如果该线段未被舍弃，则裁剪线段的端点坐标由参数u 1和u 2的值决定。

四、梁友栋-Barsky 裁剪算法特点：

梁友栋-Barsky 算法只能应用于矩形窗口的情形。通常梁友栋-Barsky 算法比Cohen －Sutherland 算法效率更高，因为需要计算的交点数目减少了。更新参数u1、u2仅仅需要一次除法；线段与窗口边界的交点仅计算一次，就计算出u1、u2最后的值。相比之下，即使一条线段完全落在裁剪窗口之外，Cohen －Sutherland 算法也要对它反复求交点，而且每次求交计算都需要做乘除法。

梁友栋-Barsky 和Cohen －Sutherland 算法还可以扩展为三维裁剪算法。

3.3.1 Sutherland-Hodgeman多边形裁剪

Sutherland-Hodgman 算法也叫逐边裁剪法，该算法是萨瑟兰德(I ．E ．Sutherland) 和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。

一、Sutherland-Hodgeman 多边形裁剪算法思想：

每次用窗口的一条边界(包括延长线) 对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。

然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。

依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示。

新的多边形顶点序列产生规则：

在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。

如下图所示, 依序考虑多边形的各条边。假设当前处理的多边形的边为SP (箭头表示顺序关系，S 为前一点，P 为当前点) ，边SP 与裁剪线的位置关系只有下面四种情况：

1、S 在外侧，P 在内侧。则交点Q 、当前点P 保存到新多边形中。

2、S 、P 均在内侧，则当前点P 保存到新多边形中。

3、S 在内侧，P 在外侧。则交点Q 保存到新多边形中。

4、S 、P 均在外侧。则没有点被保存到新多边形中。

二、Sutherland-Hodgeman 多边形裁剪算法实现：

1、已知：多边形顶点数组p[ ][2]，顶点个数n ，

裁剪边界xmin(假设对左边界进行裁剪) ，

定义新多边形顶点数组q[][2]。

2、赋初值：被裁多边形顶点数组的下标变量i=0；

新多边形顶点数组的下标变量j=-1；

前一个点S 的x 方向分量s[0]=p[n-1][0]；

S 的y 方向分量s[1]=p[n-1][1]；

前一个点S 的内外标志，用变量flag 来标识：

0表示在内侧，1表示在外侧。

if(s在边界内侧) /*例如对左边界：s[0]>=xmin*/

flag=0；

else

flag=1；

3、对多边形的n 条边进行处理，对当前点号的考虑为：0～n-1。

for(i=0；i

{

if(当前第i 个顶点是否在边界内侧？) /*对左边界：p[i][0]>=xmin */

{

if(flag!=0) /*前一个点在外侧吗？*/

{

flag=0；/*从外到内的情况，将标志置0, 作为下一次循环的前一点标志*/ j++；

q[j][0]=求出交点的x 方向分量； /*将交点q 放入新多边形*/

q[j][1]=求出交点的y 方向分量；

}

j++；

q[j][0]= p[i][0]； /*将当前点p i 放入新多边形*/

q[j][1]= p[i][1]；

}

else

{

if(flag==0) /*前一个点在内侧吗？*/

{

flag=1；/*从内到外的情况，将标志置1, 作为下一次循环的前一点标志*/ j++；

q[j][0]=求出交点的x 方向分量； /*将交点q 放入新多边形*/

q[j][1]=求出交点的y 方向分量；

}

}

s[0]=p[i][0]； /*将当前点作为下次循环的前一点*/

s[1]=p[i][1]；

}

四、点在边界内侧的判断方法：

为了判断p i 点是否在边界内侧可用坐标比较法和更通用的向量叉积符号判别法。

1、坐标比较法

将点的某个方向分量与边界进行比较。

例如，判断某点是否在下边界内侧, 用条件判别式： if(p[i][1]>=ymin) 即可。 对其它边界也一样。但不能写成通用公式。

2、向量叉积法

为简单计，测试点表示为P 点。假设窗口边界

方向为顺时针，如图中所示，对于其中任一边界向

量，从向量起点A 向终点B 看过去：

如果被测试点P 在该边界线右边(即内侧) ，

AB ×AP 的方向与X -Y 平面垂直并指向屏幕里面，即右手坐标系中Z 轴的负方向。 反过来，如果P 在该边界线的左边(即外侧) ，这时AB ×AP 的方向与X -Y 平面垂直并指向屏幕外面，即右手坐标系中Z 轴的正方向。

设：点P (x，y) 、点A (xA ，y A ) 、点B (xB ，y B ) ，

向量AB ={(xB -x A ) ，(yB -y A )}，

向量AP ={(x-xA ) ，(y-yA )}，

那么AB ×AP 的方向可由下式的符号来确定：

因此，当V ≤0时，P 在边界线内侧；

而V >0时，

P 在边界线外侧。

五、Sutherland-Hodgeman 多边形裁剪算法特点： Sutherland －Hodgeman 多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。

上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。

3.3.2 Weiler－Atherton 任意多边形裁剪

Sutherland －Hodgeman 算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton 多边形裁剪算法正是满足这种要求的算法。

一、Weiler －Atherton 任意多边形裁剪算法描述：

在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o ）、甚至是带有内环的（子区），见下图。

裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：

1、被裁剪多边形为主多边形，记为A ；

2、裁剪窗口为裁剪多边形，记为B 。

主多边形A 和裁剪多边形B 的边界将整个二维平面分成了四个区域：

1、A ∩B （交：属于A 且属于B ）；

2、A －B （差：属于A 不属于B ）；

3、B －A （差：属于B 不属于A ）；

4、A ∪B (并：属于A 或属于B ，取反；即：不属于A 且不属于B ) 。

内裁剪即通常意义上的裁剪，取图元位于窗口之内的部分，结果为A ∩B 。 外裁剪取图元位于窗口之外的部分，结果为A －B 。

观察右图不难发现裁剪结果区域的边界由被裁

剪多边形的部分边界和裁剪窗口的部分边界两部分

构成，并且在交点处边界发生交替，即由被裁剪多

边形的边界转至裁剪窗口的边界，或者反之。由于

多边形构成一个封闭的区域，所以，如果被裁剪多

边形和裁剪窗口有交点，则交点成对出现。这些交

点分成两类：

一类称“入”点，即被裁剪多边形由此点进入裁剪

窗口，如图中a 、c 、e ；

一类称“出”点，即被裁剪多边形由此点离开裁剪

窗口，如图中b 、d 、f 。

二、Weiler －Atherton 任意多边形裁剪算法思想：

假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。

算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；

而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。

按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。

由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。

三、Weiler －Atherton 任意多边形裁剪算法步骤：

1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。

2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。

3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。

然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ，并放入数组3中； 同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ，放入数组4中；

4、初始化输出数组Q ，令数组Q 为空。接着从数组3中寻找“入”点。

如果“入”点没找到，程序结束。

5、如果找到“入”点，则将“入”点放入S 中暂存。

6、将“入”点录入到输出数组Q 中。并从数组3中将该“入”点的“入”点标记删去。

7、沿数组3顺序取顶点：

如果顶点不是“出点”，则将顶点录入到输出数组Q 中，流程转第7步。 否则，流程转第8步。

8、沿数组4顺序取顶点：

如果顶点不是“入点”，则将顶点录入到输出数组Q 中，流程转第8步。 否则，流程转第9步。

9、如果顶点不等于起始点S ，流程转第6步，继续跟踪数组3。

否则，将数组Q 输出；

流程转第4步，寻找可能存在的分裂多边形。

算法在第4步：满足“入”点没找到的条件时，算法结束。算法的生成过程见下图所示。

四、Weiler －Atherton 任意多边形裁剪算法实现：

1、算法在实现中，需要用到六个数组，分别用来存放：被裁剪多边形、裁剪窗口、交点数组、插入交点后的被裁剪多边形、插入交点后的裁剪窗口、输出多边形。

2、由于交点具有“入”、“出”标记，因此凡与交点有关的数组都要采用结构数组类型： struct point

{

double x；

double y；

int flag；

}交点数组，数组3，数组4；

标记flag 有三种状态：

0：非交点；

1：“入”点；

-1：“出”点。

3、求交点时，利用被裁剪多边形的各边去对裁剪窗口的各边求交点：

for （被裁剪多边形的各边）

{

…；

for （裁剪窗口的各边）

{

求有效交点；放入交点数组；

…；

}

}

4、交点的顺序插入，意味着要对交点数组排序后再分别插入到数组1、数组2的相应位置上。

5、所谓找“入”点、“出”点，必须根据flag 找寻满足条件的顶点位置。不光数组3中要找“入”点、“出”点，而且找到后还要转到数组4的相应顶点位置处。对数组4的处理也同上。这种处理在本算法中大量遇到。

六、Weiler －Atherton 任意多边形裁剪算法特点：

1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。

2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。

3、裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。

七、Weiler －Atherton 任意多边形裁剪算法小结：

前面介绍的是内裁算法，即保留裁剪窗口内的图形。而外裁算法（保留裁剪窗口外的图形）同内裁算法差不多。

外裁算法与内裁算法不同的是：

1、从被裁剪多边形的一个“出点”开始，碰到出点，沿着被裁剪多边形按顺时针方向搜集顶点序列；

2、而当遇到“入点”时，则沿着裁剪窗口按逆时针方向搜集顶点序列。

按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点为止。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。

由于可能存在分裂的多边形，因此算法要考虑：将搜集过的“出点”的出点记号删去，以免重复跟踪。将所有的出点搜集完毕后算法结束。

Weiler －Atherton 算法的的设计思想很巧妙，裁剪是一次完成，不象

Sutherland-Hodgman 多边形裁剪算法，每次只对裁剪窗口的一条边界及其延长线进行裁剪，如裁剪窗口有n 条边，则要调用n 次S -H 算法后才能最后得出裁剪结果。

但Weiler －Atherton 算法的编程实现比Sutherland-Hodgman 算法稍难，主要难在入、出点的查寻以及跨数组搜索上。