第3章 基本图形元素生成算法精选PPT.ppt

《第3章 基本图形元素生成算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章 基本图形元素生成算法精选PPT.ppt（162页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 基本图形元素基本图形元素生成算法生成算法第1页，本讲稿共162页3.1 直线的扫描转换直线的扫描转换 3.1.1DDA算法DDA算法是根据直线的微分方程来计算x或y生成直线的扫描转换算法。在一个坐标轴上以单位间隔对线段取样,以决定另一个坐标轴方向上最靠近理想线段的整数值。第2页，本讲稿共162页设(x0,y0)为直线段的始点,(x1,y1)为直线段的终点,且端点坐标均为整数,则直线的微分方程为设|k|1,则有 yi+1=kxi+1+b=k(xi+x)+b=yi+kx上式表明,若x=1,则当x每递增1时,y递增k。扫描转换开始时,取直线始点(x0,y0)作为初始坐标。算法描述如下:k

2、为直线的斜率第3页，本讲稿共162页voidDDA-line(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;intx;floaty,k,deltx,delty;deltx=x1-x0;delty=y1-y0;k=deltydeltx;y=y0;for(x=x0;x=x1;x+)putpixel(x,int(y+0.5),color);y=y+k;第4页，本讲稿共162页3.1.2中点画线法为了讨论的方便,假定直线的斜率在01之间,其它情况参照下述讨论进行处理。假设直线的起点和终点分别为(x0,y0)和(x1,y1),则直线方程为F(x,y)=ax+by+c=0第

3、5页，本讲稿共162页其中,a=y0-y1,b=x1-x0,c=x0y1-x1y0。对于直线上的点,F(x,y)=0;对于直线上方的点,F(x,y)0;而对于直线下方的点,F(x,y)0。如图3.1所示,若直线在x方向上增加一个单位,则在y方向上的增量只能在0和1之间。假设横坐标为xP的各像素点中最佳逼近于理想直线的像素为(xP,yP),用实心小圆表示。那么,下一个与直线最近的像素只能是正右方的P1(xP+1,yP)或右上方的P2(xP+1,yP+1)两者之一,用空心小圆表示。我们用P1和P2的中点M(xP+1,yP+0.5)与理想直线的位置关系来判定。第6页，本讲稿共162页图3.1中点画线

4、示意图第7页，本讲稿共162页设Q是理想直线与垂直线x=xP+1的交点。若M在Q的下方,则P2离理想直线近,应取为下一个像素;否则应取P1。为此,我们构造判别式d=F(M)=F(xP+1,yP+0.5)=a(xP+1)+b(yP+0.5)+c当d0时,M在直线上方,则应取正右方的P1;当d=0时,约定取正右方的P1。第8页，本讲稿共162页下面我们讨论如何计算判别式d。由于d是xP和yP的线性函数,因而可以采用增量方法计算,以提高运算效率。当d0时,取正右方像素P1,再下一个像素应在P1的正右方像素P3(xP+2,yP)和P1的右上方像素P4(xP+2,yP+1)中选取,应计算d1=F(xP+

5、2,yP+0.5)=a(xP+2)+b(yP+0.5)+c=d+a第9页，本讲稿共162页故在d0的情况下,d的增量为a。而若d0,则取右上方像素P2,再下一个像素应在P2的正右方像素P4(xP+2,yP+1)和P2的右上方像素P5(xP+2,yP+2)中选取,应计算d1=F(xP+2,yP+1.5)=a(xP+2)+b(yP+1.5)+c=d+a+b故在d0的情况下,d的增量为a+b。第10页，本讲稿共162页再讨论d的初始值。第一个像素应取左端点(x0,y0),相应的判别式为d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x

6、0,y0)+a+0.5b d的初始值为：a+0.5b第11页，本讲稿共162页中点画线法的伪C算法描述如下:voidMidPoint-Line(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;inta,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+bdelta1=2*a;delta2=2*(a+b);x=x0;y=y0;第12页，本讲稿共162页putpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=delta2;elsex+;d+=delta1;putpixel(x,y,color);第

7、13页，本讲稿共162页3.1.3Bresenham算法Bresenham画线算法与中点画线法有相似之处,也是通过在每列像素中确定与理想直线最近的像素来进行直线的扫描转换的。为了讨论的方便,不妨也假定直线的斜率在01之间。如图3.2所示,过各行、各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列像素中与该交点最近的像素。第14页，本讲稿共162页图3.2Bresenham算法误差项d的几何意义第15页，本讲稿共162页算法的伪C描述如下:voidBresenham-Line(x0,y0,x1,y1,color)intx0,y0,x1,y1,col

8、or;intx,y,dx,dy;floatk,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;第16页，本讲稿共162页for(i=0;i=0)y=y+1;e=e-1;第17页，本讲稿共162页上述算法在计算直线的斜率与误差项时,要用到小数和除法,不便于硬件实现。由于算法中只用到误差项的符号,因此,为了避免除法,令e=2edx,用e代替e。改进之后的算法如下:第18页，本讲稿共162页voidBresenham-Line(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;intx,y,dx,dy,e;dx=x1-x0;dy=

9、y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)第19页，本讲稿共162页y=y+1;e=e-2*dx;第20页，本讲稿共162页3.2 圆和椭圆的扫描转换圆和椭圆的扫描转换3.2.1圆的扫描转换1.中点画圆法为了讨论的方便,我们考虑中心在原点,半径为R的圆的第二个八分圆弧,圆的其它部分可通过一系列的简单的反射变换得到。也就是讨论如何从(0,R)到(R/,R/)顺时针确定最佳逼近于该圆弧的像素序列。第21页，本讲稿共162页中心在原点,半径为R的圆的方程为x2+y2=R2若令F(x,y)=x2+y2-R2,则上述方程为 F(x,y)=0第22页，本讲稿共162页如图3.3所

10、示,假定x坐标为xP的像素中最佳逼近理想圆弧的为P(xP,yP),那么,下一个像素只能是正右方的P1(xP+1,yP)或右下方的P2(xP+1,yP-1)两者之一。引入P1和P2的中点M(xP+1,yP-0.5),当M在圆内时,应取P1(xP+1,yP)为下一个像素,否则,应取P2(xP+1,yP-1)为下一个像素。为此,构造判别式d=F(M)=F(xP+1,yP-0.5)=(xP+1)2+(yP-0.5)2-R2第23页，本讲稿共162页图3.3中点画圆法第24页，本讲稿共162页若d0,则应取P1(xP+1,yP)为下一个像素,而且再下一个像素的判别式为d=F(xP+2,yP-0.5)=(

11、xP+2)2+(yP-0.5)2-R2=d+2xP+3而d0,则应取P2(xP+1,yP-1)为下一个像素,而且再下一个像素的判别式为d=F(xP+2,yP-1.5)=(xP+2)2+(yP-1.5)2-R2=d+2(xP-yP)+5由于第一个像素是(0，R),因而d的初始值为d0=F(1,R-0.5)=1.25-R第25页，本讲稿共162页根据以上分析,可得中点画圆法算法如下:voidMidPoint-Circle(r,color)intr,clor;intx,y;floatd;x=0;y=r;d=1.25-r;putpixel(x,y,color);while(xy)if(d0)d+=2*

12、x+3;x+;第26页，本讲稿共162页elsed+=2*(x-y)+5;x+;y-;putpixel(x,y,color);第27页，本讲稿共162页在上述的算法中,判别式d使用了浮点数,影响了算法的效率。为了摆脱浮点数,令e=d-0.25,则e的初始值为1-r。判别式d0对应于e-0.25。而e的初始值为整数,且在运算过程中的增量也是整数,故e始终是整数,因而e-0.25等价于e0。改进之后的算法为第28页，本讲稿共162页voidMidPoint-Circle(r,color)intr,clor;intx,y,e;x=0;y=r;e=1-r;putpixel(x,y,clolor);wh

13、ile(xy)if(e0)e+=2*x+3;x+;第29页，本讲稿共162页elsee+=2*(x-y)+5;x+;y-;putpixel(x,y,clolor);第30页，本讲稿共162页上述算法中,e的增量是x,y的线性函数。每当x递增1,e递增2；每当y递减1,e递增2。由于初始像素为(0,r),所以x可以看成从3开始递增,y可看成从2r+2开始递减。因而上述算法可改进为第31页，本讲稿共162页voidMidPoint-Circle(r,color)intr,clor;intx,y,deltax,deltay,e;x=0;y=r;e=1-r;deltax=3;deltay=2-r-r;

14、putpixel(x,y,color);while(xy)if(e0,这时,右下方像素D在圆外,圆弧与候选点的关系只可能是和的情形,最佳逼近圆弧的像素只可能是D与V二者之一。为了确定D和V哪个更接近于圆弧,令DV=|D|-|V|=|(x+1)2+(y-1)2-R2|-|x2+(y-1)2-R2|第38页，本讲稿共162页若DV0,应取正下方像素V。而当DV=0时,二者均可取,约定取右下方像素D。对于情形,由于右下方像素D在圆外,而正下方像素V在圆内,所以D0,V0,因此DV=D+V=(x+1)2+(y-1)2-R2+x2+(y-1)2-R2=2D-2x-1第39页，本讲稿共162页故可根据2D

15、-2x-1的符号,在情形判断应取D或V。对于情形,D和V都在圆外,应取V为下一像素。由于这时D0且V0,因此2D-2x-1=D+V0可见,在D0的情况下,若2D-2x-10,应取D为下一像素,否则取V作为下一像素。第40页，本讲稿共162页如果D0,这时,右下方像素D在圆内,圆弧与候选点的关系只可能是和的情形。这时最佳逼近圆弧的像素只可能是H或D之一。同样可令HD=|H|-|D|=|(x+1)2+y2-R2|-|(x+1)2+(y-1)2-R2|若HD0,则D到圆的距离小于H到圆的距离,这时应取D为下一个像素。而当HD=0时,二者均可,约定取正右方像素H。第41页，本讲稿共162页对于情形,H

16、总在圆外,D在圆内,因而有H0,D0,所以HD=H+D=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2D+2y-1故可根据2D+2y-1的符号,在情形判断应取H或D。第42页，本讲稿共162页而对于情形。这时,H、D都在圆内,而在这段圆弧上,y是x的单调递减函数,所以只能取H为下一个像素。又H0且D0,因此,2D+2y-1=H+D0与情形的判别条件一致。可见在D=0)putpixel(x,y,color);if(delta0)delta1=2*(delta+y)-1;if(delta10)delta2=2*(delta-x)-1;if(delta2=0)direction=2;

17、elsedirecion=3;elsedirection=2;switch(direction)case1:x+;delta+=2*x+1;break;第48页，本讲稿共162页case2:x+;y-;delta+=2*(x-y+1)break;case3:y-;delta+=(-2*y+1);break;第49页，本讲稿共162页3.2.2椭圆的扫描转换中点画圆法可以推广到一般二次曲线的生成,下面以中心在原点的标准椭圆的扫描转换为例说明。设椭圆的方程为F(x,y)=b2x2+a2y2-a2b2=0其中,a为沿x轴方向的长半轴长度,b为y轴方向的短半轴长度,a、b均为整数。不失一般性,我们只讨

18、论第一象限椭圆弧的生成。需要注意的是,在处理这段椭圆时,必须以弧上斜率为-1的点(即法向量两个分量相等的点)作为分界把它分为上部分和下部分,如图3.6所示。第50页，本讲稿共162页图3.6第一象限的椭圆弧第51页，本讲稿共162页该椭圆上一点(x,y)处的法向量为第52页，本讲稿共162页其中,i和j分别为沿x轴和y轴方向的单位向量。从图3.6可看出,在上部分,法向量的y分量更大,而在下部分,法向量的x分量更大,因而,在上部分若当前最佳逼近理想椭圆弧的像素(xP,yP)满足下列不等式b2(xP+1)a2(yP-0.5)而确定的下一个像素不满足上述不等式,则表明椭圆弧从上部分转入下部分。第53

19、页，本讲稿共162页在上部分,假设横坐标为xP的像素中与椭圆弧更接近点是(xP,yP),那么下一对候选像素的中点是(xP+1,yP-0.5)。因此判别式为d1=F(xP+1,yP-0.5)=b2(xP+1)2+a2(yP-0.5)2-a2b2若d10,中点在椭圆内,则应取正右方像素,且判别式应更新为d1=F(xP+2,yP-0.5)=b2(xP+2)2+a2(yP-0.5)2-a2b2=d1+b2(2xP+3)第54页，本讲稿共162页当d10,中点在椭圆之外,这时应取右下方像素,并且更新判别式为d1=F(xP+2,yP-1.5)=b2(xP+2)2+a2(yP-1.5)2-a2b2=d1+b

20、2(2xP+3)+a2(-2yP+2)由于弧起点为(0,b),因此,第一中点是(1,b-0.5),对应的判别式是d10=F(1,b-0.5)=b2+a2(b-0.5)2-a2b2=b2+a2(-b+0.25)第55页，本讲稿共162页在下部分,应改为从正下方和右下方两个像素中选择下一像素。如果在上部分所选择的最后一像素是(xP,yP),则下部分的中点判别式d2的初始值为d20=F(xP+0.5,yP-1)=b2(xP+0.5)2+a2(yP-1)2-a2b2d2在正下方向与右下方向的增量计算与上部分类似,这里不再赘述。下部分弧的终止条件是y=0。第56页，本讲稿共162页第一象限椭圆弧的扫描转

21、换中点算法的伪C描述如下:voidMidpointEllipse(a,b,color)inta,b,color;intx,y;floatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y,color);while(b*b*(x+1)a*a(y-0.5)if(d10)if(d20)d2+=b*b(2*x+2)+a*a*(-2*y+3);x+;y-;elsed2+=a*a*(-2*y+3);第58页，本讲稿共162页y-;putpixel(x,y,color);第59页，本讲稿共162页3.3 区区 域域 填填 充充 3.3.1多边形区域填充这里所讨论的

22、多边形域可以是凸的、凹的,还可以是带孔的。该算法的基本原理是按扫描线顺序,对每一条扫描线执行如下四步:第60页，本讲稿共162页(1)求扫描线与多边形各边的交点;(2)将求得的交点按递增顺序进行排序;(3)交点配对,确定相交区间;(4)将相交区间内的像素置成多边形色,相交区间外的像素置成背景色。第61页，本讲稿共162页图3.7多边形域的填充第62页，本讲稿共162页如图3.7所示,扫描线6与多边形的边界线交于四点A、B、C、D,得到的各交点的横坐标分别为2、4、8、11,按递增顺序排序后仍为2、4、8、11,相交区间为2,4、8,11,这两个区间的像素置成多边形色,把相交区间外的像素置成背景

23、色。第63页，本讲稿共162页图3.8对区域边界上像素全部填充的结果第64页，本讲稿共162页下面再进一步讨论填充算法实现问题。该算法关键在于计算每条扫描线与多边形各边的交点,直接用直线方程求交点的方法效率较低,是不可取的。为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边,可以为每一条扫描线建立活性边表,以存放与该扫描线相交的边的有关信息,如扫描线与该边的交点x等。第65页，本讲稿共162页由于边的连贯性(即当某条边与当前扫描线相交时,它很可能也与下一条扫描线相交),以及扫描线的连贯性(即当前扫描线和各边的交点顺序与下一条扫描线和各边的交

24、点顺序很可能相同或非常类似),我们根据当前扫描线的活性边表来导出下一条扫描线的活性边表,不必为下一条扫描线从头开始构造活性边表。设边的直线方程为ax+by+c=0若y=yi时,x=xi,则当y=yi+1时第66页，本讲稿共162页令x=-b/a,上式表明某一条边与当前扫描线相交,交点x坐标为xi,如果它与下一条扫描线相交,交点x坐标为xi+1,则xi+1=xi+x。此外,如果它与下一条扫描线不相交,那么要及时把它从活性边表中删除出去,避免下一步进行无谓的计算。因而活性边表的结点中至少应为对应边保存如下内容:x:当前扫描线与边的交点;x:从当前扫描线到下一条扫描线之间的x增量;ymax:边所交的

25、最高扫描线号。第67页，本讲稿共162页图3.9图3.7中扫描线6和扫描线7的活性边表(a)扫描线6的活性边表；(b)扫描线7的活性边表(a)(b)第68页，本讲稿共162页图3.10图3.7中各扫描线的新边表第69页，本讲稿共162页3.3.2边填充算法 图3.11(a)所示为对图中的多边形的各边打上了边标志,图3.11(b)所示为扫描线4填充前和填充后的各像素,填黑色者表示置为多边形色。边填充算法的伪C算法如下:第70页，本讲稿共162页defineFALSE0edge-mark-fill(polydef,color)多边形定义polydef;intcolor;对多边形polydef每条边

26、进行直线扫描转换;InsideFlag=FALSE;For(每条与多边形polydef相交的扫描线y)for(扫描线上每个像素x)if(像素x被打上边标志)InsideFlag=!(InsideFlag);if(InsideFlag!=FALSE)putpixel(x,y,color);elseputpixel(x,y,backgroud);第71页，本讲稿共162页图3.11边填充算法示意图第72页，本讲稿共162页3.3.3种子填充算法 种子填充算法是从多边形内部一个已知像素出发,找到区域内的所有像素,并把这些像素置成多边形色。算法原理如下:种子像素入栈,当栈非空时执行如下三步操作:(1)

27、栈顶像素出栈;(2)将出栈像素置成多边形色;(3)按左、上、右、下顺序检查与出栈像素相邻的四个像素,若其中某个像素不在边界且未置成多边形色,则把该像素入栈。第73页，本讲稿共162页如图3.12所示,种子像素为S(3,3),用种子填充算法填充该封闭区域时各像素出栈的顺序为(3,3)、(3,4)、(2,4)、(4,3)、(5,2)、(4,2)、(3,2)、(2,2)、(2,3)。第74页，本讲稿共162页上述的算法把连通区域内的像素都压入堆栈,有些像素会入栈多次,这不仅降低了算法的时间效率,而且增大了空间开销。其实,我们可以在任意一个扫描线与多边形的相交区间中,只取一个种子像素,并将种子像素入栈

28、,当栈非空时作如下四步操作:第75页，本讲稿共162页(1)栈顶像素出栈;(2)沿扫描线对出栈像素的左右像素进行填充,直至遇到边界像素为止,也就是对包含出栈像素的整个区间进行填充;(3)上述区间内最左最右的像素分别记为xl和xr;(4)在区间xl,xr中检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素,若存在非边界、非填充的像素,则把每一区间的最右像素入栈。第76页，本讲稿共162页上述改进之后的算法称之为扫描线种子填充算法,其伪C语言描述如下:voidscanline-seed-fill(polydef,color,x,y)多边形定义polydef;intcolo

29、r,x,y;/*(x,y)为种子像素*/intx,y,x0,xl,xrpush(seed(x,y);/*种子像素x栈*/while(栈非空)第77页，本讲稿共162页pop(pixel(x,y);/*栈顶像素出栈,并置为(x,y)*/putpixel(x,y,color);x0=x+1;while(getpixel(x0,y)的值不等于边界像素颜色值)/*填充出栈像素的右方像素*/putpixel(x0,y,color);x0=x0+1;xr=x0-1;/*最右像素*/x0=x-1;第78页，本讲稿共162页while(getpixel(x0,y)的值不等于边界像素颜色值)/*填充出栈像素的左

30、方像素*/putpixel(x0,y,color);x0=x0-1;xl=x0+1;/*最左像素*/*检查上一条扫描线,若存在非边界且未填充的像素,则将各连续区间的最右像素入栈*/x0=xl;y=y+1;第79页，本讲稿共162页while(x0=xr)flag=0;while(getpixel(x0,y)的值不等于边界像素颜色值)&(getpixel(x0,y)的值不等于多边形内像素颜色值)&(x0 xr)if(flag=0)flag=1;x0+if(flag=1)if(x0=xr)&(getpixel(x0,y)的值不等于边界像素颜色值)&(getpixel(x0,y)的值不等于多边形内像

31、素颜色值)push(x0,y);第80页，本讲稿共162页elsepush(x0-1,y);flag=0;xnext=x0;while(pixel(x0,y1)等 于 边 界 像 素 颜 色 值)|(pixel(x0,y1)等 于 多 边 形 内 像 素 颜 色 值)&(x0=xr)x0+;if(xnext=x0)x0+;第81页，本讲稿共162页/*检查下一条扫描线,若存在非边界,未填充的像素,则将各连续区间的最右像素入栈;处理与前面一条扫描线的算法相同,只要把y+1换为y-1即可*/第82页，本讲稿共162页3.4 字字 符符 的的 生生 成成 3.4.1字符生成的方法矢量字符使用矢量的方

32、向和长度来表示字符中的每一笔笔划。矢量的方向编码如图3.13所示。第83页，本讲稿共162页图3.13矢量的方向编码第84页，本讲稿共162页一个88西文字符点阵包括64个点,需要64位二进制数(占八个字节)表示,一个1616点阵汉字,需要256位表示,即32个字节。英文字母“F”的88点阵如图3.14所示,其二进制与十六进制分别表示为第85页，本讲稿共162页图3.14字符“F”88点阵第86页，本讲稿共162页111111100 xfe100000000 x80100000000 x80111111000 xfc100000000 x80100000000 x80100000000 x80

33、100000000 x80第87页，本讲稿共162页3.4.2点阵字符字符库有压缩型和非压缩型两种。UCDOS中的1616点阵汉字字符库是非压缩型的,它分94个区94个位,每个字符由区码和位码编码,区码和位码各用一个字节(最高位为1)来表示。要显示输出一个字符,必须从字符库中读取相应的字符掩膜矩阵数据。其方法是根据区码和位码计算出字符掩膜矩阵在字符库中的起始位置,从起始位置开始连续32个字节为该字符的掩膜矩阵数据。计算公式为第88页，本讲稿共162页row=(区码0a1h)7fhcol=(位码0a1h)7fhrec=row94+colstart=rec32其中,h表示十六进制,为按位与运算符,

34、rec为字符在字符库中的序号,start为字符掩膜矩阵在字符库中的起始位置。第89页，本讲稿共162页假 如 一 个 字 符 掩 膜 矩 阵 存 储 于 字 符 型 数 组buf32中,可用下面的伪程序输出该字符。voidhz16xs(intx,inty,intcolor)inti,j,k;for(i=0;i16;i+)for(j=0;j2;j+)for(k=0;k(7-k)&1)putpixel(x+j*8+k,y+i,color);第90页，本讲稿共162页读者可参照本节所附的参考算法。此外,常常在输出字符时要考虑字体、字型、字号和方向等属性,可将上述算法加以修改实现。例如,为了实现黑体字

35、,若某个像素对应掩膜矩阵中的值为1,则将该像素及其正右方像素置为字符颜色即可。第91页，本讲稿共162页3.5 图图 形形 裁裁 剪剪 3.5.1直线段裁剪直线段裁剪常有三种方法:DanCohen和IvanSutherland直线段裁剪算法、中点再分直线段裁剪算法和LiangBarsky算法。第92页，本讲稿共162页1.DanCohen和IvanSutherland直线段裁剪算法DanCohen和IvanSutherland直线段裁剪算法是由DanCohen和IvanSutherland两人提出的,主要分三步进行。(1)将矩形窗口的四条边界延长,则整个平面被分成九个区域,如图3.15所示,每

36、个区域内的点都对应着一个四位二进制的区位码,其各位含义如图3.16所示。第93页，本讲稿共162页图3.15区域划分及编码第94页，本讲稿共162页图3.16区位码各位含义第95页，本讲稿共162页(2)判断P1、P2是否都在窗口内。(a)若C1=C2=0,即P1、P2的编码全为零,线段P1P2在窗口内,保留线段P1P2,过程结束。(b)否则,若C1C20,即作P1、P2编码的逻辑与,结果为非零时,表示P1、P2在窗口外同侧,弃之,过程结束。(c)否则,线段必有一点在窗口外,令该点为P1,进行下一步。第96页，本讲稿共162页(3)根据P1点的编码确定其在哪条边界线之外,求线段与该边界的交点P

37、,交点把线段分成两段,舍去P1P段,把交点P作为剩余线段的P1端点重新进行第二步。如图3.17所示,线段a经第二步测试为窗内口的线段(C1=C2=0),取之。第97页，本讲稿共162页图3.17DanCohen和IvanSutherland直线段裁剪算法示意图第98页，本讲稿共162页DanCohen和IvanSutherland直线段裁剪算法的伪C代码如下:defineLEFT1defineRIGHT2defineBOTTOM4defineTOP8voidencode(x,y,code)floatx,y;int*code;intc;c=0;if(xXR)c=c|RIGHT;if(yYT)c=

38、c|TOP;*code=c;return;voidSwapPoint(x1,y1,x2,y2)float*x1,*y1,*x2,*y2;floatt;t=*x1;*x1=*x2;*x2=t;t=*y1;*y1=*y2;*y2=t;voidSwapCode(code1,code2)第100页，本讲稿共162页int*code1,*code2;intt;t=*code1;*code1=*code2;*code2=t;/*(x1,y1)与(x2,y2)是线段端点坐标,其它四个参数分别为窗口的左、下、右、上边界*/C-S-Line-Clip(x1,y1,x2,y2,XL,XR,YB,YT)floatx

39、1,y1,x2,y2,XL,XR,YB,YT;intcode1,code2,code;encode(x1,y1,&code1);第101页，本讲稿共162页encode(x2,y2,&code2);while(code10|code20)if(code1&code20)return;if(code1=0)SwapPoint(&x1,&y1,&x2,&y2);SwapCode(&code1,&code2);code=code1;if(LEFT&code0)/*线段与左边界相交*/x=XL;y=y1+(y2-y1)*(XL-x1)(x2-x1);第102页，本讲稿共162页elseif(RIGHT

40、&code0)/*线段与右边界相交*/HJx=XR;y=y1+(y2-y1)*(XR-x1)(x2-x1);elseif(BOTTOM&code0)/*线段与下边界相交*/y=YB;x=x1+(x2-x1)*(YB-y1)(y2-y1);elseif(TOP&code0)/*线段与上边界相交*/y=YT;x=x1+(x2-x1)*(YT-y1)(y2-y1);第103页，本讲稿共162页x1=x;y1=y;encode(x,y,code1);Displayline(x1,y1,x2,y2);return;第104页，本讲稿共162页2.中点再分直线段裁剪算法中点再分直线段裁剪算法是对DanCo

41、hen和IvanSutherland直线段裁剪算法的改进。在DanCohen和IvanSutherland直线段裁剪算法中,为了避免求直线段与窗口边界的交点,用不断对分线段的方法排斥线段在窗口外的部分,最后求出离线段端点最远的可见点(所谓可见点就是线段落在窗口内的点),若这两点存在,则这两点就是线段P1P2的可见线段端点,下面我们仅介绍如何在线段P1P2上求离P1最远的可见点,其具体步骤如下：第105页，本讲稿共162页(1)测试P2是否在窗口内。若是,则P2就是离P1最远的可见点,结束;否则,进行下一步。(2)测试P1P2是否在窗外同侧。若是,P1P2全部不可见,结束;否则,进行下一步。(3

42、)取P1P2的中点Pm,若PmP2在窗外同侧,弃之,剩余段以P2代替Pm重复步骤(2)。否则,以P1代替Pm重复步骤(2),直到线段不能再分为止。第106页，本讲稿共162页3.LiangBarsky算法LiangBarsky算法是直线段的基于矩形窗口的参数化裁剪方法。设直线段的两个端点坐标分别为(x1,y2)和(x2,y2),其参数方程为第107页，本讲稿共162页其中,x=x2-x1,y=y2-y1。由于矩形窗口内的点满足因而有第108页，本讲稿共162页上述不等式可以表示为upkqk k=1,2,3,4其中,参数p,q定义为 p1=-x,q1=x1-xL p2=x,q2=xR-x1 p3

43、=-y,q3=y1-yB p4=y,q4=yT-y1第109页，本讲稿共162页如果pk=0,则表明直线段平行于矩形窗口边界之一,若还满足qk0,则表明直线段完全在边界外,舍弃该线段。若qk0,则表明直线段平行于矩形窗口边界并且与窗口相交。如果pk0,直线段从矩形窗口边界延长线的外部延伸到内部。如果pk0,直线段从矩形窗口边界延长线的内部延伸到外部。当pk非零时,可以计算出直线段与边界k的延长线的交点参数u值。第110页，本讲稿共162页上述不等式的解为第111页，本讲稿共162页若u1u2,则u1、u2是直线段在矩形窗口内的部分的端点参数。否则,表明直线段完全落在边界外。LiangBarsk

44、y算法的伪C代码描述如下:intLiangBarsky(x1,y1,x2,y2,xL,yB,xR,yT,ul,uu)floatx1,y1,x2,y2,xL,yB,xR,yT;float*ul,*uu;intk;floatr,u1,u2,dx,dy,p4,q4;u1=0.0;u2=1.0;dx=x2-x1;dy=y2-y1;第112页，本讲稿共162页p0=-dx;p1=dx;p2=-dy;p3=dy;q 0=x1-xL;q 1=xR-x1;q 2=y1-yB;q3=yT-y1;for(k=0;k4;k+)if(fabs(pk)=0.0)continue;elsereturn(0);elser=

45、qk/pk;if(pk0.0)if(ru1)u1=r;第113页，本讲稿共162页if(u1u2)return(0);*ul=u1;*uu=u2;第114页，本讲稿共162页3.5.2多边形裁剪对于多边形裁剪,自然就想到用线段裁剪方法处理多边形的每一条边界,但是,这样做将得到一系列不连接的直线段,如图3.18所示。但真正想显示的是如图3.19所示的裁剪后有边界的区域。因而用线段裁剪方法处理多边形的每一条边界是不可行的。通常采用Sutherland-Hodgman裁剪算法,该算法又称为逐边裁剪法,其基本思想是逐次用窗口的一条边裁剪多边形。第115页，本讲稿共162页图3.18用线段裁剪算法处理多

46、边形后的结果第116页，本讲稿共162页图3.19正确的裁剪结果第117页，本讲稿共162页图3.20线段SP与裁剪线的四种位置关系第118页，本讲稿共162页如图3.21所示,用裁剪窗口的左边界裁剪图3.18中多边形的每一条边。对于P1P2,令P1为S,P2为P,由于S在不可见一侧,P在可见一侧,因而输出线段SP与裁剪线的交点I1和线段终点P(即P2)。对于P2P3,令P2为S,P3为P,由于S、P都在可见一侧,则输出P(即P3)。同样,对于P3P4,输出P4,对于P4P5,输出P5。而对于P5P1,令P5为S,P1为P,由于S在可见一侧,P在不可见一侧,则输出线段SP与裁剪线的交点I2。至

47、此,用裁剪窗口的左边界裁剪图3.18中多边形的每一条边的过程结束,结果如图3.22所示。第119页，本讲稿共162页图3.21用窗口的左边界裁剪多边形第120页，本讲稿共162页图3.22裁剪结果第121页，本讲稿共162页3.6 属属 性性 控控 制制 3.6.1线型与线宽1.线型的处理在实际绘图中,我们经常遇到绘制指定线型的线条,如点画线、虚线等。线型可以用一个布尔值的序列来存放,如用一个长度为32的布尔数组pattern存放。把扫描转换算法中的写像素语句改为if(patterni%32)putpixel(x,y,color);第122页，本讲稿共162页2.线宽的处理 线宽的处理是指绘制

48、多个像素宽的图形。通常有线刷子、方形刷子和区域填充的三种方法。线刷子的基本原理是:把扫描转换所得的每个像素上下方或左右方半线宽之内的像素全部置成图形颜色,即可“刷出”具有一定宽度的图形。第123页，本讲稿共162页对于直线来说,如果直线斜率在,之间,把直线扫描转换所得的每个像素上下方半线宽之内的像素全部置成直线颜色,否则,把直线扫描转换所得的每个像素左右方半线宽之内的像素全部置成直线颜色。如图3.23所示为线宽是三个像素的直线。对于圆弧来说,在斜率为的点处,必须将线刷子在水平与垂直方向之间切换。第124页，本讲稿共162页如图3.24所示为线宽是三个像素的圆弧。线刷子简单、效率高。但是,当线宽

49、较大时,看起来很不自然。当比较接近水平的直线与比较接近垂直的直线汇合时,汇合处外角将有缺口。同样线宽的斜线与水平线或垂直线不一样粗。当线宽为偶数个像素时,用上述方法绘制的线条要么粗一个像素,要么细一个像素。圆弧在接近水平或垂直的地方,线条更粗一些,而在斜率接近的点附近,线条更细一些。第125页，本讲稿共162页图3.23用线刷子绘制的三个像素宽的直线第126页，本讲稿共162页图3.24用线刷子绘制的三个像素宽的圆弧第127页，本讲稿共162页图3.25用方形刷子绘制的圆弧第128页，本讲稿共162页方形刷子的基本原理是:方形刷子是把扫描转换所得的每个像素上下方和左右方半线宽之内的像素全部设置

50、成直线颜色。图3.25所示为用方形刷子绘制的圆弧。但是这种方法将会重复地写像素,这是因为对应于相邻两像素的方形一般会重叠。为了避免重复写像素,可以为每个扫描线建一个表,存放该扫描线与线条的相交区间左右端点位置。第129页，本讲稿共162页在每个像素使用方形刷子时,用该方形与各扫描线的相交区间端点坐标去更新原表内端点数据。如图3.26所示为刷子移动的相邻两步和有关扫描线的临时数据结构所保存的对应于各步的区间端点坐标。第130页，本讲稿共162页图3.26刷子移动的相邻两步对应的数据结构第131页，本讲稿共162页3.6.2字符属性在3.4节中我们介绍了字符的生成方法,但是,没有考虑字体、字号等属