二维图形裁剪的课程设计

华东交通大学图形学课程设计 课程设计名称：各种二维图形裁剪技术研究姓名： 学号：学院：基础学院班级：信息与计算科学2010-1指导老师：小组成员： 目录1、 摘要 22、 二维图形裁剪22.1 裁剪的原理 22.2 裁剪的分类32.2.1.线段的裁剪32.2.2多边形的裁剪52.2.3.圆和曲线的裁剪63、 算法 63.1 裁剪算法73.2 裁剪圆算法93.3 裁剪窗口是圆算法 114、心得体会125、参考文献126、功能实现效果的图片展示131、摘要近几十年来，计算机图形学有了引人瞩目的发展，它已广泛应用于计算机辅助设计、电视广告、动画和仿真等许多领域并发挥着重要作用。可以说计算机图形学已经发展成为一门成熟的学科。在各种实践应用中，计算机图形学的许多基础算法发挥着不可替代的重要作用，因此不断提高和完善图形学的基础算法至关重要。计算机图形学是研究在计算机中如何构造图形，并把图形的描述数据(数学模型)通过指定的算法转化为图形显示的学科。目前，计算机图形学的主要研究对象包括：点、线、面二维图形学：体三维图形学以及场等的数学构造方法与其图形显示以及它们的变化情况。2、二维图形裁剪在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。从数据集合中抽取所需信息即识别指定区域内或区域外的图形部分的过程称为裁剪算法，简称裁剪。它是计算机图形学中许多重要问题的基础。裁剪典型的用途是确定场景或画面中位于给定区域之内的部分。这一区域称为裁剪窗口。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗口内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以，一般采用先裁剪再扫描转换的方法。裁剪的应用包括：从定义的场景中抽取出用于观察的部分；在三维视图中标识出可见面：防止线段或对象的边界混淆；使用实体造型来创建对象；显示多窗口的环境；允许选择图形一部分进行复制、移动或删除等绘图操作。对于不同的应用，裁剪窗口可以是多边形或包含有曲线边界。 2.1裁剪的原理 裁剪的基本目的是判断图形元素是否部分或全部落在窗口区域之内，如果是，则进一步求出位于窗口内的部分。裁剪处理包括两个方面：判断图形元素是否在窗口内以及求图形元素与窗口的交。一般把窗口定义为矩形，由上、下、左、右四条边围成，即：(xL，yB)，(xR，yT)。裁剪的实质就是决定图形中哪些点、线段、文字以及多边形在窗口之内。对于点(x，y)，只要判断两对不等式：xLxxR，yByyT若四个不等式均成立。则点在矩形窗口之内；否则，点在矩形窗口之外。2.2 裁剪的分类裁剪算法大致包括对以下图形的裁剪：线段的裁剪(线段)区域的裁剪(多边形)区域的裁剪(圆和曲线)2.2.1线段的裁剪线段与窗口的关系有如下三种：（1）线段在窗口内，线段不需剪裁，完全可见；（2）线段在窗口外，即线段不需剪裁，完全不可见；（3）线段部分在窗口内，部分在窗口外，即需要求出线段与窗框的交点，并将窗口外的线段部分剪裁掉，只可见窗口内的直线部分。线段的裁剪算法就是要找出位于窗口内部的起始点和终止点的坐标。因矢量裁剪法对寻找起点和终点坐标的处理方法相同，下面以求始点坐标为例来说明线段矢量裁剪方法。在右图中，窗口的四条边界把XOY平面分成九个区域，分别用到对这九个窗口编号，设号区域为相应的可见窗口区，窗口的左下角点坐标（minX，minY），右上角点坐标为（maxX，maxY）。有一条矢量线段S，其起、终点的坐标分别为（Xs，Ys）和（Xe，Ye），则对线段S按矢量裁剪的算法步骤如下：1、若线段完全位于区域以外的任意区域内或落在（1，2，3）（3，6，9）（7，8，9）（1，4，7）中任意一区域组内，即满足下述条件之一：XsminX且XeminX且XeminX,YsminY且YeminY且YeminY则线段S不在窗口内，不必作进一步的求交点处理，否则转下一步。2、若线段满足minXXsmaxX且minXYsmaxY ,则线段的起点在窗口内，新的起点坐标（X，Y）即为（Xs,Ys）；否则，按以下各步判断与窗口的关系以及解算其新起点坐标（X，Y）。 3、若XsminY或YmaxY，则线段S与窗口无交点；(3) 若YmaxY且YsmaxY或者YminY且YsmaxY或当起点位于7区且Ye minY时，线段与窗口没有交点；否则还需作下面的判别;(b)若YsmaxY，则：（4-2-3）用（4-2-2）和（4-2-3）式求出的X若满足minXXmaxX，则（X,Y）的求解有效，否则线段与窗口仍无交点。4、当XsmaxX ，即线段起点位于窗口右界的右边，可仿照上述过程求出线段与右边界的交点。5、若起点（Xs,Ys）位于2或8区时，求解线段与窗口边界的交点公式为（4-2-4）和（4-2-5）式。（4-2-4）（4-2-5）用式（4-2-4）和（4-2-5）求解得在满足minXXmaxX时才有效，否则线段不在窗口内。同理，可求解出线段在窗口内新的终点坐标。 2.2.2 多边形的裁剪 多边形是计算机制图中常用的图形元素，大到行政区域，小到各种地物图块，都是多边形元素。 多边形的裁剪比直线要复杂得多。因为经过裁剪后，多边形的轮廓线仍要闭合，而裁剪后的边数可能增加，也可能减少，或者被裁剪成几个多边形，这样必须适当地插入窗口边界才能保持多边形的封闭性。这就使得多边形的裁剪不能简单地用裁剪直线的方法来实现。 对于多边形的裁剪，人们研究出了多种算法，其中萨瑟兰德霍奇曼（Sutherland-Hodgman）算法是根据相对于一条边界线裁剪多边形比较容易这一点，把整个多边形先相对于窗口的第一条边界裁剪，然后再把形成的新多边形相对于窗口的第二条裁剪，如此进行到窗口的最后一条边界，从而把多边形相对于窗口的全部边界进行了裁剪。其算法描述为：取多边形顶点Pi(i=1,2,n) ,将其相对于窗口的第一条边界进行判别，若点Pi位于边界的靠窗口一侧，则把Pi记录到要输出的多边形顶点中，否则不作记录。检查Pi点与Pi-1点（i=1时，检查Pi与Pn点）是否位于窗口边界的同一侧。若是，Pi点记录与否，随Pi-1点是否记录而定；否则计算出PiPi-1与窗口边界的交点，并将它记录到要输出的多边形的顶点中去。如此而已判别所有的顶点P1P2Pn后,得到一个新的多边形Q11,Q12,Qm,然后用新的多边形重复上述步骤1、，依次对窗口的第二、第三和第四条边界进行判别，判别完后得到的多边形Q14,Q24,Qm4即为裁剪的最后结果。如上图所示，演示了多边形的裁剪过程：（1）首先对窗口的右边界进行判别，从多边形的顶点P1开始依次判断。P1在右边界不可见一侧，故不记录P1点，且P1和P6在右边界同侧，则也不与右边界求交点。P2点在右边界可见一侧，且P2和P1在右边界异侧，因此求出P2P1与右边界交点记作Q1，同时把P2点记录下来作为（Q2）。P3点在右边界不可见一侧，但P3和P2在右边界异侧，因此求出P3P2与右边界交点记作Q3。P4点在右边界可见一侧，且P4和P3在右边界异侧，因此求出P4P3与右边界交点记作Q4，同时把P4点记录下来作为（Q5）。P5点在右边界不可见一侧，但P5和P4在右边界异侧，因此求出P5P4的右边界交占记作Q6。P6点在右边界不可见一侧，且P6和P5在右边界同侧，因此不求交点也不记录P6点。这样就得到了新多边形Q1,(Q2),Q3,Q4,(Q5),Q6（2）把新得到的多边形Q1,(Q2),Q3,Q4,(Q5),Q6对窗口的下边界进行判断，同理可得到新的多边形Q1,(Q2),Q3,Q4,Q5,Q6（3）新得到的多边形与窗口左边界和上边界进行判断，多边形无变化，即为多边形裁剪的最后结果。 2.2.3 圆和曲线的裁剪 对圆的裁剪思路是，首先通过圆的外接矩形判断来确定圆是否全部位于窗口的外边，若全部位于窗口外边，则裁剪过程结束。否则，将圆分解成一组短线段，然后按照直线裁剪的方法来进行。 由于曲线在实际绘制时是采用短直线来逼近曲线的方法实现，故曲线的裁剪也采用一般直线裁剪方法对每一短线段进行裁剪，从而实现对整个曲线的裁剪。3、算法3.1裁剪算法procedure TComputerGrapicsMainForm.Clip1Click(Sender: TObject);var i,j,Outside,Clip:Integer; xystring:string; Label tryagain; Label NextLine;begin /Windows coordinates W1:=90;W2:=270;w3:=40;w4:=160; /x coordinates y coordinates XY_Lines1,1,1:=110; XY_Lines1,1,2:=10; XY_Lines1,2,1:=290; XY_Lines1,2,2:=70; XY_Lines2,1,1:=290; XY_Lines2,1,2:=70; XY_Lines2,2,1:=250; XY_Lines2,2,2:=190; XY_Lines3,1,1:=250; XY_Lines3,1,2:=190; XY_Lines3,2,1:=70; XY_Lines3,2,2:=130; XY_Lines4,1,1:=70; XY_Lines4,1,2:=130; XY_Lines4,2,1:=110; XY_Lines4,2,2:=10; XY_Lines5,1,1:=160; XY_Lines5,1,2:=10; XY_Lines5,2,1:=160; XY_Lines5,2,2:=180; XY_Lines6,1,1:=10; XY_Lines6,1,2:=100; XY_Lines6,2,1:=300; XY_Lines6,2,2:=100; XY_Lines7,1,1:=10; XY_Lines7,1,2:=10; XY_Lines7,2,1:=30; XY_Lines7,2,2:=70; XY_Lines8,1,1:=120; XY_Lines8,1,2:=70; XY_Lines8,2,1:=250; XY_Lines8,2,2:=150; Canvas.Pen.Color := clRed;/Draw 6 lines in red color For i:=1 to 8 do begin Canvas.MoveTo(10+XY_Linesi,1,1,400-XY_Linesi,1,2); Canvas.LineTo(10+XY_Linesi,2,1,400-XY_Linesi,2,2); end; /Draw clipping retangle window in yellow Canvas.Pen.Color := clYellow;/Draw window in yellow color Canvas.MoveTo(10+90,400-40); Canvas.LineTo(10+270,400-40); Canvas.MoveTo(10+270,400-40); Canvas.LineTo(10+270,400-160); Canvas.MoveTo(10+270,400-160); Canvas.LineTo(10+90,400-160); Canvas.MoveTo(10+90,400-160); Canvas.LineTo(10+90,400-40); for i:=1 to 8 do begin for j:=1 to 2 do begin Xj:=XY_Linesi,j,1;Yj:=XY_Linesi,j,2; GetCodes(Sender,Xj,Yj,j);/check points of lines is outside the window? XYString:=IntToStr(Lj) +,+IntToStr(RJ)+ ,+IntToStr(BJ)+ ,+IntToStr(Tj); Memo1.Lines.add(XYString);/Show x,y coordinates to have a check end; for j:=1 to 2 do begin tryagain: Outside:=L1*L2+R1*R2+B1*B2+T1*T2; if outside0 then goto NextLine; if Outside=0 then /the lines is inside the window begin Clip:=Lj+Rj+Bj+Tj; if Clip0 then /Get new cliped coordinates of lines begin ClipSubProgram(sender,j);goto tryagain; end; end; end; /Draw Cliped lines in blue color Canvas.Pen.Color:=clBlue; Canvas.MoveTo(10+trunc(X1),400-trunc(Y1); Canvas.LineTo(10+trunc(X2),400-trunc(Y2); NextLine: end;end;3.2裁剪圆算法Procedure TComputerGrapicsMainForm.ClipCircle1Click(Sender: TObject);var i,j,x0,y0,RADIUS,Outside,Clip:Integer; xystring:string; Label tryagain; Label NextLine;begin /Windows coordinates W1:=90;W2:=270;w3:=40;w4:=160; x0:=120;y0:=70; RADIUS:=120; /x coordinates y coordinates XY_Lines1,1,1:=110; XY_Lines1,1,2:=10; XY_Lines1,2,1:=290; XY_Lines1,2,2:=70; XY_Lines2,1,1:=290; XY_Lines2,1,2:=70; XY_Lines2,2,1:=250; XY_Lines2,2,2:=190; XY_Lines3,1,1:=250; XY_Lines3,1,2:=190; XY_Lines3,2,1:=70; XY_Lines3,2,2:=130; XY_Lines4,1,1:=70; XY_Lines4,1,2:=130; XY_Lines4,2,1:=110; XY_Lines4,2,2:=10; XY_Lines5,1,1:=160; XY_Lines5,1,2:=10; XY_Lines5,2,1:=160; XY_Lines5,2,2:=180; XY_Lines6,1,1:=10; XY_Lines6,1,2:=100; XY_Lines6,2,1:=300; XY_Lines6,2,2:=100; XY_Lines7,1,1:=10; XY_Lines7,1,2:=10; XY_Lines7,2,1:=30; XY_Lines7,2,2:=70; XY_Lines8,1,1:=120; XY_Lines8,1,2:=70; XY_Lines8,2,1:=250; XY_Lines8,2,2:=150; Canvas.Pen.Color := clRed;/Draw 6 lines in red color For i:=1 to 8 do begin Canvas.MoveTo(10+XY_Linesi,1,1,400-XY_Linesi,1,2); Canvas.LineTo(10+XY_Linesi,2,1,400-XY_Linesi,2,2); end; /Draw clipping retangle window in yellow Canvas.Pen.Color := clYellow;/Draw window in yellow color Canvas.MoveTo(10+90,400-40); Canvas.LineTo(10+270,400-40); Canvas.MoveTo(10+270,400-40); Canvas.LineTo(10+270,400-160); Canvas.MoveTo(10+270,400-160); Canvas.LineTo(10+90,400-160); Canvas.MoveTo(10+90,400-160); Canvas.LineTo(10+90,400-40); for i:=1 to 360 do begin XY_Linesi,1,1:=x0+TRUNC(RADIUS*cos(i*3.14159/180); XY_Linesi,1,2:=y0+TRUNC(RADIUS*sin(i*3.14159/180); XY_Linesi,2,1:=x0+TRUNC(RADIUS*cos(i-1)*3.14159/180); XY_Linesi,2,2:=y0+TRUNC(RADIUS*sin(i-1)*3.14159/180); for j:=1 to 2 do begin Xj:=XY_Linesi,j,1;Yj:=XY_Linesi,j,2; GetCodes(Sender,Xj,Yj,j);/check points of lines is outside the window? XYString:=IntToStr(Lj) +,+IntToStr(RJ)+ ,+IntToStr(BJ)+ ,+IntToStr(Tj); Memo1.Lines.add(XYString);/Show x,y coordinates to have a check end; for j:=1 to 2 do begin tryagain: Outside:=L1*L2+R1*R2+B1*B2+T1*T2; if outside0 then goto NextLine; if Outside=0 then /the lines is inside the window begin Clip:=Lj+Rj+Bj+Tj; if Clip0 then /Get new cliped coordinates of lines begin ClipSubProgram(sender,j);goto tryagain; end; end; end; /Draw Cliped lines in blue color Canvas.Pen.Color:=clBlue; Canvas.MoveTo(10+trunc(X1),400-trunc(Y1); Canvas.LineTo(10+trunc(X2),400-trunc(Y2); NextLine: end;end;3.3裁剪窗口是圆算法Procedure TComputerGrapicsMainForm.CircleWindow1Click(Sender: TObject);var x0,y0,Radius:integer; x1,y1,x2,y2,length:integer; i:integer; X,Y,dx,dy,Distance:Single;begin x0:=120;y0:=70; Radius:=120; canvas.Brush.Style:=bsClear; canvas.Ellipse(x0-Radius,y0-Radius,x0+Radius,y0+Radius); x1:=0;y1:=0;x2:=250;y2:=350; if (abs(x2-x1)=abs(y2-y1) then length:=abs(x2-x1) else length:=abs(y2-y1); dx:=(x2-x1)/length; dy:=(y2-y1)/length; x:=x1+0.5; /here still can be discussed y:=y1+0.5