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

1、-作者xxxx-日期xxxx计算机图形学常用算法及代码大全【精品文档】2.1.1 生成直线的DDA算法数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。一、直线DDA算法描述：设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得= m =直线的斜率(21)可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x(22)yi+1=yi+y=yi+x·m(23)也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(

2、25)式(22)至(25)是递推的。二、直线DDA算法思想：选定x2x1和y2y1中较大者作为步进方向(假设x2x1较大)，取该方向上的增量为一个象素单位(x=1)，然后利用式(21)计算另一个方向的增量(y=x·m=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。三、直线DDA算法实现：1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2

3、、已知画线的颜色：color3、计算两个方向的变化量：dx=x2x1 dy=y2y14、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i<=steps；i+) putpixel(x，y，color)；/*在(x，y)处，以color色画点*/x=x+xin； y=y+yin； 五、直线DDA算法特点：该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。/brie

4、f 浮点数转整数的宏实现代码#define FloatToInteger(fNum) (fNum>0)?static_cast<int>(fNum+0.5):static_cast<int>(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 &

5、EndPt,COLORREF LineCor)long YDis = (EndPt.y - BeginPt.y);long XDis = (EndPt.x-BeginPt.x);long MaxStep = max(abs(XDis),abs(YDis); / 步进的步数float fXUnitLen = 1.0f; / X方向的单位步进float fYUnitLen = 1.0f; / Y方向的单位步进fYUnitLen = static_cast<float>(YDis)/static_cast<float>(MaxStep);fXUnitLen = static_

6、cast<float>(XDis)/static_cast<float>(MaxStep);/ 设置起点像素颜色pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast<float>(BeginPt.x);float y = static_cast<float>(BeginPt.y);/ 循环步进for (long i = 1;i<=MaxStep;i+)x = x + fXUnitLen;y = y + fYUnitLen;pDC->SetPixel(F

7、loatToInteger(x),FloatToInteger(y),LineCor);2.1.2 生成直线的Bresenham算法从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。一、直线Bresenham算法描述：它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。我们首先讨论m=y/x，当0m1且x1<x2时的Bresenham算法。从DDA

8、直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成：xi+1=xi+1(26)yi+1=yi+m(27)有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。二、直线Bresenham算法思想之一：由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设m<1），如下图所示。那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离

9、象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2： d1=y-yi=m(xi+1)+b-yi(28)d2=(yi+1)-y=(yi+1)-m(xi+1)-b(29)这两个距离差是d1-d2=2m(xi+1)-2yi2b-1(210)我们来分析公式(2-10)：(1)当此值为正时，d1>d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。(2)当此值为负时，d1<d2，说明直线上理论点离(xi+1，yi)象素较近，则下一个象素点应取(xi+1，yi)。(3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相

10、等，取哪个点都行，假设算法规定这种情况下取(xi+1，yi+1)作为下一个象素点。 因此只要利用(d1-d2)的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式：pi=x×(d1-d2)=2y·xi-2x·yi+c(211)式(2-11)中的x=(x2-x1)>0，因此pi与(d1-d2)有相同的符号；这里y=y2-y1，m=y/x；c=2y+x(2b-1)。下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。将式(2-11)中的下标i改写成i+1，得到：pi+1=2y·xi+1-2x·yi+1+c

11、(212)将式(2-12)减去(2-11)，并利用xi+1=xi+1，可得：pi+1= pi+2y-2x·(yi+1-yi)(213)再假设直线的初始端点恰好是其象素点的坐标，即满足：y1=mx1+b(214)由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x(215)这样，我们可利用误差判别变量，得到如下算法表示：初始 p1=2y-x(216)当pi0时： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x)否则：yi+1=yi,xi+1=xi+1， pi+1=pi+2y从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、

12、直线的两个端点坐标分量差x和y有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。三、直线Bresenham算法思想之二：由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(i)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi1，y(i+1)r)呢？设A为CD边的中点，正确的选择：若B点在A点上方，选择D点； 否则，选C点。用误差式描述为：(xi+1)=BC-AC=(yi+1-yir(28')求递推

13、公式：(xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-y(i+1)r(29')当(xi+1)0时，选D点，y(i+1)r = yir+1(xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1(210')当(xi+1)0时，选C点，y(i+1)r = yir(xi+2)= yi+1+myir-0.5=(xi+1)+m(211')初始时：(xs+1)=BC-AC=m(212')为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。令方程两边同乘2·x，即d=2·x·，则：初始时：d

14、= 2·y-x(213')递推式：当d0时： d=d+2·(yx)；y+；x+；否则： d=d+2·y；x+； (214')实现代码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<=dx; i+)  &

15、#160;  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<=dx; i+) drawpixel (x, y, color);x=x

16、+1，e=e+2dy;if (e>=0) y+, e=e-2dx;四、直线Bresenham算法实现：条件：0m1且x1<x21、输入线段的两个端点坐标和画线颜色：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<=x2；x+) putpixel(x,y,color) ；if(p>=0) y=y+1；p=p+2·(y-x)；else p=p+2·y；五、直线Bresenham算法完善

17、：现在我们修正(2-16)公式，以适应对任何方向及任何斜率线段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定xi+1和yi+1的变换规律。容易证明：当线段处于、区时，以|x|和|y|代替前面公式中的x和y，当线段处于、区时，将公式中的|x|和|y|对换，则上述两公式仍有效。在线段起点区分线段方向七、直线Bresenham算法特点：由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。2.2.2 中点算法生成圆中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中，用决策变量的符号来确定

18、象素点的选择，因此算法效率较高。一、中点画圆算法描述设要显示圆的圆心在原点(0，0)，半径为R，起点在(0，R)处，终点在(，)处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。为了应用中点画圆法，我们定义一个圆函数F(x，y)=x2+y2-R2(219)任何点(x，y)的相对位置可由圆函数的符号来检测：F(x，y)<0点(x，y)位于数学圆内=0点(x，y)位于数学圆上>0点(x，y)位于数学圆外(220)如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者

19、之一。中点画线算法假设M是E和SE的中点，即 ，则：1、当F(M)<0时，M在圆内(圆弧A)，这说明点E距离圆更近，应取点E作为下一象素点；2、当F(M)>0时，M在圆外(圆弧B)，表明SE点离圆更近，应取SE点；3、当F(M)=0时，在E点与SE点之中随便取一个即可，我们约定取SE点。 二、中点画圆算法思想因此，我们用中点M的圆函数作为决策变量di，同时用增量法来迭代计算下一个中点M的决策变量di+1。(221)下面分两种情况来讨论在迭代计算中决策变量di+1的推导。1、见图（a），若di<0，则选择E点，接着下一个中点就是，这时新的决策变量为：(222)（a）(di<

20、;0) 中点画线算法式(222)减去(221)得：di+1=di+2xi+3(223)2、见图（b），若di0，则选择SE点，接着下一个中点就是 ，这时新的决策变量为：(224)（b）(di0) 中点画线算法式(224)减去(221)得：di+1=di+2(xi-yi)+5(225)我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两步处理：（1）用前一次迭代算出的决策变量的符号来决定本次选择的点。（2）对本次选择的点，重新递推计算得出新的决策变量的值。剩下的问题是计算初始决策变量d0，如下图所示。对于初始点(0，R)，顺时针生成八分之一圆，下一个中点M的坐标是 ，所以：(226生成圆

21、的初始条件和圆的生成方向三、中点画圆算法实现1、输入：圆半径r、圆心(x0，y0)；2、确定初值：x=0，y=r、d=5/4-r；3、While(x<=y)·利用八分对称性，用规定的颜色color画八个象素点(x，y)；· 若d0y=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<0对应于e<-1/4。算法中其它与d有关的式子可把

22、d直接换成e。又由于e的初值为整数，且在运算过程中的迭代值也是整数，故e始终是整数，所以e<-1/4等价于e<0。因此，可以写出完全用整数实现的中点画圆算法。要求：写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果。六、中点画圆算法程序void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;while(x<=y)putdot(x0,y0,x,y,color);if(d<0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;put

23、dot(x0,y0,x,y,color)putpixel(x0+x,y0+y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,color);putpixel(x0-y,y0+x,color);putpixel(x0-y,y0-x,color);2.2.3 正负算法生成圆正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生

24、成圆弧。一、正负画圆算法描述设要显示圆的圆心在原点(0，0)，半径为R，初始点的坐标为(0，R)，顺时针生成八分之一圆，令：F(x，y)=x2+y2-R2则圆的方程为：F(x，y)=0 (2-27)当点(x，y)在圆内时，则F(x，y)<0；当点(x，y)在圆外时，则F(x，y)>0；当点(x，y)在圆上时，则F(x，y)=0；二、正负画圆算法思想现以下图的AB弧为例，来说明正负画圆法(顺时针生成圆)。假设当前点为Pi(xi，yi)，取下一个点Pi+1(xi+1，yi+1)的原则是： 1、当F(xi，yi)0时：取xi+1= xi+1，yi+1= yi。即向右走一步，从圆内走向圆外

25、。对应图(a)中的从Pi到Pi+1。2、当F(xi，yi)>0时：取xi+1= xi，yi+1= yi-1。即向下走一步，从圆外走向圆内。对应图(b)中的从Pi到Pi+1。由于向圆内或向圆外走取决于F(xi，yi)的正负，因此称为正负法。下面分两种情况求出F(xi，yi)的递推公式：(1) 当F(xi，yi)0时，向右走，取xi+1=xi+1，yi+1=yi，则F(xi+1，yi+1)=F(xi+1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1(2-28)(2) 当F(xi，yi)>0时，向下走，取xi+1=xi，yi+

26、1=yi-1，则F(xi+1，yi+1)=F(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1(2-9)初始时，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30)公式(2-28)、(2-29)和(2-30)就构成正负画圆算法的核心。给象素坐标(x，y)及F赋初始值后，进入循环画点；画点后，根据F的符号进行F值的递推和下一个点的获取，直到x>y为止。同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。三、正负画圆算法实现注意：初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下

27、图。例如，初始点(R，0)，逆时针生成圆，从图（b）可知：若当前点Pi在圆内，则下一点Pi+1(xi，yi+1)，即向上走一步；若当前点Pi在圆外，则下一点Pi+1(xi-1，yi)，即向左走一步；(a) 顺时针生成圆 (b) 逆时针生成圆五、正负画圆算法特点物理意义清楚，程序中只含整数运算，因此算法速度快。六、正负画圆算法程序/ 顺时针生成圆void PNARC(int x0,int y0,int r,int color)int x=0,y=r,f=0;while(x<=y)putdot(x0,y0,x,y,color);if(f<=0)f=f+2*x+1;x+;elsef=f-

28、2*y+1;y-;2.3 区域填充前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。区域填充一般分两类：多边形填充和种子填充。一、多边形填充1、填充条件多边形的顶点序列(Pi，i=0，1，n)、填充色。2、多边形内点的判别准则对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，因为多边形是闭合的，那么：若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图中测试点4引出的射线)；反之，

29、交点个数为偶数时，则该点为外点。(例：测试点2引出的射线)。多边形内点的判别准则和奇异点3、奇异点的处理：上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。 多边形内点的判别准则和奇异点综合以上情况，我们将多边形的顶点分为两大类： (1) 局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。(2)非极值点：如图中的点P3、

30、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。处理奇异点规则：（1）对于局部极值点，应看成两个点；（2）对于非极值点，应看成一个点。4、逐点判别算法步骤：(1)求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点置为背景色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，

31、从而影响了填充速度。 二、种子填充种子填充是将区域内的一点(种子)赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。1、填充条件区域内一点的坐标即种子坐标、边界色、填充色。2、连通方式区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部的任意象素。八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。注意：（1） 八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须

32、是四连通的，见下图(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.4 图案填充2.3.1 边相关扫描线多边形

33、填充算法边相关扫描线填充算法属于多边形填充类。它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。一、边相关扫描线填充算法描述扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+1=yi+1与该边的交点则为xi+1=xi+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。(a) 扫描线的相关性(b)

34、 边的相关性边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。1、边表（ET：Edge Table）用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为：扫描线 y 对应的ET表第一项：某边的最大y值（ymax）。注意要进行奇异点处理：对于非极值点应该ymax=ymax-1。第二项：某边的最小的y对应的x值。第三项：某边斜率的倒数:1/m。第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空。2、活动边表（AET：Active Edge Table）ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对

35、某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。二、边相关扫描线填充算法思想1、根据给出的多边形顶点坐标，建立ET表； 求出顶点坐标中最大y值ymax和最小y值ymin。2、初始化AET表指针，使它为空。3、使用扫描线的yj值作为循环变量，使其初值为ymin。 对于循环变量yj的每一整数值，重复作以下事情，直到yj大于ymax，或ET表与AET表都为空为止：(1) 如果ET表中yj桶非空，则将yj桶中的全部记录合并到AET表中。(2) 对AET表链中的记录按x的大小从小到大排序。(3) 依次取出AET表各记录中的xi

36、坐标值，两两配对填充，即将每对xi之间的象素填上所要求的颜色。(4) 如果AET表中某记录的ymax=yj，则删除该记录。(5) 对于仍留在AET表中的每个记录，用xi+1/m代替xi进行修改，这就是该记录的边线与下一条扫描线yj+1的交点。(6) 使yj加1，以便进入下一轮循环。三、边相关扫描线填充算法举例对下图(a)的多边形利用边相关扫描线填充算法进行处理：1、首先建立ET表。注意：在做奇异点处理时，当该边最大y值对应的顶点为非极值点时，边记录的第一项：ymax=ymax-1。例如：P3P4边、P3P2边、P4P5边，见下图(b)。2、接着建立AET表。AET表的建立过程就是有效地进行填充

37、的操作，在这个期间不断地做以下工作：（1）合并ET表；（2）x递增排序；（3）实施填充；（4）删除ymaxyj的边；（5）修改边记录xi=xi+1/m；（6）yj+1进入下一轮循环。结果见下图(c)。(a) 多边形 (b) ET表 (c) AET表四、边相关扫描线填充算法实现1、根据给定的多边形顶点坐标，建立ET 表。2、AET表初始化，每个桶置空。3、for(y=ymin;y<= ymax;y+) 合并当前扫描线y的ET表； 将y桶中每个记录按x项升序排列； 在当前y值下，将两两记录的x值之间的象素进行填充； 删除y=ymax的边记录； 修改边记录x=x+1/m； 六、边相关扫描线填充

38、算法特点该算法充分利用多边形的边相关性和扫描线的相关性，使用ET表对多边形的非水平边进行登记；用AET表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。2.3.2 扫描线种子填充算法该算法属于种子填充算法，它是以扫描线上的区段为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。一、扫描线种子填充算法思想扫描线种子填充算法的基本思想是：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。二、扫描线种子填充算

39、法实现借助于堆栈，上述算法实现步骤如下：1、初始化堆栈。2、种子压入堆栈。3、while（堆栈非空） (1)从堆栈弹出种子象素。(2)如果种子象素尚未填充，则：a.求出种子区段：xleft、xright;b.填充整个区段。leftxxright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。leftxxright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。四、扫描线种子填充算法特点1、该算法考虑了扫描线上象素

40、的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。2.3.3 边标志填充算法在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边标志填充算法就是在逐行处理时，利用边界色作为标志来进行填充的。例如某扫描线从左到右扫描时碰到边界色，立刻改变标志的状

41、态，接下来再根据标志的状态决定某象素点是否填充。一、边标志填充算法思想扫描线具有连贯性，这种连贯性只有在扫描线与多边形相交处才会发生变化，而每次的变化结果：无非是在前景色和背景色之间相互“切换”。边标志填充算法正是基于这一发现，先在屏幕上生成多边形轮廓线，然后逐条扫描处理。处理中：逐点读取象素值，若为边界色，则对该象素值进行颜色切换。二、边标志填充算法实现 1、用边界色画出多边形轮廓线，也就是将多边形边界所经过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。如下图所示。边标志填充算法3、逐条扫描线进行处理，对每条扫描线依从左

42、往右的顺序，逐个访问该扫描线上的象素。每遇到边界象素，标志取反。然后，按照标志是否为真，决定象素是否为填充色。四、边标志填充算法特点该算法思想简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。五、边标志填充算法程序EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)int i,x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*设置画笔色*/ for(i=0 ;i<n;i+)line(pi0,pi1,p(i+1)%n0,p(i+1)

43、%n)1); /*画出多边形的n条边*/用求极值的算法，从多边形顶点数组p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y<=ymax;y+) flag=-1;for(x=xmin;x<=xmax;x+) if(getpixel(x,y)=boundarycolor)flag=-flag;if(flag=1)putpixel(x,y, newcolor);六、边标志填充算法错误处理1、该算法虽然简单，但程序运行后会出现局部错误。从下图可以发现，对于多边形顶点为局部极值点时，扫描线与多边形的相交次数不再是偶数，而是奇数，填充时会出现“抽丝”现象。即某扫描线上不

44、该填充的区段填上色，而应该填充的区段却没有填上色。解决的办法：判断多边形顶点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志。2、特别当心多边形边界的扫描转换。在这里就不能考虑：不同的斜率产生的直线要亮度均匀，如下图(a)所示。否则当扫描线y遇到斜率小于1的边界线时，碰到几个边界点，会引起标志的无序改变，将导致填充的错误。解决的办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只能遇到一个点。请看下图(b)。在边标志填充算法中要注意多边形边界的扫描转换3.2 线段的裁剪直线段的裁剪比点复杂，其裁

45、剪方法又是多边形裁剪和三维图形裁剪的基础。一、直线裁剪的基本思想判断直线与窗口的位置关系：1确定直线是完全可见；2部分可见；3还是完全不可见。对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。二、裁剪线段和窗口的关系假定窗口左下角坐标为(xmin，ymin)，右上角坐标为(xmax，ymax)，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况：1、直线的两个端点均在窗口内，如图中AB线。这时直线完全可见，可被简单接受。2、直线的两个端点都在窗口外，并且位于窗口某一边界的同一外侧，如图中EF线。则直线完全不可见，可被简单舍弃。3、除此之外需要求交点，以确定直线在窗口某一

46、边界内是否有可见部分,并裁掉外部线段，显示内部线段。如CD、GH、IJ线。为了提高裁剪效率，算法设计一般可从下面两方面作出考虑：(1) 快速判断情况1和情况2。(2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。三、直线求交计算当线段P1P2穿过某边界L时，交点P的计算如图中所示。根据直线两点式方程：(32)整理后得通用交点公式：(33)1、与上边界的求交公式：(34)2、与下边界的求交公式：(35)3、与右边界的求交公式：(36)4、与左边界的求交公式：(37)四、直线裁剪的常用算法 1CohenSutherland算法2中点分割算法3梁友栋-Barsky裁剪算法3.2.1 Coh

47、enSutherland算法一、CohenSutherland算法思想：该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。二、CohenSutherland算法步骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域

48、在左边界外侧(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。2、判别根据C1和C2的具体值，可以有三种情况：（1）C1=C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，

49、均需要求交点。3、求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。当条件(C1&00010)成立时，表示端点P1位于窗口左边界外侧，按照前面介绍的求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。三、C

50、ohenSutherland算法分区编码程序：Code(int x,int y,int *c)*c=0;if(y>ymax) /*（xmin，ymin）和（xmax，ymax）为窗口左下角、右上角坐标。*/*c=*c|0x08; else if(y<ymin)*c=*c|0x04;if(x>xmax)*c=*c|0x02;else if(x<xmin)*c=*c|0x01;四、CohenSutherland算法的流程图：3.2.2 中点分割算法CohenSutherland直线裁剪算法，充分利用了直线段与裁剪边框的相关性，使裁剪速度大大提高，但在求交过程中仍采用了乘除运

51、算，裁剪速度受到影响。而中点分割法的特点，就在于它是用连续平分线段最终求得交点的方法代替用乘除法实现求交运算。这样只需进行整数的加法和用运算器右移一位来实现除法运算，从而避免去做大量的乘除法。一、中点分割算法思想：1、中点公式（38）2、中点分割法求交点的规则如图中所示，当线段P1P2求出中点P后，舍弃线段的哪部分，由下面两条规则决定：中点分割法求交点规则（1）如果P1与P同侧，移动P1点；（即可能的交点只能出现在PP2段）if(C1&C)!=0) P1=P;（2）如果P1与P不同侧，移动P2点。（即可能的交点只能出现在P1P段）if(C1&C)= =0) P2=P;二、中点分

52、割算法实现：1、将直线的两端点P1、P2编码得：C1、C2；2、判别根据C1和C2的具体值，可以有三种情况：（1）C1C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点（1）令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点；（2）保留窗内端点P2到暂存器里；（3）对P1编码为C1；（4）用中点公式求出中点，并编码得C；（5）按照中点算法的求交规则：若P1和P同侧，移动P1点；if(C1&C)!=0)P1=P;否则，移动P2点。 elseP2=P;（6）流程转（3），直到P1和P2相差一个单位时：令交点为P2，取出暂存器的端点赋给P1，然后转向流程1。三、中点分割算法特点：