计算机图形学 |
您所在的位置：网站首页 › 直线图形的概念 › 计算机图形学 |
计算机图形学
|
计算机图形学----直线与多边形的裁剪 裁剪算法详解：在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 一、直线段编码裁剪算法（Cohen-Sutherland算法）假设窗口是标准矩形，即边与坐标轴平行的矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边描述。 算法基本思想： 对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理： (1) 直线段完全可见，“简取”之。 (2) 直线段完全不可见，“简弃”之。 (3) 直线段既不满足“简取”的条件，又不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。 原理：将裁剪窗口各边延长，形成9个区域，最中间的框便是裁剪窗口，编码0000，其他的区域都有一个各自的编码，使得任意落在该平面的直线端点都会有各自的编码，直接通过编码运算（与、异或运算），算出完全可见和完全不可见的。 裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口内，应取之。若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。 程序实现： #defineLEFT 1 #defineRIGHT 2 #defineBOTTOM 4 #defineTOP 8 intCMy1_1View::C_S_Line(CDC *pDC, int x1, int y1, int x2, int y2) { int code1,code2,code,x,y; encode(x1,y1,&code1); //(x1,y1)处的编码 encode(x2,y2,&code2); //(x2,y2)处的编码 while (code1!=0||code2!=0) //当 code1 不等于0 或code2 不等于0 { if ((code1&code2)!=0) return 0; //当 code1 与code2 不等于0，在同侧； code=code1; if (code1==0) code=code2; if ((LEFT&code)!=0) //求交点 { x=WL; y=y1+(y2-y1)*(WL-x1)/(x2-x1); } else if ((RIGHT&code)!=0) { x=WR; y=y1+(y2-y1)*(WR-x1)/(x2-x1); } else if ((BOTTOM&code)!=0) { y=WB; x=x1+(x2-x1)*(WB-y1)/(y2-y1); } else if ((TOP&code)!=0) { y=WT; x=x1+(x2-x1)*(WT-y1)/(y2-y1); } if (code==code1) { x1=x;y1=y; encode(x,y,&code1); } else { x2=x;y2=y; encode(x,y,&code2); } } //end while,表示code1，code2 都为0，其中的线段为可视部分 pDC->MoveTo(x1+350,y1); pDC->LineTo(x2+350,y2); } //对坐标点(x,y)编码 void CMy1_1View::encode(int x, int y, int*code) { int c=0; if(xWR) c=c|RIGHT; if(yWT) c=c|TOP; *code=c; }程序运行效果(后附文档，有详细操作)： 直线与多边形的裁剪.docx 二、多边形裁剪对于一个多边形，可以把它分解为边界的线段逐段进行裁剪。但这样做会使原来封闭的多边形变成不封闭的或者一些离散的线段。当多边形作为实区域考虑时，封闭的多边形裁剪后仍应当是封闭的多边形，以便进行填充。为此，可以使用Sutherland-Hodgman算法。该算法的基本思想是一次用窗口的一条边裁剪多边形。 算法的每一步，考虑窗口的一条边以及延长线构成的裁剪线。该线把平面分成两个部分：一部分包含窗口，称为可见一侧；另一部分称为不可见一侧。依序考虑多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种。 (1)S,P均在可见一侧 (2)S,P均在不可见一侧 (3)S可见,P不可见 (4)S不可见,P可见。 上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图一样，知识判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。 基于divide and conquer策略的Sutherland-Hodgman算法 typedef struct { float x; float y; }Vertex; typedef Vertex Edge[2]; typedef Vertex VertexArray[MAX]; void SutherlandHodgmanClip（VertexArray InVertexArray, VertexArray OutVertexArray, edge ClipBoundary, int &Inlength, int &Outlength） { Vertex s, p, ip; int j; Outlength = 0; S = InVertexArray [InLength -1]; for (j = 0; j < Inlength; j++) { P = InVertexArray [j]; if(Inside (P, ClipBoundary)) { if(Inside (S, ClipBoundary)) //SP在窗口内，情况1 Output(p, OutLength, OutVertex Array) else{ //S在窗口外, 情况4 Intersect (S, P, ClipBoundary, &ip); Output (ip, OutLength, OutVertexArray); Output (P, OutLength, OutVertexArray); } } else if (Inside (S, WindowsBoundary)) { //S在窗口内，P在窗口外,情况3 Intersect (S, P, ClipBoundary, &ip); Output (ip, OutLength, OutVertexArray); } //情况2没有输出 S = P; } } //判点在窗口内 bool Inside (Vertex &TestPt, Edge ClipBoundary) { if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边 if(testpt.y>=ClipBoundary[0].y) return TRUE; else if(ClipBoundary[1].x< ClipBoundary[0].x) //裁剪边为窗口上边 if(testpt.y ClipBoundary[0].y) //裁剪边为窗口右边 if(testpt.x= ClipBoundary[0].x) return TRUE; return FALSE; } //直线段SP和窗口边界求交，返回交点； void Intersect (Vertex&S,Vertex &P,Edge ClipBoundary,Vertex& IntersectPt) { if(ClipBoundary[0].y== ClipBoundary[1].y)//水平裁剪边 { IntersectPt.y = ClipBoundary[0].y; IntersectPt.x = S.x+( ClipBoundary[0].y -s.y)*(p.x - s.x) / (p.y - s.y); } else //垂直裁剪边 { Intersect.x = ClipBoundary[0].x; Intersect.y = s.y + (ClipBoundary[0].x - s.x)*(p.y - s.y) / (p.x. - s.x)； } }http://www.doc88.com/p-3681059225014.html |
【本文地址】
今日新闻 |
推荐新闻 |